Click here for full text:
Drawing Straight Lines
Carroll, Jeremy J.
HPL200072
Keyword(s): lines; pseudolines; polar coordinates; trilinear coordinates; nonlinear programming; geometry
Abstract: We present a graphdrawing algorithm which respects extended colinearity 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 nonlinear program. These inequalities are solved by first solving linear inequalities in the angles, and then tackling the full nonlinear program. The solution is a drawing of the graph. The algorithm has been used to draw all the solutions to the 6Venn triangle problem.
17 Pages
Back to Index
