1. Contracting planar graphs to contractions of triangulations
- Author
-
Daniël Paulusma, Dimitrios M. Thilikos, and Marcin Kamiński
- Subjects
FOS: Computer and information sciences ,Discrete Mathematics (cs.DM) ,Planar straight-line graph ,G.2.1 ,0102 computer and information sciences ,01 natural sciences ,Theoretical Computer Science ,Planar graph ,Combinatorics ,symbols.namesake ,TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY ,Outerplanar graph ,FOS: Mathematics ,Graph minor ,Mathematics - Combinatorics ,Discrete Mathematics and Combinatorics ,0101 mathematics ,Forbidden graph characterization ,Universal graph ,Mathematics ,Dual graph ,Topological minor ,Discrete mathematics ,Contraction ,Book embedding ,010102 general mathematics ,1-planar graph ,Computational Theory and Mathematics ,68R10, 05C85 ,010201 computation theory & mathematics ,symbols ,Combinatorics (math.CO) ,Fixed parameter tractable ,Computer Science - Discrete Mathematics ,MathematicsofComputing_DISCRETEMATHEMATICS - Abstract
For every graph $H$, there exists a polynomial-time algorithm deciding if a planar input graph $G$ can be contracted to~$H$. However, the degree of the polynomial depends on the size of $H$. In this paper, we identify a class of graphs $\cal C$ such that for every $H \in \cal C$, there exists an algorithm deciding in time $f(|V(H)|) \cdot |V(G)|^{\bigO{1}}$ whether a planar graph $G$ can be contracted to~$H$. (The function $f(\cdot)$ does not depend on $G$.) The class $\cal C$ is the closure of planar triangulated graphs under taking of contractions. In fact, we prove that a graph $H \in \cal C$ if and only if there exists a constant $c_H$ such that if the tree-width of a graph is at least $c_H$, it contains $H$ as a contraction. We also provide a characterization of $\cal C$ in terms of minimal forbidden contractions., 11 pages, 3 figues
- Published
- 2011
- Full Text
- View/download PDF