Talk:Dual graph

non-isomorphic

...has order 6, not 7 right?... =The dual of a "graph" is not always a "graph" given that the Wikipedia has chosen the definition of "graph" to be the one that excludes loops and parallel edges (what is being called a "simple graph" in many books) the dual of a graph is not always a graph. Every connected component of a graph has to be 3-edge connected for its dual to be a graph. A cut edge corresponds to a loop in the dual, and an edge cut of two corresponds to parallel edges in the dual.

Also the dual of the dual is not the original graph if the original is disconnected. (See Bondy+Murty/Graph Theory and Applications.

Wouldn't it be better to speak about multigraphs rather than graphs to introduce dual. If we restrict ourselves to simple loopless graphs, the figure for non-isomorphic duals is wrong (parallel edges). —The preceding unsigned comment was added by Taxipom (talk • contribs) 00:18, 22 March 2007 (UTC). pom 00:18, 22 March 2007 (UTC) (sorry I forgot to sign) Also, the Whitney criterion will also be false. It seems that there is a strong evidence that duality should be introduced for multigraphs with loops allowed. pom 00:28, 22 March 2007 (UTC)

I don't know what means "the dual of a graph is not always a graph", even if we restrict the word graph to "simple graph". Although the definition is not so precise, the term "dual graph" means that it is a graph. Of course, some plane graph won't have a dual graph. Also, it is sometimes written "the dual" in this article, instead of "a dual graph". pom 00:25, 22 March 2007 (UTC)

The concept requires both multiple edges and loops. That is how it is nearly always done in technical places. McKay 06:23, 23 March 2007 (UTC)

It appears (to my untrained eye) that the figure for non-isomorphhic duals is in error. It is supposed to illustrate how "the same graph can have non-isomorphic dual graphs." However, the graph G is not identical in the top and bottom of the figure (the left-most vertex has been shifted to the interior). This is confusing to me. Kmote (talk) 20:03, 13 February 2008 (UTC)

It is topologically equivalent. There is a one-to-one matching of the points in top-G and bottom-G such that if a point A is connected to a point B in one, then A's equivalent connects to B's equivalent in the other.76.240.199.90 (talk) 01:37, 17 February 2008 (UTC)

introduction - come in pairs?

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).

example

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

Regular Polyhedra

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)

Cut

• 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)

geometric / combinatorial

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)

Confusing statement

I find this statement

• The dual of a plane graph is a plane multigraph - multiple edges.

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)

Applications of the Dual graph

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)

Non-plane graphs

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)

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)

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

"Complement", "complementary"

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)

GA Review

This review is transcluded from Talk:Dual graph/GA1. The edit link for this section can be used to add comments to the review.

Reviewer: 99of9 (talk · contribs) 04:48, 6 October 2016 (UTC)

I'm up for reviewing this article. Glad to see the nomination @David Eppstein:. Bear with me, I'm a bit new at this! --99of9 (talk) 04:48, 6 October 2016 (UTC)

Rate	Attribute	Review Comment
1. Well-written:
	1a. the prose is clear, concise, and understandable to an appropriately broad audience; spelling and grammar are correct.	Spelling and grammar are fine. It's clear and concise enough, and there are wikilinks to required concepts.
	1b. it complies with the Manual of Style guidelines for lead sections, layout, words to watch, fiction, and list incorporation.
2. Verifiable with no original research:
	2a. it contains a list of all references (sources of information), presented in accordance with the layout style guideline.
	2b. reliable sources are cited inline. All content that could reasonably be challenged, except for plot summaries and that which summarizes cited content elsewhere in the article, must be cited no later than the end of the paragraph (or line if the content is not in prose).
	2c. it contains no original research.	One reference is authored by the primary Wikipedia author (also nominator). I have checked this reference in detail, and confirm that it was published in conference proceedings, has been broadly cited, and is relevant and balanced in this article. This does not constitute bias or original research according to our policies.
	2d. it contains no copyright violations or plagiarism.	I've done some spot tests. Hard to say definitively, but I think plagiarism is unlikely here.
3. Broad in its coverage:
	3a. it addresses the main aspects of the topic.	Perhaps a little history of when the concept of duals was first developed? Maybe some words on the wider applications/uses of this concept? Done
	3b. it stays focused on the topic without going into unnecessary detail (see summary style).	It would be tough and somewhat heavy on detail for the general reader, but is roughly appropriate for the more mathematically inclined audience who would come to this page.
	4. Neutral: it represents viewpoints fairly and without editorial bias, giving due weight to each.	One reference is authored by the primary Wikipedia author (also nominator). I have checked this reference in detail, and confirm that it was published in conference proceedings, has been broadly cited, and is relevant and balanced in this article. This does not constitute bias or original research according to our policies.
	5. Stable: it does not change significantly from day to day because of an ongoing edit war or content dispute.
