ℋ-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.