Back to Search
Start Over
Angles of planar triangular graphs
- 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.
- Subjects :
- Discrete mathematics
Book embedding
Planar straight-line graph
General Mathematics
Graph theory
Computer Science::Computational Geometry
1-planar graph
Geometric graph theory
law.invention
Planar graph
Combinatorics
symbols.namesake
law
Graph drawing
Outerplanar graph
Line graph
Graph minor
symbols
Nested triangles graph
Polyhedral graph
Mathematics
Subjects
Details
- Database :
- OpenAIRE
- Journal :
- Scopus-Elsevier, STOC
- Accession number :
- edsair.doi.dedup.....a5844c984beabf773eb8530d7026968f