[thumbuddy]

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]

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]

> 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.