  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.