6. Illustrated, if possible, by media such as images, video, or audio:
	6a. media are tagged with their copyright statuses, and valid non-free use rationales are provided for non-free content.	The image commons:File:Intercpunetring.png could do with a description template and ensuring that the "author" is linked properly to the (now-renamed) uploader.  Done The image File:Noniso dual graphs.svg does not properly attribute the creator User:Drini of the PNG it was derived from File:Nonisomorphicdualgraps.png.  Done The email associated with the image File:K6-Petersen duality.svg should be forwarded to the commons:Commons:OTRS system to ensure it is in the system.  Done
	6b. media are relevant to the topic, and have suitable captions.
	7. Overall assessment.	Good job. Congrats.

Re the images: I moved the text on Intercpunetring.png into an Information template and fixed the link to the user, added text attributing the other image (although my own belief is that the graphs themselves are non-copyrightable, so an image that completely redraws them with a different layout as this one does has no actual copyright dependence on its predecessor), and forwarded the emails to OTRS. I assume it may take a little while for OTRS to read them and update the image data accordingly. —David Eppstein (talk) 00:09, 7 October 2016 (UTC)

Update: The OTRS information is now linked. —David Eppstein (talk) 01:00, 11 October 2016 (UTC)

Other comments

Lead

• "(if G is connected)" deserves a wikilink or explanation of what you mean by connected. --99of9 (talk) 04:53, 6 October 2016 (UTC)

• Related to this, I can't tell how to make a dual when dangling bond's are involved (see pic)...

  

  What is the dual to this? The 4-6 edge does not "separate two faces from one another", so therefore does not get an edge in the dual? In which case how do you get node 6 of G back from H? Or should the dual have a loop from the outside "face" to itself?

• It still has two faces on each side of it, they're just the same face as each other, so the dual vertex corresponding to that face has a self-loop. I've updated the article in an attempt to clarify this, as well as to link connected graph as suggested. —David Eppstein (talk) 05:14, 6 October 2016 (UTC)

•  Done lovely --99of9 (talk) 05:37, 6 October 2016 (UTC)

Dual polyhedra

• In this section it would help to assert that all convex polyhedra (3d) can be represented as a plane graph, to connect with the definition used of a dual graph. I was led astray here because the link to convex polyhedron is redirected to convex polytope, which includes higher dimensions. Since I knew that a 4d hypercube graph wasn't a planar graph, it seemed to contradict the idea that you could necessarily find a dual. --99of9 (talk) 05:54, 6 October 2016 (UTC)
  • Rewrote this section to give more of an introduction to polyhedral graphs, especially given your question in the next section of the review on self-dual graphs. —David Eppstein (talk) 00:16, 7 October 2016 (UTC)

Self duality

• "there also exist self-dual graphs that are not polyhedral, such as the one shown". The one shown seems to be two tetrahedra connected by sharing a vertex in common. Is that still a polyhedron, albeit not convex? --99of9 (talk) 06:39, 6 October 2016 (UTC)
  • No. "Polyhedral graph" is a technical term referring only to convex polyhedra. A polyhedral graph must be 3-connected (deleting up to two vertices keeps it connected) while in this case deleting the one shared vertex disconnects it. —David Eppstein (talk) 00:11, 7 October 2016 (UTC)

Simple vs multi

• "cutset" is used before it is defined and wikilinked. --99of9 (talk) 12:23, 6 October 2016 (UTC)
  • Glossed and linked at the first use. —David Eppstein (talk) 00:21, 7 October 2016 (UTC)

Uniqueness

• "Whitney" is used before he is defined and wikilinked. --99of9 (talk) 12:41, 6 October 2016 (UTC)
• "if it is a subdivision" ... please explain subdivision. --99of9 (talk) 12:44, 6 October 2016 (UTC)
  • Linked Hassler Whitney and glossed and linked subdivision. —David Eppstein (talk) 00:24, 7 October 2016 (UTC)

Cuts and cutsets

• What is a "*simple* cycle"? --99of9 (talk) 05:44, 7 October 2016 (UTC)
  • I rewrote much of this section to clarify some of its terms, including this one. —David Eppstein (talk) 00:34, 8 October 2016 (UTC)

Suggested 3a expansions

• I added a history section. Applications will require a bit more thought and research. Presumably it should at least include the duality of series-parallel circuits in CMOS design but there should be others. —David Eppstein (talk) 06:44, 24 October 2016 (UTC)

Spanning trees decomposition

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)

Three nodes graph

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)