Planar cover

The graph C is a planar cover of the graph H. The covering map is indicated by the vertex colors.

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.^[1]

The existence of a planar cover is a minor-closed graph property,^[2] 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).^[3] If H is a connected graph, each vertex of H must have the same number of pre-images in C;^[2] 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

Identifying pairs of opposite vertices of the dodecahedron gives a covering map to the Petersen graph

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.^[4] 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.^[5]

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.

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 K_3,3, by identifying antipodal pairs of vertices.^[6]

Cover-preserving operations

If a graph H has a planar cover, so does every graph minor of H.^[2] 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.^[7] 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.^[8] 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.^[9]

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.^[2] 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

Unsolved problem in mathematics: Does every connected graph with a planar cover have an embedding into the projective plane? (more unsolved problems in mathematics)

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.^[10] The assumption that H is connected is necessary here, because a disjoint union of projective-planar graphs may not itself be projective-planar^[11] 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.^[12] Based on these two results, he conjectured that in fact every connected graph with a planar cover is projective.^[13] As of 2013, this conjecture remains unsolved.^[14] 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.^[15]

K_1,2,2,2, the only possible minimal counterexample to Negami's conjecture

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.^[16] 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.^[17] The one remaining graph for which this has not yet been done is K_1,2,2,2, a seven-vertex apex graph that forms the skeleton of a four-dimensional octahedral pyramid. If K_1,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, K_1,2,2,2 would necessarily be its smallest counterexample.^[18]

A related conjecture by Michael Fellows, now solved, concerns planar emulators, a generalization of planar covers that maps graph neighborhoods surjectively rather than bijectively.^[19] The graphs with planar emulators, like those with planar covers, are closed under minors and Y-Δ transforms.^[20] 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.^[21] 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.^[22] However, several of the 32 connected forbidden minors for projective-planar graphs turn out to have planar emulators.^[23] Therefore, Fellows' conjecture is false. Finding a full set of forbidden minors for the existence of planar emulators remains an open problem.^[24]

Notes

1. Hliněný (2010), p. 1
2. Hliněný (2010), Proposition 1, p. 2
3. Hliněný (2010), Definition, p. 2
4. Inkmann & Thomas (2011): "This construction is illustrated in Figure 1, where the dodecahedron is shown to be a planar double cover of the Petersen graph."
5. Archdeacon & Richter (1990); Negami (2003).
6. Zelinka (1982)
7. Robertson & Seymour (2004)
8. Robertson & Seymour (1995)
9. Fellows & Langston (1988); Fellows & Koblitz (1992). The non-constructivity of algorithmically testing the existence of k-fold planar covers is given explicitly as an example by Fellows and Koblitz.
10. Negami (1986); Hliněný (2010), Theorem 2, p. 2
11. For instance, the two Kuratowski graphs are projective-planar but any union of two of them is not (Archdeacon 1981).
12. Negami (1988); Hliněný (2010), Theorem 3, p. 3
13. Negami (1988); Hliněný (2010), Conjecture 4, p. 4
14. Chimani et al. (2013)
15. Huneke (1993)
16. Hliněný (2010), p. 4; the list of forbidden projective-planar minors is from Archdeacon (1981). Negami (1988) instead stated the corresponding observation for the 103 irreducible non-projective-planar graphs given by Glover, Huneke & Wang (1979).
17. Negami (1988); Huneke (1993); Hliněný (1998); Archdeacon (2002); Hliněný (2010), pp. 4–6
18. Hliněný (2010), pp. 6–9
19. Fellows (1985); Kitakubo (1991); Hliněný (2010), Definition, p. 9
20. Hliněný (2010), Proposition 13, p. 9. Hliněný credits this to Fellows and writes that its proof is nontrivial.
21. Hliněný (2010), Conjecture 14, p. 9
22. Kitakubo (1991).
23. Hliněný (2010), pp. 9–10; Rieck & Yamashita (2010); Chimani et al. (2013)
24. Hliněný (2010), p. 10

References

Secondary sources about Negami's conjecture

