Contracting a planar graph efficiently

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

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

Publication date: 27 May 2020

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.

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

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 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)

Cites Work

• Paths, Trees, and Flowers
• Dynamic Perfect Hashing: Upper and Lower Bounds
• Title not available (Why is that?)
• Unique maximum matching algorithms
• Title not available (Why is that?)
• The minimum spanning tree problem on a planar graph
• Two linear time algorithms for MST on minor closed graph classes.
• Optimal Decremental Connectivity in Planar Graphs.
• Title not available (Why is that?)
• Planar separators and parallel polygon triangulation.
• On linear-time algorithms for five-coloring planar graphs
• Structured recursive separator decompositions for planar graphs in linear time
• Efficient Union-Find for planar graphs and other sparse graph classes
• Contracting a Planar Graph Efficiently
• Faster Algorithms for Computing Maximal 2-Connected Subgraphs in Sparse Directed Graphs
• Multiple-Source Single-Sink Maximum Flow in Directed Planar Graphs in O(diameter · n log n) Time
• Decremental 2- and 3-connectivity on planar graphs
• Multiway Simple Cycle Separators and I/O-Efficient Algorithms for Planar Graphs

Cited In (6)

• On planar perfectly contractile graphs
• Title not available (Why is that?)
• Decremental SPQR-trees for Planar Graphs
• Good \(r\)-divisions imply optimal amortized decremental biconnectivity
• Contracting a Planar Graph Efficiently
• 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)