Undecidability of Winkler′s r-Neighborhood Problem for Covering Digraphs

Consider the following decision problem which P. Winkler and V. Bulitko (independently) showed was undecidable: Given a finite set Φ of rooted graphs and a positive integer r, is there a graph G such that Φ represents, up to isomorphism, the set of all r-neighborhoods of G? We show the undecidability of the related problem in which G is required to be the covering digraph of a partial ordering. Our construction shows that the problem remains undecidable (for certain fixed r) even when G is also required to be planar and bipartite.