TY - GEN

T1 - Drawing Graphs as Spanners

AU - Aichholzer, Oswin

AU - Borrazzo, Manuel

AU - Bose, Prosenjit

AU - Cardinal, Jean

AU - Frati, Fabrizio

AU - Morin, Pat

AU - Vogtenhuber, Birgit

PY - 2020/10/9

Y1 - 2020/10/9

N2 - 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 Γ 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 Γ. 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, ∃ R-complete, and linear-time solvable problems, respectively. Second, we prove that, for every ϵ> 0, every (planar) graph admits a proper (resp. planar) straight-line drawing with spanning ratio smaller than 1 + ϵ. Third, we note that our drawings with spanning ratio smaller than 1 + ϵ have large edge-length ratio, that is, the ratio between the lengths of the longest and 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 do not.

AB - 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 Γ 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 Γ. 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, ∃ R-complete, and linear-time solvable problems, respectively. Second, we prove that, for every ϵ> 0, every (planar) graph admits a proper (resp. planar) straight-line drawing with spanning ratio smaller than 1 + ϵ. Third, we note that our drawings with spanning ratio smaller than 1 + ϵ have large edge-length ratio, that is, the ratio between the lengths of the longest and 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 do not.

UR - https://arxiv.org/abs/2002.05580

UR - http://www.scopus.com/inward/record.url?scp=85093830836&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-60440-0_25

DO - 10.1007/978-3-030-60440-0_25

M3 - Conference paper

SN - 9783030604394

VL - 12301

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 310

EP - 324

BT - Graph-Theoretic Concepts in Computer Science - 46th International Workshop, WG 2020, Revised Selected Papers

A2 - Adler, Isolde

A2 - Müller, Haiko

PB - Springer International Publishing AG

CY - Leeds, United Kingdom

T2 - 46th International Workshop on Graph-Theoretic Concepts in Computer Science

Y2 - 24 June 2020 through 26 June 2020

ER -