Planarity – Can you find the planar embedding?(jasondavies.com)
jasondavies.com
Planarity – Can you find the planar embedding?
https://www.jasondavies.com/planarity/
5 comments
Nice, as a game I was hooked.
16 moves in 44 sec
agree, cool 14 moves but 87 seconds ;-)
Tweak the game a bit and it could become NP hard?
If you know the graph is planar, then you can find the Tutte embedding by solving a set of linear equations [1].
However, the problem of finding a drawing that minimises the number of edge crossings (or even just the number of crossings in such a layout [e.g., 2]) for a general graph is NP-hard.
[1]: https://en.wikipedia.org/wiki/Tutte_embedding
[2]: https://epubs.siam.org/doi/abs/10.1137/120872310
However, the problem of finding a drawing that minimises the number of edge crossings (or even just the number of crossings in such a layout [e.g., 2]) for a general graph is NP-hard.
[1]: https://en.wikipedia.org/wiki/Tutte_embedding
[2]: https://epubs.siam.org/doi/abs/10.1137/120872310
There are linear time algorithms that take a planar graph and find an embedding where all the edges are straight lines.
However, I believe the problem of starting with a general graph and finding an embedding with the minimum number of edge crossings is NP-Hard.
However, I believe the problem of starting with a general graph and finding an embedding with the minimum number of edge crossings is NP-Hard.