Testing Bipartiteness of Geometric Intersection Graphs

Details Testing Bipartiteness of Geometric Intersection Graphs Testing Bipartiteness of Geometric Intersection Graphs

2003-07-09

arxiv.org/abs/cs/0307023v2

ACM Trans. Algorithms 5(2):15, 2009

Computer Science

Computational Geometry

32 pages, 20 figures. A shorter (10 page) version of this paper was presented at the 15th ACM-SIAM Symp. Discrete Algorithms,

Scientific paper

10.1145/1497290.1497291

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.

Affiliated with

Also associated with

No associations

Rating

Testing Bipartiteness of Geometric Intersection Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Testing Bipartiteness of Geometric Intersection Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Testing Bipartiteness of Geometric Intersection Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-137460