graphs in these classes. This allows the planar graph algorithm to be extended to certain broader families of graphs closed under graph minors and having the structure of clique-sums of planar graphs and graphs of bounded size. A minor-closed family of graphs has this clique-sum structure exactly when its forbidden minors include a graph with crossing number at most one.

Approximation algorithms

The

1.Previous
3.Next