Talk:Dual graph

it is misleading to say they come in pairs: a graph G can have two duals G' and G" depending on its plane drawing - as explained later. —The preceding unsigned comment was added by Tejas81 (talk • contribs) 19:54, 9 May 2007 (UTC).

what about giving the dualism between the Delaunay Triangulation and Voronoi Diagrams as an example?

Should his page take note that the planar projections of the regular polyhedra come in dual pairs (tetrahedron-tetrahedron, hexahedron-octahedron, and dodecahedron-icosahedron)? —Preceding unsigned comment added by 76.252.3.170 (talk) 23:00, 1 February 2008 (UTC)

• Let G be a connected graph. An algebraic dual of G is a graph G^★ so that G and G^★ have the same set of edges, any [Cycle space|cycle]] of G is a cut of G^★, and any cut of G is a cycle of G^★.
• Cut as in Cut (graph theory)? --Abdull (talk) 11:35, 28 July 2008 (UTC)

=biconnectedness=

Is it true that a dual graph is always biconnected? If so then this fact should be added to the article. (unsigned)

: No it is not true. Take any planar graph G with a cut-vertex, then its dual also has a cut-vertex. McKay (talk) 07:26, 29 April 2009 (UTC)

: : McKay's statement is not true. A cycle with a pending edge is planar and has a cut vertex, but its dual has only 2 vertices, so it cannot have a cut vertex. Nevertheless, a dual graph is not always biconnected. This is demonstrated by two disjoint cycles. The dual has 3 vertices and the 'middle one' is a cut vertex. Leen Droogendijk (talk) 14:09, 12 January 2014 (UTC)

I think, this page should adopt the clear distinction between the geometric dual and the combinatorial dual; just look up any graph theory text book.

--Gabriel (talk) 10:03, 8 June 2009 (UTC)

I find this statement

• The dual of a plane graph is a plane multigraph - multiple edges.Here we consider that graphs may have loops and multiple edges to avoid uncommon considerations.

really confusing. If I did not already know what it ts trying to say, I don't think I'd be able to figure it out. The footnote specifies "Here we consider that graphs may have loops and multiple edges to avoid uncommon considerations.". If that is true, then the statement should read

• The dual of a plane graph is a plane graph.

And I have no idea what "uncommon considerations" could be. Maproom (talk) 13:26, 25 March 2013 (UTC)

{{reflist|talk}}

It would be nice if there were some references to the application of dual graph in a discipline of science, such as Physics, Geology, Biology, Engineering, Computer Science, etc... — Preceding unsigned comment added by SuperChocolate (talk • contribs) 11:49, 4 June 2014 (UTC)

The article is almost all about plane graphs – and to its creators' credit, it makes this explicit. The embedding of graphs in other surfaces is something that interests me more than most, so please don't attach too much importance to this comment.

Some graphs can't be embedded in the plane, but all can be embedded in some surface. Even those that can be embedded in the plane can generally be embedded in some other surface. And duality of graphs is surface dependent. Two examples:

• The cubic Klein graph can't be embedded in the plane, but can be embedded in the genus-3 orientable surface. There, its dual is the 7-regular Klein graph.
• The cube can be embedded in the plane (or equivalently the sphere), where its dual graph is the octahedron, K_2,2,2. But the cube can also be embedded nicely in the torus, where its dual graph is a doubled K₄, like K₄ but with two edges joining each pair of vertices.

If I were working on the article, I would mention this. Maybe it's just as well I'm not. Maproom (talk) 21:56, 11 August 2015 (UTC)

{{reflist}}

:It is important, and mentioned in the lead, but should probably be elsewhere as well. Maybe as another subsection of the new "Variations" section? If you know of good sources for nonplanar duality that would be helpful (I think I know the subject well enough to write it without sources, but that way lies original research.) —David Eppstein (talk) 22:16, 11 August 2015 (UTC)

::{{ping|David Eppstein}}: I see that you have done an excellent job! Maproom (talk) 15:52, 12 August 2015 (UTC)

The article uses the word "complementary", applied to a graph, to mean "corresponding". It also writes once of "the complement of the graph in the manifold", in the topological sense. All of these may confuse readers who are familiar with the concept of "complement graph". I think confusion could be avoided by replacing "complementary" by "corresponding". I would also like to avoid the phrase "complement of the graph", but cannot at present think of a good way to do it. Maproom (talk) 19:21, 15 August 2015 (UTC)

:If it uses complementary to mean corresponding, it's a mistake. It should mean "not corresponding". Could you point out where that happens? Barring such mistakes, the word complement is used in two different senses here: (1) the set of edges not belonging to some particular edge set, and (2) the set of points not belonging to some particular point set. I don't know of a concise and accurate way to word those two different senses differently from each other. —David Eppstein (talk) 19:24, 15 August 2015 (UTC)

::Thank you for your response. I was wrong about "complementary", the article uses it correctly throughout. This just shows that I don't read definitions carefully enough.

::I will continue to try to think of a way to reword the "complement of the graph in the manifold" sentence. Maproom (talk) 07:27, 16 August 2015 (UTC)

:::We're also using "connected component" in a different sense in the nonplanar section than elsewhere, so it might be a good idea to avoid that one too if possible. —David Eppstein (talk) 07:43, 16 August 2015 (UTC)

{{Talk:Dual graph/GA1}}

{{Did you know nominations/Dual graph}}

In the "Spanning trees" section there is a sentence I really don't understand, or it is out of context:

"However, this does not work for shortest path trees, even approximately: there exist planar graphs such that, for every pair of a spanning tree in the graph and a complementary spanning tree in the dual graph, at least one of the two trees has distances that are significantly longer than the distances in its graph."

What's "this" which is not working? According to the cited source, "A spanning tree T in a finite planar connected graph G determines a dual spanning tree T∗ in the dual graph G∗ such that T and T∗ do not intersect. We show

that it is not always possible to find T in G such that the diameters of T and T∗ are both within a uniform multiplicative constant (independent of G) of the diameters of their ambient graphs."

In the article there is nothing about diameters. As shortest path trees are spanning trees, previous statements about spanning trees must be true for shortest path trees as well. SyP (talk) 14:41, 15 April 2017 (UTC)

:You can decompose into minimum spanning tree and dual maximum spanning tree, but you can't decompose into shortest path tree and another tree where you have any control over the lengths of the paths. —David Eppstein (talk) 15:51, 15 April 2017 (UTC)

::Thank you, now I understand. SyP (talk) 20:49, 15 April 2017 (UTC)

It may be interesting to present the dual graph of this three-nodes graphs: 1<->2 and 1<->3.

According to the definition it is not that clear if it must have one or two loops. MClerc (talk) 08:58, 18 October 2022 (UTC)

:Two loops. There is a dual edge for every primal edge. —David Eppstein (talk) 14:34, 18 October 2022 (UTC)