mcq@drutx.UUCP (McQueerRL) (08/21/84)
[]---- Pardon me while I get pedantic for a little while. The Kuratowski characterization for non-planar graphs is indeed elegant, but "contains" is a hazy way of stating it. That seems to imply that all non-planar graphs contain a K5 or K3,3 as a subgraph. In fact, they must possess a subgraph homeomorphic to K5 or K3,3, homeomorphs being graphs which are isomorphic if one removes all degree 2 vertices by joining their edges into a single edge, ie: X---X---X---X becomes X--------X This consideration can make seeing the K3,3 or K5 in a non-planar graph quite tricky. Take a K5, put degree 2 vertices in all over the place, make several more arcs between them, warp the thing into a strange configuration, and the K5 will be hard to spot. What I really wanted to say was that Kuratowski's theorem actually doesn't yield good computational algorithms for planarity, and is tricky to code, to boot. The text I just dug out claims that it has been shown to be a least o(n**6). It's a pity, given the aformentioned elegance of the result. That textbook, "Graph Theory With Applications to Engineering and Computer Science", by Narsingh Deo, discusses use of depth first search techniques for planarity testing, although pretty concisely. OK, enough being pedantic. Graph theory used to be one of my favorite academic pursuits. Bob McQueer ihnp4!drutx!mcq (replies after the 24th are futile. I'll be leaving) P.S. - I think of Kuratowski's theorem kind of in the same light as Cayley's theorem for finite groups - very pretty results which characterize a class of objects in an immensely appealing fashion, but which truthfully don't prove to be of much use for practical application, or further development. Comments ?