 | ||
In graph theory, a planar cover of a finite graph G is a finite covering graph of G that is itself a planar graph. Every graph that can be embedded into the projective plane has a planar cover; an unsolved conjecture of Seiya Negami states that these are the only graphs with planar covers.
Contents
The existence of a planar cover is a minor-closed graph property, and so can be characterized by finitely many forbidden minors, but the exact set of forbidden minors is not known. For the same reason, there exists a polynomial time algorithm for testing whether a given graph has a planar cover, but an explicit description of this algorithm is not known.
Definition
A covering map from one graph C to another graph H may be described by a function f from the vertices of C onto the vertices of H that, for each vertex v of C, gives a bijection between the neighbors of v and the neighbors of f(v). If H is a connected graph, each vertex of H must have the same number of pre-images in C; this number is called the ply of the map, and C is called a covering graph of G. If C and H are both finite, and C is a planar graph, then C is called a planar cover of H.
Examples
The graph of the dodecahedron has a symmetry that maps each vertex to the antipodal vertex. The set of antipodal pairs of vertices and their adjacencies can itself be viewed as a graph, the Petersen graph. The dodecahedron forms a planar cover of this nonplanar graph. As this example shows, not every graph with a planar cover is itself planar. However, when a planar graph covers a non-planar one, the ply must be an even number.
The graph of a k-gonal prism has 2k vertices, and is planar with two k-gon faces and k quadrilateral faces. If k = ab, with a ≥ 2 and b ≥ 3, then it has an a-ply covering map to a b-fonal prism, in which two vertices of the k-prism are mapped to the same vertex of the b-prism if they both belong to the same k-gonal face and the distance from one to the other is a multiple of b. For instance, the dodecagonal prism can form a 2-ply cover of the hexagonal prism, a 3-ply cover of the cube, or a 4-ply cover of the triangular prism. These examples show that a graph may have many different planar covers, and may be the planar cover for many other graphs. Additionally they show that the ply of a planar cover may be arbitrarily large. They are not the only covers involving prisms: for instance, the hexagonal prism can also cover a non-planar graph, the utility graph K3,3, by identifying antipodal pairs of vertices.
Cover-preserving operations
If a graph H has a planar cover, so does every graph minor of H. A minor G of H may be formed by deleting edges and vertices from H, and by contracting edges of H. The covering graph C can be transformed in the same way: for each deleted edge or vertex in H, delete its preimage in C, and for each contracted edge or vertex in H, contract its preimage in C. The result of applying these operations to C is a minor of C that covers G. Since every minor of a planar graph is itself planar, this gives a planar cover of the minor G.
Because the graphs with planar covers are closed under the operation of taking minors, it follows from the Robertson–Seymour theorem that they may be characterized by a finite set of forbidden minors. A graph is a forbidden minor for this property if it has no planar cover, but all of its minors do have planar covers. This characterization can be used to prove the existence of a polynomial time algorithm that tests for the existence of a planar cover, by searching for each of the forbidden minors and returning that a planar cover exists only if this search fails to find any of them. However, because the exact set of forbidden minors for this property is not known, this proof of existence is non-constructive, and does not lead to an explicit description of the set of forbidden minors or of the algorithm based on them.
Another graph operation that preserves the existence of a planar cover is the Y-Δ transform, which replaces any degree-three vertex of a graph H by a triangle connecting its three neighbors. However, the reverse of this transformation, a Δ-Y transform, does not necessarily preserve planar covers.
Additionally, a disjoint union of two graphs that have covers will also have a cover, formed as the disjoint union of the covering graphs. If the two covers have the same ply as each other, then this will also be the ply of their union.
Negami's conjecture
If a graph H has an embedding into the projective plane, then it necessarily has a planar cover, given by the preimage of H in the orientable double cover of the projective plane, which is a sphere. Negami (1986) proved, conversely, that if a connected graph H has a two-ply planar cover then H must have an embedding into the projective plane. The assumption that H is connected is necessary here, because a disjoint union of projective-planar graphs may not itself be projective-planar but will still have a planar cover, the disjoint union of the orientable double covers.
A regular cover of a graph H is one that comes from a group of symmetries of its covering graph: the preimages of each vertex in H are an orbit of the group. Negami (1988) proved that every connected graph with a planar regular cover can be embedded into the projective plane. Based on these two results, he conjectured that in fact every connected graph with a planar cover is projective. As of 2013, this conjecture remains unsolved. It is also known as Negami's "1-2-∞ conjecture", because it can be reformulated as stating that the minimum ply of a planar cover, if it exists, must be either 1 or 2.
Like the graphs with planar covers, the graphs with projective plane embeddings can be characterized by forbidden minors. In this case the exact set of forbidden minors is known: there are 35 of them. 32 of these are connected, and one of these 32 graphs necessarily appears as a minor in any connected non-projective-planar graph. Since Negami made his conjecture, it has been proven that 31 of these 32 forbidden minors either do not have planar covers, or can be reduced by Y-Δ transforms to a simpler graph on this list. The one remaining graph for which this has not yet been done is K1,2,2,2, a seven-vertex apex graph that forms the skeleton of a four-dimensional octahedral pyramid. If K1,2,2,2 could be shown not to have any planar covers, this would complete a proof of the conjecture. On the other hand, if the conjecture is false, K1,2,2,2 would necessarily be its smallest counterexample.
A related conjecture by Michael Fellows, now solved, concerns planar emulators, a generalization of planar covers that maps graph neighborhoods surjectively rather than bijectively. The graphs with planar emulators, like those with planar covers, are closed under minors and Y-Δ transforms. In 1988, independently of Negami, Fellows conjectured that the graphs with planar emulators are exactly the graphs that can be embedded into the projective plane. The conjecture is true for regular emulators, coming from automomorphisms of the underlying covering graph, by a result analogous to the result of Negami (1988) for regular planar covers. However, several of the 32 connected forbidden minors for projective-planar graphs turn out to have planar emulators. Therefore, Fellows' conjecture is false. Finding a full set of forbidden minors for the existence of planar emulators remains an open problem.