Straight line triangle representations

DOI10.1007/978-3-319-03841-4_11zbMATH Open1362.68226arXiv1503.06970OpenAlexW2565444683MaRDI QIDQ517440FDOQ517440

Authors: Nieke Aerts, Stefan Felsner 

Publication date: 23 March 2017

Published in: Discrete \& Computational Geometry, Graph Drawing (Search for Journal in Brave)

Abstract: A straight line triangle representation (SLTR) of a planar graph is a straight line drawing such that all the faces including the outer face have triangular shape. Such a drawing can be viewed as a tiling of a triangle using triangles with the input graph as skeletal structure. In this paper we present a characterization of graphs that have an SLTR. The characterization is based on flat angle assignments, i.e., selections of angles of the graph that have size~$pi$ in the representation. We also provide a second characterization in terms of contact systems of pseudosegments. With the aid of discrete harmonic functions we show that contact systems of pseudosegments that respect certain conditions are stretchable. The stretching procedure is then used to get straight line triangle representations. Since the discrete harmonic function approach is quite flexible it allows further applications, we mention some of them. The drawback of the characterization of SLTRs is that we are not able to effectively check whether a given graph admits a flat angle assignment that fulfills the conditions. Hence it is still open to decide whether the recognition of graphs that admit straight line triangle representation is polynomially tractable.

Full work available at URL: https://arxiv.org/abs/1503.06970

Recommendations

• Straight-line triangle representations via Schnyder labelings
• Discrete Representation of Straight Lines
• Triangles in arrangements of lines
• Triangles and trilinear coordinates
• Straight line representations of planar graphs
• scientific article; zbMATH DE number 1423120
• scientific article; zbMATH DE number 3986067

zbMATH Keywords

planar graphstrianglesdiscrete harmonic functionscontact family of pseudosegmentsstraight line drawings

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62)

Cites Work

• Planar graphs and poset dimension
• Lattice structures from planar graphs
• Dimers, tilings and trees
• Barycentric systems and stretchability
• Title not available (Why is that?)
• Schnyder woods and orthogonal surfaces
• How to Draw a Graph
• Strongly-connected outerplanar graphs with proper touching triangle representations
• On touching triangle graphs
• Straight-line triangle representations via Schnyder labelings
• On Triangle Contact Graphs
• Touching triangle representations for 3-connected planar graphs
• Geodesic embeddings and planar graphs
• Planar minimally rigid graphs and pseudo-triangulations
• Convex drawings of planar graphs and the order dimension of 3-polytopes
• Planar graphs as minimal resolutions of trivariate monomial ideals
• Triangle contact representations and duality
• On the number of planar orientations with prescribed degrees
• Henneberg steps for triangle representations

This page was built for publication: Straight line triangle representations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q517440)