Dual graph

The red graph is the dual graph of the blue 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 whenever two faces of G are separated from each other by an edge. Thus, each edge e of G has a corresponding dual edge, the edge that connects the two faces on either side of e.

Graph duality is a topological generalization of the geometric concepts of dual polyhedra and dual tessellations, and is in turn generalized algebraically by the concept of a dual matroid. Variations of planar graph duality include a version of duality for directed graphs, and duality for graphs embedded onto non-planar two-dimensional surfaces. However, the notion described in this page is different from the edge-to-vertex dual (line graph) of a graph and should not be confused with it.

The term "dual" is used because this property is symmetric, meaning that if H is a dual of G, then G is a dual of H (if G is connected). When discussing the dual of a graph G, the graph G itself may be referred to as the "primal graph". Many other graph properties and structures may be translated into other natural properties and structures of the dual. For instance, cycles are dual to cuts, spanning trees are dual to the complements of spanning trees, and simple graphs (without parallel edges or self-loops) are dual to 3-edge-connected graphs.

Polyhedral graphs, and some other planar graphs, have unique dual graphs. However, for planar graphs more generally, there may be multiple dual graphs, depending on the choice of planar embedding of the graph. Testing whether one planar graph is dual to another is NP-complete.

Examples

The cube and regular octahedron have dual graphs

Dual polyhedra

Main article: Dual polyhedron

Duality of planar graphs is closely connected to the concept of a dual polyhedron: for a three-dimensional polyhedron, the graph of the polyhedron (its set of vertices and edges) is dual to the graph of the dual polyhedron. For this reason the graphs of the Platonic solids come in dual pairs:[1] the graph K2,2,2 of the regular octahedron is dual to the cube graph, etc. The regular tetrahedron is self-dual, so its graph K4 is also.

Polyhedron duality can also be extended to duality of higher dimensional polytopes,[2] but this extension of geometric duality does not have clear connections to graph-theoretic duality.

Self-dual graphs

A self-dual graph. It is 3-edge-connected (dual to being simple) but not 3-vertex-connected.

A plane graph is said to be self-dual if it is isomorphic to its dual graph. The wheel graphs provide an infinite family of self-dual graphs coming from self-dual polyhedra (the pyramids).[3][4] However, there also exist self-dual graphs that are not polyhedral, such as the one shown. Servatius & Christopher (1992) describe two operations, adhesion and explosion, that can be used to construct a self-dual graph containing a given planar graph; for instance, the self-dual graph shown can be constructed as the adhesion of a tetrahedron with its dual.[4]

It follows from Euler's formula that every self-dual graph with n vertices has exactly 2n − 2 edges.[5] Every simple self-dual planar graph contains at least four vertices of degree three, and every self-dual embedding has at least four triangular faces.[6]

Variations

Directed graphs

In a directed plane graph, the dual graph may be made directed as well, by orienting each dual edge by a 90° clockwise turn from the corresponding primal edge.[7] Strictly speaking, this construction is not a duality of directed planar graphs, because starting from a graph G and taking the dual twice does not return to G itself, but instead constructs a graph isomorphic to the transpose graph of G, the graph formed from G by reversing all of its edges. Taking the dual four times returns to the original graph.

Weak dual

The weak dual of a plane graph is the subgraph of the dual graph whose vertices correspond to the bounded faces of the primal graph. A plane graph is outerplanar if and only if its weak dual is a forest, and a plane graph is a Halin graph if and only if its weak dual is biconnected and outerplanar. For any plane graph G, let G+ be the plane multigraph formed by adding a single new vertex v in the unbounded face of G, and connecting v to each vertex of the outer face (multiple times, if a vertex appears multiple times on the boundary of the outer face); then, G is the weak dual of the (plane) dual of G+.[8][9]

Infinite graphs and tessellations

