标题： H-平面性和参数扩展：当调节器全局作用时 显示英文标题

标题： H-Planarity and Parametric Extensions: when Modulators Act Globally

摘要： 我们引入了一种基于修改问题的调制器/目标方案的图分解系列，这些分解能够实现若干算法应用，这些应用在参数上扩展了平面性的算法潜力。 我们方法的核心是一个计算平面H-调制器的多项式时间算法。 给定一个图类H，图G的平面H-调制器是一个集合X \subseteq V(G)，使得X的“躯干”是平面的，并且G - X的所有连通分量都属于H。在这里，X的躯干是从G[X]得到的，如果对于G - X的每个连通分量，我们将其在G[X]上的邻域形成一个团。 我们引入H-平面性作为判断图G是否具有平面H-调制器的问题。 我们证明，如果H是遗传的、CMSO可定义的，并且可以在多项式时间内判定，则H-平面性可以在多项式时间内求解。 此外，我们通过定义H-平面树深度和H-平面树宽的概念，引入了H-平面性的两种参数扩展，这些概念将消除距离和树分解的概念推广到类H。结合这一结果与各种H-调制器问题的现有FPT算法，我们从而得到了针对许多图类H的由H-平面树深度和H-平面树宽参数化的FPT算法。通过结合平面图和有界树宽图的已知算法特性，我们计算H-平面树深度和H-平面树宽的方法导致了多种算法应用。 例如，一旦我们知道给定图具有有界的H-平面树深度或有界的H-平面树宽，我们就可以推导出图着色的加法近似算法和计数（加权）完美匹配的多项式时间算法。 此外，我们为几个问题设计了高效的多项式时间近似方案（EPTAS-es），包括最大独立集。 显示英文摘要

摘要： 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 H-modulators. Given a graph class H, a planar 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 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 H-Planarity as the problem of deciding whether a graph G has a planar H-modulator. We prove that, if H is hereditary, CMSO-definable, and decidable in polynomial time, then H-Planarity is solvable in polynomial time. Further, we introduce two parametric extensions of H-Planarity by defining the notions of H-planar treedepth and H-planar treewidth, which generalize the concepts of elimination distance and tree decompositions to the class H. Combining this result with existing FPT algorithms for various H-modulator problems, we thereby obtain FPT algorithms parameterized by H-planar treedepth and H-planar treewidth for numerous graph classes H. By combining the well-known algorithmic properties of planar graphs and graphs of bounded treewidth, our methods for computing H-planar treedepth and H-planar treewidth lead to a variety of algorithmic applications. For instance, once we know that a given graph has bounded H-planar treedepth or bounded H-planar treewidth, we can derive additive approximation algorithms for graph coloring and polynomial-time algorithms for counting (weighted) perfect matchings. Furthermore, we design Efficient Polynomial-Time Approximation Schemes (EPTAS-es) for several problems, including Maximum Independent Set.