hp home products & services support solutions how to buy
hp logo - invent
corner hp labs corner
search search
contact hp contact hp
hp labs home hp labs home
about hp labs about hp labs
research research
news and events news and events
careers @ labs careers @ labs
technical reports technical reports
talks and speeches talks and speeches
worldwide sites worldwide sites
corner corner
HP Labs Technical Reports

Click here for full text: PDF

Drawing Straight Lines

Carroll, Jeremy J.


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

printing icon
printing instructions printing instructions
Privacy Statement Legal Notices © 1994-2000 Hewlett-Packard Company