3 ms·

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

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.

amelius 3y ago
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.
- 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.