@inbook {IOPORT.05988769,
    author       = {B{\'\i}lka, Ond\v{r}ej and Jir\'asek, Jozef and Klav{\'\i}k, Pavel and Tancer, Martin and Volec, Jan},
    title        = {On the complexity of planar covering of small graphs.},
    year         = {2011},
    booktitle    = {Graph-theoretic concepts in computer science. 37th international workshop, WG 2011, Tepl\'a Monastery, Czech Republic, June 21--24, 2011. Revised papers},
    isbn         = {978-3-642-25869-5},
    pages        = {83-94},
    publisher    = {Berlin: Springer},
    doi          = {10.1007/978-3-642-25870-1_9},
    abstract     = {Summary: The problem Cover$(H)$ asks whether an input graph $G$ covers a fixed graph $H$ (i.e., whether there exists a homomorphism $G \rightarrow 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. Kratochv{\'\i}l 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.},
    identifier   = {05988769},
}