Planar cover

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

Contents

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 Dodecahedron.png
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. Dodecagonal prism.png
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

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]

K1,2,2,2, the only possible minimal counterexample to Negami's conjecture Octahedral pyramid.png
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

  1. ↑ Hliněný (2010), p. 1
  2. 1 2 3 4 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

Related Research Articles

In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a plane graph or planar embedding of the graph. A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points.

Petersen graph Cubic graph with 10 vertices and 15 edges

In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named after Julius Petersen, who in 1898 constructed it to be the smallest bridgeless cubic graph with no three-edge-coloring.

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

In graph theory, the Robertson–Seymour theorem states that the undirected graphs, partially ordered by the graph minor relationship, form a well-quasi-ordering. Equivalently, every family of graphs that is closed under minors can be defined by a finite set of forbidden minors, in the same way that Wagner's theorem characterizes the planar graphs as being the graphs that do not have the complete graph K5 or the complete bipartite graph K3,3 as minors.

In graph theory, an undirected graph H is called a minor of the graph G if H can be formed from G by deleting edges and vertices and by contracting edges.

In topological graph theory, a mathematical discipline, a linkless embedding of an undirected graph is an embedding of the graph into three-dimensional Euclidean space in such a way that no two cycles of the graph are linked. A flat embedding is an embedding with the property that every cycle is the boundary of a topological disk whose interior is disjoint from the graph. A linklessly embeddable graph is a graph that has a linkless or flat embedding; these graphs form a three-dimensional analogue of the planar graphs. Complementarily, an intrinsically linked graph is a graph that does not have a linkless embedding.

Hadwiger conjecture (graph theory)

In graph theory, the Hadwiger conjecture states that if G is loopless and has no minor then its chromatic number satisfies . It is known to be true for . The conjecture is a generalization of the four-color theorem and is considered to be one of the most important and challenging open problems in the field.

The arboricity of an undirected graph is the minimum number of forests into which its edges can be partitioned. Equivalently it is the minimum number of spanning forests needed to cover all the edges of the graph. The Nash-Williams theorem provides necessary and sufficient conditions for when a graph is k-arboric.

Dual graph

In the mathematical discipline of graph theory, the dual graph of a plane graph G is a graph that has a vertex for each face of G. The dual graph has an edge for each pair of faces in G that are separated from each other by an edge, and a self-loop when the same face appears on both sides of an edge. Thus, each edge e of G has a corresponding dual edge, whose endpoints are the dual vertices corresponding to the faces on either side of e. The definition of the dual depends on the choice of embedding of the graph G, so it is a property of plane graphs rather than planar graphs. For planar graphs generally, there may be multiple dual graphs, depending on the choice of planar embedding of the graph.

Colin de Verdière's invariant is a graph parameter for any graph G, introduced by Yves Colin de Verdière in 1990. It was motivated by the study of the maximum multiplicity of the second eigenvalue of certain Schrödinger operators.

Wagners theorem Characterization theorem in graph theory of planar graphs

In graph theory, Wagner's theorem is a mathematical forbidden graph characterization of planar graphs, named after Klaus Wagner, stating that a finite graph is planar if and only if its minors include neither K5 nor K3,3. This was one of the earliest results in the theory of graph minors and can be seen as a forerunner of the Robertson–Seymour theorem.

Cactus graph

In graph theory, a cactus is a connected graph in which any two simple cycles have at most one vertex in common. Equivalently, it is a connected graph in which every edge belongs to at most one simple cycle, or in which every block is an edge or a cycle.

Circle packing theorem Describes the possible tangency relations between circles with disjoint interiors

The circle packing theorem describes the possible tangency relations between circles in the plane whose interiors are disjoint. A circle packing is a connected collection of circles whose interiors are disjoint. The intersection graph of a circle packing is the graph having a vertex for each circle, and an edge for every pair of circles that are tangent. If the circle packing is on the plane, or, equivalently, on the sphere, then its intersection graph is called a coin graph; more generally, intersection graphs of interior-disjoint geometric objects are called tangency graphs or contact graphs. Coin graphs are always connected, simple, and planar. The circle packing theorem states that these are the only requirements for a graph to be a coin graph:

In the mathematical discipline of graph theory, a graph C is a covering graph of another graph G if there is a covering map from the vertex set of C to the vertex set of G. A covering map f is a surjection and a local isomorphism: the neighbourhood of a vertex v in C is mapped bijectively onto the neighbourhood of f(v) in G.

In mathematics, the graph structure theorem is a major result in the area of graph theory. The result establishes a deep and fundamental connection between the theory of graph minors and topological embeddings. The theorem is stated in the seventeenth of a series of 23 papers by Neil Robertson and Paul Seymour. Its proof is very long and involved. Kawarabayashi & Mohar (2007) and Lovász (2006) are surveys accessible to nonspecialists, describing the theorem and its consequences.

Herschel graph

In graph theory, a branch of mathematics, the Herschel graph is a bipartite undirected graph with 11 vertices and 18 edges, the smallest non-Hamiltonian polyhedral graph. It is named after British astronomer Alexander Stewart Herschel.

Apex graph

In graph theory, a branch of mathematics, an apex graph is a graph that can be made planar by the removal of a single vertex. The deleted vertex is called an apex of the graph. It is an apex, not the apex because an apex graph may have more than one apex; for example, in the minimal nonplanar graphs K5 or K3,3, every vertex is an apex. The apex graphs include graphs that are themselves planar, in which case again every vertex is an apex. The null graph is also counted as an apex graph even though it has no vertex to remove.

Apollonian network

In combinatorial mathematics, an Apollonian network is an undirected graph formed by a process of recursively subdividing a triangle into three smaller triangles. Apollonian networks may equivalently be defined as the planar 3-trees, the maximal planar chordal graphs, the uniquely 4-colorable planar graphs, and the graphs of stacked polytopes. They are named after Apollonius of Perga, who studied a related circle-packing construction.

Octahedral pyramid

In 4-dimensional geometry, the octahedral pyramid is bounded by one octahedron on the base and 8 triangular pyramid cells which meet at the apex. Since an octahedron has a circumradius divided by edge length less than one, the triangular pyramids can be made with regular faces by computing the appropriate height.

<i>k</i>-outerplanar graph

In graph theory, a k-outerplanar graph is a planar graph that has a planar embedding in which the vertices belong to at most concentric layers. The outerplanarity index of a planar graph is the minimum value of for which it is -outerplanar.

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

Primary sources about planar covers

Supporting literature

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.