Talk:Dual graph

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated B-class, Mid-importance)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
B Class
Mid Importance
 Field: Discrete mathematics


non-isomorphic[edit]

...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 (talkcontribs) 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?[edit]

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 (talkcontribs) 19:54, 9 May 2007 (UTC).

example[edit]

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

Regular Polyhedra[edit]

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[edit]

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

biconnectedness[edit]

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[edit]

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[edit]

I find this statement

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

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

  1. ^ Here we consider that graphs may have loops and multiple edges to avoid uncommon considerations.

Applications of the Dual graph[edit]

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 (talkcontribs) 11:49, 4 June 2014 (UTC)

Non-plane graphs[edit]

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, K2,2,2. But the cube can also be embedded nicely in the torus, where its dual graph is a doubled K4, like K4 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"[edit]

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)