MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Wikipedia claims (permanent link) without reference:

Testing whether one planar graph is dual to another is NP-complete.

Another claim with reference:

For any plane graph G, the medial graph of G and the medial graph of the dual graph of G are isomorphic. Conversely, for any 4-regular plane graph H, the only two plane graphs with medial graph H are dual to each other.

One can decide if a planar graph is dual to another by checking if the medial graphs are isomorphic.

The two Wikipedia claims mean graph isomorphism is NP-complete, which is unlikely collapse.

Q1 What is wrong with this?

share|cite|improve this question
11  
This is a problem coming from slightly bad naming. 'Plane graph' and 'Planar graph' are not the same: the former is a graph together with a crossing-free drawing in the plane, the latter is a graph which has at least one such drawing. The extra hardness that boosts testing planar duality into NP-complete (as compared to being at most as hard as GI) comes from the choice of non-isomorphic embeddings. – user36212 Feb 9 at 12:40
up vote 22 down vote accepted

The dual graph and medial graph depend on the choice of an embedding in the plane. The Wikipedia claim seems to be that testing whether there are choices of embeddings for which two graphs are dual is NP-complete.

It looks as though Wikipedia makes a distinction between a planar graph (can be embedded in the plane) and plane graph (is embedded in the plane).

Edit: Actually, later on in the Wikipedia article, there is a reference, to

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

and the precise statement is indeed as I understood.

share|cite|improve this answer
5  
The wikipedia distinction between plane and planar graphs is quite standard. – Chris Godsil Feb 9 at 18:42
1  
I wrote the second quote given by the OP. This answer by Jeremy is great. The essential confusion is that people often speak of the dual graph of planar graph. In reality, an embedding of the planar graph is also needed. While it is possible that a particular embedding is clear from context, I get the impression that most people are unaware of this technicality. For more information, carefully read the Wikipedia section Dual_graph#Uniqueness. The image in that section provides a good example. – Tyson Williams Feb 10 at 4:38

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.