Drawing Graphs as Spanners

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

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference paperpeer-review


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.

Original languageEnglish
Title of host publicationGraph-Theoretic Concepts in Computer Science - 46th International Workshop, WG 2020, Revised Selected Papers
EditorsIsolde Adler, Haiko Müller
Place of PublicationLeeds, United Kingdom
PublisherSpringer International Publishing AG
Number of pages15
ISBN (Print)9783030604394
Publication statusE-pub ahead of print - 9 Oct 2020
Event46th International Workshop on Graph-Theoretic Concepts in Computer Science: WG 2020 - Virtuell, Leeds, United Kingdom
Duration: 24 Jun 202026 Jun 2020

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12301 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference46th International Workshop on Graph-Theoretic Concepts in Computer Science
Country/TerritoryUnited Kingdom
CityVirtuell, Leeds

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fields of Expertise

  • Information, Communication & Computing


Dive into the research topics of 'Drawing Graphs as Spanners'. Together they form a unique fingerprint.

Cite this