Contracting a Planar Graph Efficiently
Abstract
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.
Research Areas
