Mathematics – Combinatorics
Scientific paper
2011-07-30
Mathematics
Combinatorics
Full version (including Appendix) of a paper from the conference WG 2011
Scientific paper
The problem Cover(H) asks whether an input graph G covers a fixed graph H (i.e., whether there exists a homomorphism G to H which locally preserves the structure of the graphs). Complexity of this problem has been intensively studied. In this paper, we consider the problem PlanarCover(H) which restricts the input graph G to be planar. PlanarCover(H) is polynomially solvable if Cover(H) belongs to P, and it is even trivially solvable if H has no planar cover. Thus the interesting cases are when H admits a planar cover, but Cover(H) is NP-complete. This also relates the problem to the long-standing Negami Conjecture which aims to describe all graphs having a planar cover. Kratochvil asked whether there are non-trivial graphs for which Cover(H) is NP-complete but PlanarCover(H) belongs to P. We examine the first nontrivial cases of graphs H for which Cover(H) is NP-complete and which admit a planar cover. We prove NP-completeness of PlanarCover(H) in these cases.
Bílka Ondřej
Jirásek Jozef
Klavík Pavel
Tancer Martin
Volec Jan
No associations
LandOfFree
On the Complexity of Planar Covering of Small Graphs 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 On the Complexity of Planar Covering of Small Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Complexity of Planar Covering of Small Graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-136137