Contracting planar graphs to contractions of triangulations

Details Contracting planar graphs to contractions of triangulations Contracting planar graphs to contractions of triangulations

2010-12-11

arxiv.org/abs/1012.2460v1

Mathematics

Combinatorics

11 pages, 3 figues

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Contracting planar graphs to contractions of triangulations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Contracting planar graphs to contractions of triangulations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Contracting planar graphs to contractions of triangulations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-105696