The concept of duality applies as well to infinite graphs embedded in the plane as it does to finite graphs, although care is needed to avoid topological complications such as points of the plane that are neither part of an open region disjoint from the graph nor part of an edge or vertex of the graph. When all faces are bounded regions surrounded by a cycle of the graph, an infinite planar graph embedding can also be viewed as a tessellation of the plane, a covering of the plane by closed disks (the tiles of the tessellation) whose interiors (the faces of the embedding) are disjoint open disks. Planar duality gives rise to the notion of a dual tessellation, a tessellation formed by placing a vertex at the center of each tile and connecting the centers of adjacent tiles.[10]

A Voronoi diagram (red) and Delaunay triangulation (black) of a finite point set (the black points)

The concept of a dual tessellation can also be applied to partitions of the plane into finitely many regions, and is closely related to but not quite the same as planar graph duality in this case. For instance, the Voronoi diagram of a finite set of point sites is a partition of the plane into polygons within which one site is closer than any other; the sites on the convex hull of the input give rise to unbounded polygons, two of whose sides are infinite rays rather than finite line segments. The dual of this diagram is the Delaunay triangulation of the input, a planar graph that connects two sites by an edge whenever there exists a circle that contains those two sites and no other sites. The edges of the convex hull of the input are also edges of the Delaunay triangulation, but they correspond to rays rather than line segments of the Voronoi diagram. This duality between Voronoi diagrams and Delaunay triangulations can be turned into a duality between finite graphs in either of two ways: by adding an artificial vertex at infinity to the Voronoi diagram, to serve as the other endpoint for all of its rays,[11] or by treating the bounded part of the Voronoi diagram as the weak dual of the Delaunay triangulation. Note also that although the Voronoi diagram and Delaunay triangulation are dual, they may not necessarily be embedded in the plane in such a way that each Delaunay edge crosses only the Voronoi edge or ray to which it is dual.

Nonplanar embeddings

K7 is dual to the Heawood graph in the torus
K6 is dual to the Petersen graph in the projective plane

The concept of duality can be extended to graph embeddings on two-dimensional manifolds other than the plane. The definition is the same: there is a dual vertex for each connected component of the complement of the graph in the manifold, and a dual edge for each graph edge connecting the two dual vertices on either side of the edge. In most applications of this concept, it is restricted to embeddings with the property that each face is a topological disk; this constraint generalizes the requirement for planar graphs that the graph be connected. With this constraint, the dual of any surface-embedded graph has a natural embedding on the same surface, such that the dual of the dual is isomorphic to and isomorphically embedded to the original graph. For instance, the complete graph K7 is a toroidal graph: it is not planar but can be embedded in a torus, with each face of the embedding being a triangle. This embedding has the Heawood graph as its dual graph.[12]

The same concept works equally well for non-orientable surfaces. For instance, K6 can be embedded in the projective plane with ten triangular faces as the hemi-icosahedron, whose dual is the Petersen graph embedded as the hemi-dodecahedron.[13]

Even planar graphs may have nonplanar embeddings, with duals derived from those embeddings that differ from their planar duals. For instance, the four Petrie polygons of a cube (hexagons formed by removing two opposite vertices of the cube) form the hexagonal faces of an embedding of the cube in a torus. The dual graph of this embedding has four vertices forming a complete graph K4 with doubled edges. In the torus embedding of this dual graph, the six edges incident to each vertex, in cyclic order around that vertex, cycle twice through the three other vertices.. In contrast to the situation in the plane, this embedding of the cube and its dual is not unique; the cube graph has several other torus embeddings, with different duals.[12]

Many of the equivalences between primal and dual graph properties of planar graphs fail to generalize to nonplanar duals, or require additional care in their generalization.

Properties

Many natural and important concepts in graph theory correspond to other equally natural but different concepts in the dual graph. Because the dual of the dual of a connected plane graph is isomorphic to the primal graph, each of these pairings is bidirectional: if concept X in a planar graph corresponds to concept Y in the dual graph, then concept Y in a planar graph corresponds to concept X in the dual.

Uniqueness

Two red graphs are duals for the blue one, but they are not isomorphic.

Because the dual graph depends on a particular embedding, the dual graph of a planar graph is not unique in the sense that the same planar graph can have non-isomorphic dual graphs.[14] In the picture, the red graphs are not isomorphic because the upper one has a vertex with degree 6 (the outer face).

