testing bipartiteness of geometric intersection graphs
We show how to test the bipartiteness of an intersection graph of n line segments or simple polygons in the plane, or of balls in R d , in time O ( n log n ). More generally we find subquadratic algorithms for connectivity and bipartiteness testing of intersection graphs of a broad class of geometric objects. For unit balls in R d , connectivity testing has equivalent randomized complexity to construction of Euclidean minimum spanning trees, and for line segments in the plane connectivity testing has the same lower bounds as Hopcroft's problem; therefore, for these problems, connectivity is unlikely to be solved as efficiently as bipartiteness. For line segments or planar disks, testing k -colorability of intersection graphs for k > 2 is NP-complete.
intersection graph line segments minimum spanning tree hopcroft's problem disks geometric thickness coin graph bipartite graph graph coloring