Optimization Algorithms for Planar Graphs

planarity.org

47 points·bhickey··5 comments

In practice, often people don't know if graphs will be planar or if they should expect it. However this is great work for specialists. In the graph drawing community, work that focused on planar graphs has been quite elegant but applications are not that widespread.

I somewhat agree with you, but, you can depending on graph size and time test for planarity. There are also some physical ish cases where graphs are guaranteed planar. And like most things, maybe empirically one of these methods works.

Is a planarity testing algorithm explained in the book?

Also, methods to transform any graph into a planar graph with some cost function?

This is what I would be most interested in.

> Is a planarity testing algorithm explained in the book?

Planar graphs do not embed K5 (the complete graph with five nodes) or K3,3 (the complete bipartite graph with three nodes on each side). You can get a brief overview of planarity testing algorithms here: https://en.m.wikipedia.org/wiki/Planarity_testing

> Also, methods to transform any graph into a planar graph with some cost function?

Do you mean an algorithm that finds a planar subgraph while optimizing some cost? Sounds interesting, but it's not something I've ever explored.

Heh, found this game:

https://www.jasondavies.com/planarity/

Reply on news.ycombinator.com