However, if the graph is 3-connected, then Whitney showed that the embedding, and thus the dual graph, is unique.[15] By Steinitz's theorem, these graphs are exactly the polyhedral graphs, the graphs of convex polyhedra. A planar graph is 3-vertex-connected if and only if its dual graph is 3-vertex-connected. More generally, a planar graph has a unique embedding, and therefore also a unique dual, if and only if it is a subdivision of a 3-vertex-connected planar graph. However, for some planar graphs that are not 3-vertex-connected (such as the complete bipartite graph K2,4) the embedding is not unique, but all embeddings are isomorphic; in this case, correspondingly, all dual graphs are isomorphic.

Because different embeddings may lead to different dual graphs, testing whether one graph is a dual of another (without already knowing their embeddings) is a nontrivial algorithmic problem. For biconnected graphs, it can be solved in polynomial time by using the SPQR trees of the graphs to construct a canonical form for the equivalence relation of having a shared mutual dual. For instance, the two red graphs in the illustration are equivalent according to this relation. However, for planar graphs that are not biconnected, this relation is not an equivalence relation and the problem of testing mutual duality is NP-complete.[16]

Simple graphs versus multigraphs

The dual of a simple graph need not be simple: it may have self-loops (an edge with both endpoints at the same vertex) or multiple edges connecting the same two vertices. As a special case of the cut-cycle duality discussed below, the bridges of a planar graph G are in one-to-one correspondence with the self-loops of the dual graph.[17] For the same reason, a pair of parallel edges in a dual multigraph (that is, a length-2 cycle) corresponds to a 2-edge cutset in the primal graph. Therefore, a planar graph is simple if and only if its dual has no 1- or 2-edge cutsets (that is, it is 3-edge-connected), and the simple planar graphs whose duals are simple are exactly the 3-edge-connected simple planar graphs.[18] This class of graphs includes, but is not the same as, the class of 3-vertex-connected simple planar graphs.

Cuts and cycles

A cutset in an arbitrary connected graph is a subset of edges whose removal disconnects the graph into multiple connected components. A minimal cutset (also called a bond) is a cutset with the property that every proper subset of the cutset is not itself a cut. A minimal cutset necessarily separates its graph into exactly two components, and consists of the set of edges that have one endpoint in each component.[19]

In a connected planar graph G, every simple cycle of G corresponds to a minimal cutset in the dual of G, and vice versa.[20] This can be seen as a form of the Jordan curve theorem: each simple cycle separates the faces of G into the faces in the interior of the cycle and the faces of the exterior of the cycle, and the duals of the cycle edges are exactly the edges that cross from the interior to the exterior.[21] The girth of any planar graph (the size of its smallest cycle) equals the edge connectivity of its dual graph (the size of its smallest cutset).[22]

This duality extends from individual cutsets and cycles to vector spaces defined from them: the cycle space of a planar graph equals the cut space of its dual graph.[23] Thus, the rank of a planar graph (the dimension of its cut space) equals the cyclotomic number of its dual (the dimension of its cycle space) and vice versa.[14] For edge-weighted planar graphs (with sufficiently general weights that no two cycles have the same weight) the minimum-weight cycle basis of the graph is dual to the Gomory–Hu tree of the dual graph. The minimum weight cycle basis is a minimum-weight set of cycles whose symmetric differences form every other cycle in the graph, or in other words a basis of the cycle space. The edges in each of its cycles are dual to the edges of one of the cuts in the Gomory–Hu tree, a collection of nested cuts that together include a minimum cut separating each pair of vertices in the graph. When cycle weights may be tied, the minimum-weight cycle basis may not be unique, but in this case it is still true that the Gomory–Hu tree of the dual graph corresponds to one of the minimum weight cycle bases of the graph.[23]

In directed planar graphs, simple directed cycles are dual to directed cuts (partitions of the vertices into two subsets such that all edges go in one direction, from one subset to the other). Strongly oriented planar graphs (graphs whose underlying undirected graph is connected, and in which every edge belongs to a cycle) are dual to directed acyclic graphs in which no edge belongs to a cycle. To put this another way, the strong orientations of a connected planar graph (assignments of directions to the edges of the graph that result in a strongly connected graph) are dual to acyclic orientations (assignments of directions that produce a directed acyclic graph).[24]

