Contracting a planar graph efficiently

DOI10.4230/LIPICS.ESA.2017.50zbMATH Open1442.68176OpenAlexW2963473090MaRDI QIDQ5111739FDOQ5111739

Authors Jacob Holm, Giuseppe F. Italiano, Adam Karczmarz, Jakub Łącki, Eva Rotenberg, Piotr Sankowski 

Publication date 27 May 2020

Full work available at URL https://arxiv.org/abs/1706.10228

zbMATH Keywords

algorithmsdata structuresconnectivityplanar graphscoloring

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Data structures (68P05) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Connectivity (05C40)

Abstract: 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.

Recommendations

• Optimal decremental connectivity in planar graphs
• Optimal decremental connectivity in planar graphs
• Decremental 2- and 3-connectivity on planar graphs
• Data structures for two-edge connectivity in planar graphs
• scientific article; zbMATH DE number 176746

Cites work

• scientific article; zbMATH DE number 2185626 (Why is no real title available?)
• scientific article; zbMATH DE number 437525 (Why is no real title available?)
• scientific article; zbMATH DE number 1256776 (Why is no real title available?)
• Contracting a planar graph efficiently
• Decremental 2- and 3-connectivity on planar graphs
• Dynamic Perfect Hashing: Upper and Lower Bounds
• Efficient Union-Find for planar graphs and other sparse graph classes
• Faster algorithms for computing maximal 2-connected subgraphs in sparse directed graphs
• Multiple-source single-sink maximum flow in directed planar graphs in \(O(\mathrm{diameter} \cdot n \log n)\) time
• Multiway simple cycle separators and I/O-efficient algorithms for planar graphs
• On linear-time algorithms for five-coloring planar graphs
• Optimal decremental connectivity in planar graphs
• Paths, Trees, and Flowers
• Planar separators and parallel polygon triangulation.
• Structured recursive separator decompositions for planar graphs in linear time
• The minimum spanning tree problem on a planar graph
• Two linear time algorithms for MST on minor closed graph classes.
• Unique maximum matching algorithms

Cited in

(6)

• Decremental SPQR-trees for Planar Graphs
• scientific article; zbMATH DE number 7378710 (Why is no real title available?)
• Contracting a planar graph efficiently
• On planar perfectly contractile graphs
• Good \(r\)-divisions imply optimal amortized decremental biconnectivity
• Contractions of Planar Graphs in Polynomial Time

This page was built for publication: Contracting a planar graph efficiently

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111739)