Drawing Straight Lines

Carroll, Jeremy J.

HPL-2000-72

Keyword(s): lines; pseudo-lines; polar coordinates; trilinear coordinates; non-linear programming; geometry

Abstract: 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

Back to Index