Contracting a Planar Graph Efficiently

Adam Karczmarz
Eva Rotenberg
Giuseppe F. Italiano
Jacob Holm
Piotr Sankowski
Google Scholar


We show 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 loops and parallel edges. By applying the data structure, we can improve the running times of algorithms for several planar graph problems, including decremental 2-edge, 2-vertex and 3-edge connectivity. We also show that using our data structure in a black-box manner, one obtains very simple optimal algorithms for computing MST and 5-coloring in planar graphs.