Partially Embedded Planarity

Definition

In Partially Embedded Planarity we are given a prescribed planar drawing of a subgraph and want to know whether this drawing can be planarly extended by adding some further edges.

Formally, the undirected graph \(G=(V,E)\) is accompanied by a prescribed subgraph \(H\) for which a planar embedding \(\mathcal H\) is given. The triplet \((G, H, \mathcal H)\) is often called partially embedded graph (PEG). We call a planar embedding \(\mathcal G\) of \(G\) an extension of the embedding \(\mathcal H\) of \(H\) if the restriction of \(\mathcal G\) to \(H\) coincides with \(\mathcal H\). The problem Partially Embedded Planarity asks whether such an extension exists for a PEG.

Complexity

Angelini et al. (2015) give a linear-time algorithm for testing Partially Embedded Planarity. A simpler linear-time algorithm is given by Fink, Rutter, and T. P. (2023).

Related Problems

The problem can reduced to Clustered Planarity by fixing the embedding of \(\mathcal H\) using wheels and using clusters to fix the endpoints of the edges of \(G\setminus H\) to their vertices and to ensure that these edges are embedded in the correct faces (diss?).

Schaefer gives a reduction to SEFE-2, where \(G\) constitutes the one exclusive graph and the other exclusive graph is obtained by triangulating \(\mathcal H\) (Schaefer 2013, Theorem 6.2.).

References

Angelini, Patrizio, Giuseppe Di Battista, Fabrizio Frati, Vı́t Jelı́nek, Jan Kratochvı́l, Maurizio Patrignani, and Ignaz Rutter. 2015. “Testing Planarity of Partially Embedded Graphs.” ACM Transactions on Algorithms 11 (4): 32:1–42. https://doi.org/10.1145/2629341.

Fink, Simon D., Ignaz Rutter, and Sandhya T. P. 2023. “A Simple Partially Embedded Planarity Test Based on Vertex-Addition.” In To Appear.

Schaefer, Marcus. 2013. “Toward a Theory of Planarity: Hanani-Tutte and Planarity Variants.” Journal of Graph Algorithms and Applications 17 (4): 367–440. https://doi.org/10.7155/jgaa.00298.