\(\mathcal{H}\)-Planarity and Parametric Extensions: when Modulators Act Globally

We introduce a series of graph decompositions based on the modulator/target scheme of modification problems that enable several algorithmic applications that parametrically extend the algorithmic potential of planarity. In the core of our approach is a polynomial time algorithm for computing planar \(\mathcal{H}\)-modulators. Given a graph class \(\mathcal{H}\), a planar \(\mathcal{H}\)-modulator of a graph \(G\) is a set \(X \subseteq V(G)\) such that the “torso” of \(X\) is planar and all connected components of \(G-X\) belong to \(\mathcal{H}\). Here, the torso of \(X\) is obtained from \(G[X]\) if, for every connected component of \(G-X\), we form a clique out of its neighborhood on \(G[X]\). We introduce \(\mathcal{H}\)-Planarity as the problem of deciding whether a graph \(G\) has a planar \(\mathcal{H}\)-modulator. We prove that, if \(\mathcal{H}\) is hereditary, CMS0-definable, and decidable in polynomial time, then \(\mathcal{H}\)-Planarity is solvable in polynomial time.