Drawing Straight Lines

[摘要] We present a graph-drawing algorithm which respects extended co-linearity constraints. These are expressed as a set of 'straight' paths in a planar graph. Constraints of this sort are translated into a set of inequalities over polar coordinates of lines. These inequalities provide necessary and sufficient conditions for the lines to be an appropriate drawing of the graph. Combined with a formula expressing some aesthetic parameter these inequalities then express the graph drawing problem as a classic non-linear program. These inequalities are solved by first solving linear inequalities in the angles, and then tackling the full non-linear program. The solution is a drawing of the graph. The algorithm has been used to draw all the solutions to the 6-Venn triangle problem. 17 Pages

[发布机构] HP Development Company

[学科分类] 计算机科学（综合）

[关键词] lines;pseudo-lines;polar coordinates;trilinear coordinates;non-linear programming;geometry