Contracting a Planar Graph Efficiently

DOI10.4230/LIPIcs.ESA.2017.50zbMath1442.68176arXiv1706.10228OpenAlexW2963473090MaRDI QIDQ5111739

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

Publication date: 27 May 2020

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

zbMATH Keywords

algorithmsplanar graphsconnectivitydata structurescoloring

Mathematics Subject Classification ID

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

Related Items (3)

Unnamed Item ⋮ Decremental SPQR-trees for Planar Graphs ⋮ Contracting a Planar Graph Efficiently

Cites Work

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

This page was built for publication: Contracting a Planar Graph Efficiently