3 ms·
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 comm
by graphviz 3y ago
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.
- thumbuddy 3y agoI 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.
- amelius 3y agoIs 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.
- bhickey 3y ago> 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 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.