Spanning trees

A simple maze in which the maze walls and the free space between the walls form two interdigitating trees

A spanning tree may be defined as a set of edges that, together with all of the vertices of the graph, forms a connected and acyclic subgraph. But, by cut-cycle duality, if a set S of edges in a planar graph G is acyclic (has no cycles), then the set of edges dual to S has no cuts, from which it follows that the complementary set of dual edges (the duals of the edges that are not in S) forms a connected subgraph. Symmetrically, if S is connected, then the edges dual to the complement of S form an acyclic subgraph. Therefore, when S has both properties – it is connected and acyclic – the same is true for the complementary set in the dual graph. That is, each spanning tree of G is complementary to a spanning tree of the dual graph, and vice versa. In particular, the minimum spanning tree of G is complementary to the maximum spanning tree of the dual graph.[25]

Thus, the edges of any planar graph and its dual can together be partitioned (in multiple different ways) into two spanning trees, one in the primal and one in the dual, that together extend to all the vertices and faces of the graph but never cross each other. An example of this type of decomposition into interdigitating trees can be seen in some simple types of maze, with a single entrance and no disconnected components of walls; in this case both the maze walls and the space between the walls take the form of a mathematical tree. If the free space of the maze is partitioned into simple cells (such as the squares of a grid) then this system of cells can be viewed as an embedding of a planar graph, in which the tree structure of the walls forms a spanning tree of the graph and the tree structure of the free space forms a spanning tree of the dual graph.[26] Similar pairs of interdigitating trees can be seen e.g. in the tree-shaped pattern of streams and rivers within a drainage basin and the dual tree-shaped pattern of ridgelines separating the streams.[27]

This partition of the edges and their duals into two trees leads to a simple proof of Euler's formula V − E + F = 2 for planar graphs with V vertices, E edges, and F faces. Any spanning tree and its complementary dual spanning tree partition the edges into two subsets of V − 1 and F − 1 edges respectively, and adding the sizes of the two subsets gives the equation

E = (V − 1) + (F − 1)

which may be rearranged to form Euler's formula. According to Duncan Sommerville, this proof of Euler's formula is due to G. K. C. Von Staudt's Geometrie der Lage (Nürnberg, 1847).[28]

In nonplanar surface embeddings the set of dual edges complementary to a spanning tree is not a dual spanning tree. Instead this set of edges is the union of a dual spanning tree with a small set of extra edges whose number is determined by the genus of the surface on which the graph is embedded. The extra edges, in combination with paths in the spanning trees, can be used to form a basis of the fundamental group of the surface.[29]

Additional properties

Matroids and algebraic duals

Let G be a connected graph. An algebraic dual of G is a graph G★ such that G and G★ have the same set of edges, any cycle of G is a cut of G★, and any cut of G is a cycle of G★. Every planar graph has an algebraic dual, which is in general not unique (any dual defined by a plane embedding will do). The converse is actually true, as settled by Hassler Whitney in Whitney's planarity criterion:[37]

A connected graph G is planar if and only if it has an algebraic dual.

The same fact can be expressed in the theory of matroids. If M is the graphic matroid of a graph G, then a graph G★ is an algebraic dual of G if and only if the graphic matroid of G★ is the dual matroid of M. Then Whitney's planarity criterion can be rephrased as stating that the dual matroid of a graphic matroid M is itself a graphic matroid if and only if the underlying graph G of M is planar. If G is planar, the dual matroid is the graphic matroid of the dual graph of G. In particular, all dual graphs, for all the different planar embeddings of G, have isomorphic graphic matroids.

For nonplanar surface embeddings, unlike planar duals, the dual graph is not generally an algebraic dual of the primal graph. And for a non-planar graph G, the dual matroid of the graphic matroid of G is not itself a graphic matroid. However, it is still a matroid whose circuits correspond to the cuts in G, and in this sense can be thought of as a generalized algebraic dual of G.