• Hliněný, Petr (2010), "20 years of Negami's planar cover conjecture" (PDF), Graphs and Combinatorics 26 (4): 525–536, doi:10.1007/s00373-010-0934-9, MR 2669457. Page numbers in notes refer to the preprint version.
• Huneke, John Philip (1993), "A conjecture in topological graph theory", Graph Structure Theory (Seattle, WA, 1991), Contemporary Mathematics 147, Providence, RI: American Mathematical Society, pp. 387–389, doi:10.1090/conm/147/01186, MR 1224718.

Primary sources about planar covers

• Archdeacon, Dan (2002), "Two graphs without planar covers", Journal of Graph Theory 41 (4): 318–326, doi:10.1002/jgt.10075, MR 1936947.
• Archdeacon, Dan; Richter, R. Bruce (1990), "On the parity of planar covers", Journal of Graph Theory 14 (2): 199–204, doi:10.1002/jgt.3190140208, MR 1053603.
• Chimani, Markus; Derka, Martin; Hliněný, Petr; Klusáček, Matěj (2013), "How not to characterize planar-emulable graphs", Advances in Applied Mathematics 50 (1): 46–68, doi:10.1016/j.aam.2012.06.004, MR 2996383.
• Hliněný, Petr (1998), "K_4,4 − e has no finite planar cover", Journal of Graph Theory 27 (1): 51–60, doi:10.1002/(SICI)1097-0118(199801)27:1<51::AID-JGT8>3.3.CO;2-S, MR 1487786.
• Inkmann, Torsten; Thomas, Robin (2011), "Minor-minimal planar graphs of even branch-width", Combinatorics, Probability and Computing 20 (1): 73–82, doi:10.1017/S0963548310000283, MR 2745678.
• Kitakubo, Shigeru (1991), "Planar branched coverings of graphs", Yokohama Mathematical Journal 38 (2): 113–120, MR 1105068.
• Negami, Seiya (1986), "Enumeration of projective-planar embeddings of graphs", Discrete Mathematics 62 (3): 299–306, doi:10.1016/0012-365X(86)90217-7, MR 866945.
• Negami, Seiya (1988), "The spherical genus and virtually planar graphs", Discrete Mathematics 70 (2): 159–168, doi:10.1016/0012-365X(88)90090-8, MR 949775.
• Negami, Seiya (2003), "Composite planar coverings of graphs", Discrete Mathematics 268 (1-3): 207–216, doi:10.1016/S0012-365X(02)00689-1, MR 1983279.
• Rieck, Yo'av; Yamashita, Yasushi (2010), "Finite planar emulators for K_4,5 − 4K₂ and K_1,2,2,2 and Fellows' conjecture", European Journal of Combinatorics 31 (3): 903–907, doi:10.1016/j.ejc.2009.06.003, MR 2587038.

Supporting literature

• Archdeacon, Dan (1981), "A Kuratowski theorem for the projective plane", Journal of Graph Theory 5 (3): 243–246, doi:10.1002/jgt.3190050305, MR 625065
• Fellows, Michael R. (1985), Encoding Graphs in Graphs, Ph.D. thesis, Univ. of California, San Diego.
• Fellows, Michael R.; Koblitz, Neal (1992), "Self-witnessing polynomial-time complexity and prime factorization", Designs, Codes and Cryptography 2 (3): 231–235, doi:10.1007/BF00141967, MR 1181730.
• Fellows, Michael R.; Langston, Michael A. (1988), "Nonconstructive tools for proving polynomial-time decidability", Journal of the ACM 35 (3): 727–739, doi:10.1145/44483.44491.
• Glover, Henry H.; Huneke, John P.; Wang, Chin San (1979), "103 graphs that are irreducible for the projective plane", Journal of Combinatorial Theory, Series B 27 (3): 332–370, doi:10.1016/0095-8956(79)90022-4, MR 554298.
• Robertson, Neil; Seymour, Paul (1995), "Graph Minors. XIII. The disjoint paths problem", Journal of Combinatorial Theory, Series B 63 (1): 65–110, doi:10.1006/jctb.1995.1006.
• Robertson, Neil; Seymour, Paul (2004), "Graph Minors. XX. Wagner's conjecture", Journal of Combinatorial Theory, Series B 92 (2): 325–357, doi:10.1016/j.jctb.2004.08.001.
• Zelinka, Bohdan (1982), "On double covers of graphs", Mathematica Slovaca 32 (1): 49–54, MR 648219.