Contracting a planar graph efficiently

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningfagfællebedømt

Dokumenter

  • Holm, Jacob
  • Giuseppe F. Italiano
  • Adam Karczmarz
  • Jakub Łacki
  • Eva Rotenberg
  • Piotr Sankowski

We present a data structure that can maintain a simple planar graph under edge contractions in linear total time. The data structure supports adjacency queries and provides access to neighbor lists in O(1) time. Moreover, it can report all the arising self-loops and parallel edges. By applying the data structure, we can achieve optimal running times for decremental bridge detection, 2-edge connectivity, maximal 3-edge connected components, and the problem of finding a unique perfect matching for a static planar graph. Furthermore, we improve the running times of algorithms for several planar graph problems, including decremental 2-vertex and 3- edge connectivity, and we show that using our data structure in a black-box manner, one obtains conceptually simple optimal algorithms for computing MST and 5-coloring in planar graphs.

OriginalsprogEngelsk
Titel25th European Symposium on Algorithms, ESA 2017
RedaktørerChristian Sohler, Christian Sohler, Kirk Pruhs
Antal sider15
ForlagSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Publikationsdato1 sep. 2017
Artikelnummer50
ISBN (Elektronisk)9783959770491
DOI
StatusUdgivet - 1 sep. 2017
Begivenhed25th European Symposium on Algorithms, ESA 2017 - Vienna, Østrig
Varighed: 4 sep. 20176 sep. 2017

Konference

Konference25th European Symposium on Algorithms, ESA 2017
LandØstrig
ByVienna
Periode04/09/201706/09/2017
NavnLeibniz International Proceedings in Informatics, LIPIcs
Vol/bind87
ISSN1868-8969

Antal downloads er baseret på statistik fra Google Scholar og www.ku.dk


Ingen data tilgængelig

ID: 230343909