A Simple Partially Embedded Planarity Test Based on Vertex-Addition

Abstract

In the Partially Embedded Planarity problem, we are given a graph G together with a topological drawing of a subgraph H of G. The task is to decide whether the drawing can be extended to a drawing of the whole graph such that no two edges cross. Angelini et al. gave a linear-time algorithm for solving this problem in 2010 [1,2]. While their paper constitutes a significant result, the algorithm described therein is highly complex: it uses several layers of decompositions according to connectivity of both G and H, its description spans more than 30 pages, and can hardly be considered implementable. We give an independent linear-time algorithm that works along the well-known vertex-addition planarity test by Booth and Lueker [5,6]. We modify the PC-tree as underlying data structure used for representing all planar drawing possibilities in a natural way to also respect the restrictions given by the prescribed drawing of the subgraph H. The testing algorithm and its proof of correctness only require small adaptations from the comparatively much simpler generic planarity test, of which several implementations exist. If the test succeeds, an embedding can be constructed using the same approaches that are used for the generic planarity test.