Google Research

Contracting a Planar Graph Efficiently

  • Adam Karczmarz
  • Eva Rotenberg
  • Giuseppe F. Italiano
  • Jacob Holm
  • Jakub Łącki
  • Piotr Sankowski
ESA (2017)


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.

Learn more about how we do research

We maintain a portfolio of research projects, providing individuals and teams the freedom to emphasize specific types of work