Parallel Algorithms for $K_{5}$-minor Free Graphs
Samir Khuller · eCommons (Cornell University) · 1988
For several problems, restricting attention to special classes of graphs has yielded better algorithms. In particular, restricting to planar graphs yields efficient parallel algorithms for several graph problems. In this paper, we extend these algorithms to $K_{5}$-minor free graphs, showing that the restriction of planarity is not important. The two problems dealt with are: graph coloring and maximal independent sets. We also show that $K_{5}$-minor free graphs are four colorable (this bound is tight). We also give an NC algorithms to recognize $K_{5}$-minor free graphs.