TY - JOUR T1 - Extending planar graph algorithms to K3,3-free graphs JF - Information and Computation Y1 - 1990 A1 - Khuller, Samir AB - 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 K3,3-free graphs, showing that the restriction of planarity is not important. The three problems dealt with are: graph coloring, depth first search, and maximal independent sets. As a corollary we show that K3,3-free graphs are five colorable (this bound is tight). VL - 84 SN - 0890-5401 UR - http://www.sciencedirect.com/science/article/pii/089054019090031C CP - 1 M3 - 10.1016/0890-5401(90)90031-C ER -