1993 · 21 citations · 15 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, solving a problem that is explicitly mentioned as open by several authors; we also discuss minimalit y properties of the charact erization. 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 tackle the problem of maximizing the minimum angle of the drawing of a planar triangular graph by studying the solution-space of a non-linear optimization problem; (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 length of its edges; in turn, this result allows to give a new characterization of the disc packing represent ations of planar triangular graphs.
15
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
Embedding planar graphs on the grid
Walter Schnyder · Symposium on Discrete Algorithms · 1990 · 577 citations