The duality between Eulerian and bipartite planar graphs can be extended to binary matroids (which include the graphic matroids derived from planar graphs): a binary matroid is Eulerian if and only if its dual matroid is bipartite.[32] The two dual concepts of girth and edge connectivity are unified in matroid theory by matroid girth: the girth of the graphic matroid of a planar graph is the same as the graph's girth, and the girth of the dual matroid (the graphic matroid of the dual graph) is the edge connectivity of the graph.[22]

Notes

  1. ↑ Bóna, Miklós (2006), A walk through combinatorics (2nd ed.), World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ, p. 276, doi:10.1142/6177, ISBN 981-256-885-9, MR 2361255.
  2. ↑ Ziegler, Günter M. (1995), "2.3 Polarity", Lectures on Polytopes, Graduate Texts in Mathematics 152, pp. 59–64.
  3. ↑ Weisstein, Eric W., "Self-dual graph", MathWorld.
  4. 1 2 Servatius, Brigitte; Christopher, Peter R. (1992), "Construction of self-dual graphs", The American Mathematical Monthly 99 (2): 153–158, doi:10.2307/2324184, MR 1144356.
  5. ↑ Thulasiraman, K.; Swamy, M. N. S. (2011), Graphs: Theory and Algorithms, John Wiley & Sons, Exercise 7.11, p. 198, ISBN 9781118030257.
  6. ↑ See the proof of Theorem 5 in Servatius & Christopher (1992).
  7. 1 2 di Battista, Giuseppe; Eades, Peter; Tamassia, Roberto; Tollis, Ioannis G. (1999), Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall, p. 91, ISBN 978-0-13-301615-4.
  8. ↑ Fleischner, Herbert J.; Geller, D. P.; Harary, Frank (1974), "Outerplanar graphs and weak duals", Journal of the Indian Mathematical Society 38: 215–219, MR 0389672.
  9. ↑ Sysło, Maciej M.; Proskurowski, Andrzej (1983), "On Halin graphs", Graph Theory: Proceedings of a Conference held in Lagów, Poland, February 10–13, 1981, Lecture Notes in Mathematics 1018, Springer-Verlag, pp. 248–256, doi:10.1007/BFb0071635.
  10. ↑ Weisstein, Eric W., "Dual Tessellation", MathWorld.
  11. ↑ Samet, Hanan (2006), Foundations of Multidimensional and Metric Data Structures, Morgan Kaufmann, p. 348, ISBN 9780123694461.
  12. 1 2 Gagarin, Andrei; Kocay, William; Neilson, Daniel (2003), "Embeddings of small graphs on the torus" (PDF), Cubo 5: 351–371.
  13. ↑ Nakamoto, Atsuhiro; Negami, Seiya (2000), "Full-symmetric embeddings of graphs on closed surfaces", Memoirs of Osaka Kyoiku University 49 (1): 1–15, MR 1833214.
  14. 1 2 Foulds, L. R. (2012), Graph Theory Applications, Springer, pp. 66–67, ISBN 9781461209331.
  15. ↑ Bondy, Adrian; Murty, U.S.R. (2008), "Planar Graphs", Graph Theory, Graduate Texts in Mathematics 244, Springer, Theorem 10.28, p. 267, doi:10.1007/978-1-84628-970-5, ISBN 9781846289699, LCCN 2007923502
  16. ↑ Angelini, Patrizio; Bläsius, Thomas; Rutter, Ignaz (2014), "Testing mutual duality of planar graphs", International Journal of Computational Geometry and Applications 24 (4): 325–346, arXiv:1303.1640, doi:10.1142/S0218195914600103, MR 3349917.
  17. ↑ Jensen, Tommy R.; Toft, Bjarne (1995), Graph Coloring Problems, Wiley-Interscience Series in Discrete Mathematics and Optimization 39, Wiley, p. 17, ISBN 9780471028659, note that "bridge" and "loop" are dual concepts.
  18. ↑ Balakrishnan, V. K. (1997), Schaum's Outline of Graph Theory, McGraw Hill Professional, Problem 8.64, p. 229, ISBN 9780070054899.
  19. ↑ Diestel, Reinhard (2006), Graph Theory, Graduate Texts in Mathematics 173, Springer, p. 25, ISBN 9783540261834.
  20. ↑ Godsil, Chris; Royle, Gordon F. (2013), Algebraic Graph Theory, Graduate Texts in Mathematics 207, Springer, Theorem 14.3.1, p. 312, ISBN 9781461301639.
  21. ↑ Oxley, J. G. (2006), Matroid Theory, Oxford Graduate Texts in Mathematics 3, Oxford University Press, p. 93, ISBN 9780199202508.
  22. 1 2 Cho, Jung Jin; Chen, Yong; Ding, Yu (2007), "On the (co)girth of a connected matroid", Discrete Applied Mathematics 155 (18): 2456–2470, doi:10.1016/j.dam.2007.06.015, MR 2365057.
  23. 1 2 Hartvigsen, D.; Mardon, R. (1994), "The all-pairs min cut problem and the minimum cycle basis problem on planar graphs", SIAM Journal on Discrete Mathematics 7 (3): 403–418, doi:10.1137/S0895480190177042.
  24. ↑ Noy, Marc (2001), "Acyclic and totally cyclic orientations in planar graphs", American Mathematical Monthly 108 (1): 66–68, doi:10.2307/2695680, MR 1857074.
  25. ↑ Tutte, W. T. (1984), Graph theory, Encyclopedia of Mathematics and its Applications 21, Reading, MA: Addison-Wesley Publishing Company, Advanced Book Program, p. 289, ISBN 0-201-13520-5, MR 746795.
  26. ↑ Lyons, Russell (1998), "A bird's-eye view of uniform spanning trees and forests", Microsurveys in discrete probability (Princeton, NJ, 1997), DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 41, Amer. Math. Soc., Providence, RI, pp. 135–162, MR 1630412. See in particular p. 138.
  27. ↑ Flammini, Alessandro (October 1996), Scaling Behavior for Models of River Network, Ph.D. thesis, International School for Advanced Studies, pp. 40–41.
  28. ↑ Sommerville, D. M. Y. (1958), An Introduction to the Geometry of N Dimensions, Dover.
  29. ↑ Eppstein, David (2003), "Dynamic generators of topologically embedded graphs", Proceedings of the 14th ACM/SIAM Symposium on Discrete Algorithms, pp. 599–608, arXiv:cs.DS/0207082.
  30. ↑ Harary, Frank (1969), Graph Theory, Reading, Mass.: Addison-Wesley Publishing Co., Theorem 9.4, p. 142, MR 0256911.
  31. ↑ Gross, Jonathan L.; Yellen, Jay, eds. (2003), Handbook of Graph Theory, CRC Press, p. 724, ISBN 978-1584880905.
  32. 1 2 Welsh, D. J. A. (1969), "Euler and bipartite matroids", Journal of Combinatorial Theory 6: 375–377, doi:10.1016/s0021-9800(69)80033-5, MR 0237368.
  33. ↑ He, Xin (1999), "On floor-plan of plane graphs", SIAM Journal on Computing 28 (6): 2150–2167, doi:10.1137/s0097539796308874.
  34. ↑ Florek, Jan (2010), "On Barnette's conjecture", Discrete Mathematics 310 (10-11): 1531–1535, doi:10.1016/j.disc.2010.01.018, MR 2601261.
  35. ↑ Las Vergnas, Michel (1980), "Convexity in oriented matroids", Journal of Combinatorial Theory, Series B 29 (2): 231–243, doi:10.1016/0095-8956(80)90082-9, MR 586435.
  36. ↑ Tutte, William Thomas (1953). "A contribution to the theory of chromatic polynomials".
  37. ↑ Whitney, Hassler (1932), "Non-separable and planar graphs", Transactions of the American Mathematical Society 34 (2): 339–362, doi:10.1090/S0002-9947-1932-1501641-2.

External links

This article is issued from Wikipedia - version of the Friday, March 18, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.