Patrick Poon–Theoretical Computer Science Seminar

Testing Planarity of Partially Embedded Graphs

Patrizio Angelini, Giuseppe Di Battista, Fabrizio Frati, Vit Jelinek, Jan Kratochvil, Maurizio Patrignani, and Ignaz Rutter

Presented by Patrick Poon

We study the following problem: Given a planar graph G and a planar drawing (embedding) of a subgraph of G, can such a drawing be extended to a planar drawing of the entire graph G? This problem fits the paradigm of extending a partial solution to a complete one, which has been studied before in many different settings. Unlike many cases, in which the presence of a partial solution in the input makes hard an otherwise easy problem, we show that the planarity question remains polynomial-time solvable. Our algorithm is based on several combinatorial lemmata which show that the planarity of partially embedded graphs meets the “oncas” behaviour – obvious necessary conditions for planarity are also sufficient. These conditions are expressed in terms of the interplay between (a) rotation schemes and containment relationships between cycles and (b) the decomposition of a graph into its connected, biconnected, and triconnected components.