Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. NP-Completeness Resu ...
Article

NP-Completeness Results for Minimum Planar Spanners

Ulrik Brandes (1), Dagmar Handke (1)
(1) Faculty of Mathematics and Computer Science [Konstanz]
Download article
Open on HAL
Imported on
March 26, 2015
Published on
January 1, 1998
Last modified on
March 31, 2025
Volume 3
vol. 3:1
DOI
10.46298/dmtcs.257
License
https://about.hal.science/hal-authorisation-v1
Indicators
889
Views
655
Downloads

NP-Completeness Results for Minimum Planar Spanners

Ulrik Brandes (1), Dagmar Handke (1)
(1) Faculty of Mathematics and Computer Science [Konstanz]
Abstract
For any fixed parameter t greater or equal to 1, a \emph t-spanner of a graph G is a spanning subgraph in which the distance between every pair of vertices is at most t times their distance in G. A \emph minimum t-spanner is a t-spanner with minimum total edge weight or, in unweighted graphs, minimum number of edges. In this paper, we prove the NP-hardness of finding minimum t-spanners for planar weighted graphs and digraphs if t greater or equal to 3, and for planar unweighted graphs and digraphs if t greater or equal to 5. We thus extend results on that problem to the interesting case where the instances are known to be planar. We also introduce the related problem of finding minimum \emphplanar t-spanners and establish its NP-hardness for similar fixed values of t.
Keywords
English
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
French
  • graph spanners
  • NP-completeness
  • planar graphs
Cited by

Source: OpenCitations

  • Tree Spanners in Planar Graphs

    Lecture notes in computer science

    Authors : Sándor P. Fekete ORCID, Jana Kremer

    Journal reference : Volume , 1998, pp. 298-309

    DOI : 10.1007/10692760_24

  • Approximation of minimum weight spanners for sparse graphs

    Theoretical Computer Science

    Authors : Feodor F. Dragan, Fedor V. Fomin ORCID, Petr A. Golovach ORCID

    Journal reference : Volume 412, 2010, pp. 846-852

    DOI : 10.1016/j.tcs.2010.11.034

  • Additive Spanners for k-Chordal Graphs

    Lecture notes in computer science

    Authors : Victor D. Chepoi ORCID, Feodor F. Dragan, Chenyu Yan ORCID

    Journal reference : Volume , 2003, pp. 96-107

    DOI : 10.1007/3-540-44849-7_16

  • A distance approximating trees

    Discrete Applied Mathematics

    Authors : Vojtech Bálint

    Journal reference : Volume 156, 2008, pp. 2740-2752

    DOI : 10.1016/j.dam.2007.11.012

  • Tree spanners in planar graphs

    Discrete Applied Mathematics

    Authors : Sándor P. Fekete ORCID, Jana Kremer

    Journal reference : Volume 108, 2001, pp. 85-103

    DOI : 10.1016/s0166-218x(00)00226-2

  • Spanners for bounded tree-length graphs

    Theoretical Computer Science

    Authors : Yon Dourisboure, Feodor F. Dragan, Cyril Gavoille ORCID, Chenyu Yan ORCID

    Journal reference : Volume 383, 2007, pp. 34-44

    DOI : 10.1016/j.tcs.2007.03.058

  • An FPT Algorithm for Minimum Additive Spanner Problem

    arXiv (Cornell University)

    Authors : Kobayashi

    Journal reference : Volume , 2019, pp.

    DOI : 10.4230/lipics.stacs.2020.11

  • Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences

    Theoretical Computer Science

    Authors : Feodor F. Dragan, Muad Abu-Ata

    Journal reference : Volume 547, 2014, pp. 1-17

    DOI : 10.1016/j.tcs.2014.06.007

  • Graph spanners: A tutorial review

    arXiv (Cornell University)

    Authors : Reyan Ahmed ORCID, Greg Bodwin ORCID, Faryad Darabi Sahneh ORCID, Keaton Hamm ORCID, Mohammad Javad Latifi Jebelli ORCID, Stephen Kobourov ORCID, Richard Spence ORCID

    Journal reference : Volume 37, 2020, pp. 100253

    DOI : 10.1016/j.cosrev.2020.100253

  • Additive sparse spanners for graphs with bounded length of largest induced cycle

    Theoretical Computer Science

    Authors : Victor D. Chepoi ORCID, Feodor F. Dragan, Chenyu Yan ORCID

    Journal reference : Volume 347, 2005, pp. 54-75

    DOI : 10.1016/j.tcs.2005.05.017
Preview
Loading PDF preview...