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

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