fbpx
Wikipedia

Planar cover

April 16, 2024

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 graph C is a planar cover of the graph H. The covering map is indicated by the vertex colors.

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 edit

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 edit

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

Cover-preserving operations edit

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 edit

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]

 
K1,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 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.[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 edit

  1. ^ Hliněný (2010), p. 1
  2. ^ a b c d 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 edit

Secondary sources about Negami's conjecture edit

  • 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, S2CID 121645. 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, vol. 147, Providence, RI: American Mathematical Society, pp. 387–389, doi:10.1090/conm/147/01186, MR 1224718.

Primary sources about planar covers edit

  • 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, arXiv:1107.0176, doi:10.1016/j.aam.2012.06.004, MR 2996383.
  • Hliněný, Petr (1998), "K4,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, arXiv:1007.0373, doi:10.1017/S0963548310000283, MR 2745678, S2CID 9093660.
  • 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 0866945.
  • 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 0949775.
  • 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 K4,5 − 4K2 and K1,2,2,2 and Fellows' conjecture", European Journal of Combinatorics, 31 (3): 903–907, arXiv:0812.3700, doi:10.1016/j.ejc.2009.06.003, MR 2587038, S2CID 36777608.

Supporting literature edit

April 16, 2024
planar, cover, graph, theory, planar, cover, finite, graph, finite, covering, graph, that, itself, planar, graph, every, graph, that, embedded, into, projective, plane, planar, cover, unsolved, conjecture, seiya, negami, states, that, these, only, graphs, with. 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 graph C is a planar cover of the graph H The covering map is indicated by the vertex colors 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 Contents 1 Definition 2 Examples 3 Cover preserving operations 4 Negami s conjecture 5 Notes 6 References 6 1 Secondary sources about Negami s conjecture 6 2 Primary sources about planar covers 6 3 Supporting literatureDefinition editA 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 edit nbsp Identifying pairs of opposite vertices of the dodecahedron gives a covering map to the Petersen graphThe 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 nbsp 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 K3 3 by identifying antipodal pairs of vertices 6 Cover preserving operations editIf 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 D 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 D 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 editUnsolved 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 nbsp K1 2 2 2 the only possible minimal counterexample to Negami s conjectureLike 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 D transforms to a simpler graph on this list 17 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 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 D 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 edit Hlineny 2010 p 1 a b c d Hlineny 2010 Proposition 1 p 2 Hlineny 2010 Definition p 2 Inkmann amp Thomas 2011 This construction is illustrated in Figure 1 where the dodecahedron is shown to be a planar double cover of the Petersen graph Archdeacon amp Richter 1990 Negami 2003 Zelinka 1982 Robertson amp Seymour 2004 Robertson amp Seymour 1995 Fellows amp Langston 1988 Fellows amp 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 Negami 1986 Hlineny 2010 Theorem 2 p 2 For instance the two Kuratowski graphs are projective planar but any union of two of them is not Archdeacon 1981 Negami 1988 Hlineny 2010 Theorem 3 p 3 Negami 1988 Hlineny 2010 Conjecture 4 p 4 Chimani et al 2013 Huneke 1993 Hlineny 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 amp Wang 1979 Negami 1988 Huneke 1993 Hlineny 1998 Archdeacon 2002 Hlineny 2010 pp 4 6 Hlineny 2010 pp 6 9 Fellows 1985 Kitakubo 1991 Hlineny 2010 Definition p 9 Hlineny 2010 Proposition 13 p 9 Hlineny credits this to Fellows and writes that its proof is nontrivial Hlineny 2010 Conjecture 14 p 9 Kitakubo 1991 Hlineny 2010 pp 9 10 Rieck amp Yamashita 2010 Chimani et al 2013 Hlineny 2010 p 10References editSecondary sources about Negami s conjecture edit Hlineny 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 S2CID 121645 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 vol 147 Providence RI American Mathematical Society pp 387 389 doi 10 1090 conm 147 01186 MR 1224718 Primary sources about planar covers edit 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 Hlineny Petr Klusacek Matej 2013 How not to characterize planar emulable graphs Advances in Applied Mathematics 50 1 46 68 arXiv 1107 0176 doi 10 1016 j aam 2012 06 004 MR 2996383 Hlineny Petr 1998 K4 4 e has no finite planar cover Journal of Graph Theory 27 1 51 60 doi 10 1002 SICI 1097 0118 199801 27 1 lt 51 AID JGT8 gt 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 arXiv 1007 0373 doi 10 1017 S0963548310000283 MR 2745678 S2CID 9093660 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 0866945 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 0949775 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 K4 5 4K2 and K1 2 2 2 and Fellows conjecture European Journal of Combinatorics 31 3 903 907 arXiv 0812 3700 doi 10 1016 j ejc 2009 06 003 MR 2587038 S2CID 36777608 Supporting literature edit Archdeacon Dan 1981 A Kuratowski theorem for the projective plane Journal of Graph Theory 5 3 243 246 doi 10 1002 jgt 3190050305 MR 0625065 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 S2CID 3976355 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 S2CID 16587284 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 0554298 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 0648219 Retrieved from https en wikipedia org w index php title Planar cover amp oldid 1170302645, wikipedia, wiki, book, books, library,

article

, read, download, free, free download, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, picture, music, song, movie, book, game, games.