Contracting a planar graph efficiently

Research output: Research - peer-reviewArticle in proceedings – Annual report year: 2017

View graph of relations

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.

Original languageEnglish
Title of host publication25th European Symposium on Algorithms, ESA 2017
Volume87
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Publication date1 Sep 2017
Article number50
ISBN (Electronic)9783959770491
DOIs
StatePublished - 1 Sep 2017
Event25th European Symposium on Algorithms (ESA 2017) - Vienna, Austria
Duration: 4 Sep 20176 Sep 2017

Conference

Conference25th European Symposium on Algorithms (ESA 2017)
CountryAustria
CityVienna
Period04/09/201706/09/2017
CitationsWeb of Science® Times Cited: No match on DOI

    Research areas

  • Algorithms, Coloring, Connectivity, Data structures, Planar graphs
Download as:
Download as PDF
Select render style:
APAAuthorCBE/CSEHarvardMLAStandardVancouverShortLong
PDF
Download as HTML
Select render style:
APAAuthorCBE/CSEHarvardMLAStandardVancouverShortLong
HTML
Download as Word
Select render style:
APAAuthorCBE/CSEHarvardMLAStandardVancouverShortLong
Word

ID: 140495563