Timeline for Is deciding if one planar graph is dual to another really NP-hard (Wikipedia claim)?
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 10, 2016 at 6:20 | vote | accept | joro | ||
| Feb 10, 2016 at 4:38 | comment | added | Tyson Williams | 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. | |
| Feb 9, 2016 at 18:42 | comment | added | Chris Godsil | The wikipedia distinction between plane and planar graphs is quite standard. | |
| Feb 9, 2016 at 10:59 | history | edited | Jeremy Rickard | CC BY-SA 3.0 |
added 390 characters in body
|
| Feb 9, 2016 at 10:08 | history | edited | Jeremy Rickard | CC BY-SA 3.0 |
added 150 characters in body
|
| Feb 9, 2016 at 10:01 | history | answered | Jeremy Rickard | CC BY-SA 3.0 |