SIAM Journal on Discrete Mathematics · 1996 · 42 citations · 13 references
ComputingComputer ScienceMathematicsCombinatoricsGeometryOptimizationDelaunay TriangulationsGeometric OptimizationGeometry ProcessingGraph DrawingGraph Layout AlgorithmsDelaunay Triangulation AlgorithmsNonlinear OptimizationPlanar Graph AlgorithmsPlanar Graph DrawingPlanar Graph RepresentationsPlanar GraphsTriangulations
We give a characterization of all the planar drawings of a triangular graph through a system of equations and inequalities relating its angles; we also discuss minimality properties of the characterization. The characterization can be used: (1) to decide in linear time whether a given distribution of angles between the edges of a planar triangular graph can result in a planar drawing; (2) to reduce the problem of maximizing the minimum angle in a planar straight-line drawing of a planar triangular graph to a nonlinear optimization problem purely on a space of angles; (3) to give a characterization of the planar drawings of a triconnected graph through a system of equations and inequalities relating its angles; (4) to give a characterization of Delaunay triangulations through a system of equations and inequalities relating its angles; (5) to give a characterization of all the planar drawings of a triangular graph through a system of equations and inequalities relating the lengths of its edges; in turn, this result allows us to give a new characterization of the disc-packing representations of planar triangular graphs.
13
W. T. Tutte · Proceedings of the London Mathematical Society · 1963 · 1.1K citations
Algorithms for drawing graphs: an annotated bibliography
Giuseppe Di Battista, Peter Eades, Roberto Tamassia et al. · Computational Geometry · 1994 · 860 citations
How to draw a planar graph on a grid
Hubert de Fraysseix, János Pach, Richard Pollack · COMBINATORICA · 1990 · 644 citations
Convex Representations of Graphs
W. T. Tutte · Proceedings of the London Mathematical Society · 1960 · 281 citations
Planar graphs and poset dimension
Walter Schnyder · Order · 1989 · 269 citations