2003/07/31 by David Eppstein · 1 citation
Computer Science · Mathematics · #Combinatorics #Computational Geometry and Mesh Generation #Data Management and Algorithms #Discrete mathematics #Euclidean geometry #Euclidean space #Geometry #Graph #Graph Theory and Algorithms #Intersection (aeronautics) #Intersection graph #Line graph #Line segment #Mathematics #Pathwidth #Planar graph #Plane (geometry) #Treewidth #cs.CG
paper · pdf · doi:10.1145/1497290.1497291
published as ACM Trans. Algorithms 5(2):15, 2009 · 32 pages, 20 figures. A shorter (10 page) version of this paper was presented at the 15th ACM-SIAM Symp. Discrete Algorithms, New Orleans, 2004, pp. 853-861
arxiv created 2007/11/16 · openalex publication_date 2009/03/01 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
We show how to test the bipartiteness of an intersection graph of n line segments or simple polygons in the plane, or of an intersection graph of balls in d -dimensional Euclidean space, 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. Our algorithms for these problems return either a bipartition of the input or an odd cycle in its intersection graph. We also consider lower bounds for connectivity and k -colorability problems of geometric intersection graphs. For unit balls in d dimensions, 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 point-line incidence testing 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.