Drawing graphs as spanners

DOI10.1007/S00454-022-00398-5MaRDI QIDQ5918794zbMATH OpenOpenAlexFDO

Authors Oswin Aichholzer, Manuel Borrazzo, Prosenjit Bose, Jean Cardinal, Fabrizio Frati, Pat Morin, Birgit Vogtenhuber

Publication date 16 September 2022

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

canonical orderingedge-length ratiogeometric spannerplanar graphtoughness

Mathematics Subject Classification ID

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

Abstract: We study the problem of embedding graphs in the plane as good geometric spanners. That is, for a graph $G$, the goal is to construct a straight-line drawing $Gamma$ of $G$ in the plane such that, for any two vertices $u$ and $v$ of $G$, the ratio between the minimum length of any path from $u$ to $v$ and the Euclidean distance between $u$ and $v$ is small. The maximum such ratio, over all pairs of vertices of $G$, is the spanning ratio of $Gamma$. First, we show that deciding whether a graph admits a straight-line drawing with spanning ratio $1$, a proper straight-line drawing with spanning ratio $1$, and a planar straight-line drawing with spanning ratio $1$ are NP-complete, $existsmathbbR$-complete, and linear-time solvable problems, respectively, where a drawing is proper if no two vertices overlap and no edge overlaps a vertex. Second, we show that moving from spanning ratio $1$ to spanning ratio $1+epsilon$ allows us to draw every graph. Namely, we prove that, for every $epsilon>0$, every (planar) graph admits a proper (resp. planar) straight-line drawing with spanning ratio smaller than $1+epsilon$. Third, our drawings with spanning ratio smaller than $1+epsilon$ have large edge-length ratio, that is, the ratio between the length of the longest edge and the length of the shortest edge is exponential. We show that this is sometimes unavoidable. More generally, we identify having bounded toughness as the criterion that distinguishes graphs that admit straight-line drawings with constant spanning ratio and polynomial edge-length ratio from graphs that require exponential edge-length ratio in any straight-line drawing with constant spanning ratio.

Recommendations

• On the planar edge-length ratio of planar graphs
• A note on minimum-segment drawings of planar graphs
• On Spanners of Geometric Graphs

Cites work

• Almost all Delaunay triangulations have stretch factor greater than \(\pi /2\)
• An algorithm for straight-line drawing of planar graphs
• An Algorithm to Construct Greedy Drawings of Triangulations
• Competitive routing in the half-\(\theta_6\)-graph
• Complexity of some geometric and topological problems
• Construction and Local Routing for Angle-Monotone Graphs
• Convex drawings of 3-connected plane graphs
• Curves with increasing chords
• Delaunay graphs are almost as good as complete graphs
• Drawing a tree as a minimum spanning tree approximation
• Drawing planar graphs using the canonical ordering
• Drawings of planar graphs with few slopes and segments
• Euclidean greedy drawings of trees
• Gabriel triangulations and angle-monotone graphs: local routing and recognition
• Good spanning trees in graph drawing
• How to draw a planar graph on a grid
• scientific article; zbMATH DE number 432759 (Why is no real title available?)
• scientific article; zbMATH DE number 4092241 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1433426 (Why is no real title available?)
• Increasing-chord graphs on point sets
• Lower bounds on the dilation of plane spanners
• Monotone drawings of 3-connected plane graphs
• Monotone drawings of graphs
• Monotone drawings of graphs with fixed embedding
• More canonical ordering
• On a conjecture related to geometric routing
• On a connection between the existence of k-trees and the toughness of a graph
• On monotone drawings of trees
• On planar greedy drawings of 3-connected planar graphs
• On plane geometric spanners: a survey and open problems
• On self-approaching and increasing-chord drawings of 3-connected planar graphs
• On succinct greedy drawings of plane triangulations and 3-connected plane graphs
• On the area requirements of Euclidean minimum spanning trees
• On the maximal number of edges of convex digital polygons included into an m m-grid
• Optimal monotone drawings of trees
• Orderly spanning trees with applications to graph encoding and graph drawing
• Polynomial area bounds for MST embeddings of trees
• Recognition and complexity of point visibility graphs
• Self-approaching curves
• Self-approaching graphs
• Some results on greedy embeddings in metric spaces
• Strongly monotone drawings of planar graphs
• Succinct greedy drawings do not always exist
• Succinct Greedy Geometric Routing Using Hyperbolic Geometry
• Succinct strictly convex greedy drawing of 3-connected plane graphs
• The art gallery problem is \(\exists \mathbb{R}\)-complete
• The Planar Hamiltonian Circuit Problem is NP-Complete
• The stretch factor of the Delaunay triangulation is less than 1.998
• There are planar graphs almost as good as the complete graph
• Tough graphs and Hamiltonian circuits.
• Toughness in graphs -- a survey
• Transitions in geometric minimum spanning trees
• Universality considerations in VLSI circuits

Cited in

(5)

• On the edge-length ratio of planar graphs
• Emanation graph: a plane geometric spanner with Steiner points
• Graph spanners
• On edge-length ratios of partial 2-trees
• On the planar edge-length ratio of planar graphs

This page was built for publication: Drawing graphs as spanners

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