  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 hence is
unlikely to be solved as efficiently as bipartiteness testing. For line
segments or planar disks, testing k-colorability of intersection graphs for k>2
is NP-complete.
