15
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 11
    $\begingroup$ 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. $\endgroup$
    – user36212
    Commented Feb 9, 2016 at 12:40

1 Answer 1

Reset to default
23
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 5
    $\begingroup$ The wikipedia distinction between plane and planar graphs is quite standard. $\endgroup$
    – Chris Godsil
    Commented Feb 9, 2016 at 18:42
  • 1
    $\begingroup$ 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. $\endgroup$
    – Tyson Williams
    Commented Feb 10, 2016 at 4:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .