Back to Search Start Over

Angles of planar triangular graphs

Authors :
Luca Vismara
Giuseppe Di Battista
DI BATTISTA, Giuseppe
Luca, Vismara
S. Rao Kosaraju, David S. Johnson, Alok Aggarwal
L., Vismara
Source :
Scopus-Elsevier, STOC

Abstract

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.

Details

Database :
OpenAIRE
Journal :
Scopus-Elsevier, STOC
Accession number :
edsair.doi.dedup.....a5844c984beabf773eb8530d7026968f