Wikipedia [claims (permanent link)](https://en.wikipedia.org/w/index.php?title=Dual_graph&oldid=694744772) without reference:



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


Another [claim](https://en.wikipedia.org/wiki/Medial_graph) 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?
> 
> 
> 



Is deciding if one planar graph is dual to another really NP-hard (Wikipedia claim)?
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](http://arxiv.org/abs/1303.1640)


and the precise statement is indeed as I understood.


