Testing bipartiteness of geometric intersection graphs

ABSTRACT

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.

REFERENCES

• 1: Pankaj K. Agarwal , Herbert Edelsbrunner , Otfried Schwarzkopf , Emo Welzl, Euclidean minimum spanning trees and bichromatic closest pairs, Discrete & Computational Geometry, v.6 n.5, p.407-422, 1991 [doi>10.1007/BF02574698]
• 2: Agarwal, P. K., and Erickson, J. 1999. Geometric range searching and its relatives. In Advances in Discrete and Computational Geometry, B. Chazelle, J. E. Goodman, and R. Pollack, Eds. Number 223 in Contemporary Mathematics. American Mathematics Society, 1--56.
• 3: F Aurenhammer, Power diagrams: properties, algorithms and applications, SIAM Journal on Computing, v.16 n.1, p.78-96, Feb. 1987 [doi>10.1137/0216006]
• 4: Barát, J., Matoušek, J., and Wood, D. R. 2006. Bounded-degree graphs have arbitrarily large geometric thickness. Electron. J. Combinat. 13, 1, R3.
• 5: Paul B. Callahan, Dealing with higher dimensions: the well-separated pair decomposition and its applications, Johns Hopkins University, Baltimore, MD, 1995
• 6: Chan, T. M.-Y. 1999. Geometric applications of a randomized optimization technique. Disc. Computat. Geom. 22, 4 (Dec.), 547--567.
• 7: Chazelle, B. 1996. Lines in space: combinatorics and algorithms. Algorithmica 15, 5, 428--447.
• 8: Bernard Chazelle , Herbert Edelsbrunner, An optimal algorithm for intersecting line segments in the plane, Journal of the ACM (JACM), v.39 n.1, p.1-54, Jan. 1992 [doi>10.1145/147508.147511]
• 9: Brent N. Clark , Charles J. Colbourn , David S. Johnson, Unit disk graphs, Discrete Mathematics, v.86 n.1-3, p.165-177, Dec. 14, 1990 [doi>10.1016/0012-365X(90)90358-O]
• 10: Clarkson, K. L., Eppstein, D., Miller, G. L., Sturtivant, C., and Teng, S.-H. 1996. Approximating center points with iterated Radon points. Int. J. Computat. Geom. Appl. 6, 3 (Sept.), 357--377.
• 11: Giuseppe Di Battista , Peter Eades , Roberto Tamassia , Ioannis G. Tollis, Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall PTR, Upper Saddle River, NJ, 1998
• 12: Dillencourt, M. B., Eppstein, D., and Hirschberg, D. S. 2000. Geometric thickness of complete graphs. J. Graph Algor. Appl. 4, 3, 5--17.
• 13: Dujmović, V., and Wood, D. R. 2006. Graph treewidth and geometric thickness parameters. In Proceedings of the 13th International Symposium on Graph Drawing (GD 2005) P. Healy and N. S. Nikolov, Eds. Lecture Notes in Computer Science, vol. 3843. Springer-Verlag, Berlin, Germany, 129--140.
• 14: Christian A. Duncan , David Eppstein , Stephen G. Kobourov, The geometric thickness of low degree graphs, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA [doi>10.1145/997817.997868]
• 15: Herbert Edelsbrunner , Ernst Peter Mücke, Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms, ACM Transactions on Graphics (TOG), v.9 n.1, p.66-104, Jan. 1990 [doi>10.1145/77635.77639]
• 16: Ehrlich, G., Even, S., and Tarjan, R. E. 1986. Intersection graphs of curves in the plane. J. Combinat. Theory, Ser. B 21, 8--20.
• 17: David Eppstein, Separating Thickness from Geometric Thickness, Revised Papers from the 10th International Symposium on Graph Drawing, p.150-161, August 26-28, 2002
• 18: Eppstein, D. 2004. Separating thickness from geometric thickness. In Towards a Theory of Geometric Graphs, J. Pach, Ed. Number 342 in Contemporary Mathematics. American Mathematics Society, 75--86.
• 19: David Eppstein , Zvi Galil , Giuseppe F. Italiano , Amnon Nissenzweig, Sparsification—a technique for speeding up dynamic graph algorithms, Journal of the ACM (JACM), v.44 n.5, p.669-696, Sept. 1997 [doi>10.1145/265910.265914]
• 20: Eppstein, D., Miller, G. L., and Teng, S.-H. 1995. A deterministic linear time algorithm for geometric separators and its applications. Fund. Inf. 22, 4 (Apr.), 309--331.
• 21: Eppstein, D., van Kreveld, M. J., Mumford, E., and Speckmann, B. 2007. Edges and switches, tunnels and bridges. In Proceedings of the 10th Workshop on Algorithms and Data Structures. Lecture Notes in Computer Science, vol. 4619. Springer-Verlag, Berlin, Germany, 77--88.
• 22: Erickson, J. 1996. New lower bounds for Hopcroft's problem. Disc. Computat. Geom. 16, 4, 389--418.
• 23: Fürer, M., and Kasiviswanathan, S. P. 2006. Spanners for geometric intersection graphs. ACM Computing Research Repository. ACM, New York.
• 24: Garey, M. R., Johnson, D. S., and Stockmeyer, L. 1976. Some simplified NP-complete graph problems. Theoret. Comput. Sci. 1, 237--267.
• 25: Graf, A., Stumpf, M., and Weißenfels, G. 1998. On coloring unit disk graphs. Algorithmica 20, 3, 277--293.
• 26: Guibas, L. J., Hershberger, J. E., Suri, S., and Zhang, L. 2001. Kinetic connectivity of unit disks. Disc. Computat. Geom. 25, 4 (Apr.), 591--610.
• 27: John Hershberger , Subhash Suri, Kinetic connectivity of rectangles, Proceedings of the fifteenth annual symposium on Computational geometry, p.237-246, June 13-16, 1999, Miami Beach, Florida, United States [doi>10.1145/304893.304977]
• 28: John Hershberger , Subhash Suri, Simplified kinetic connectivity for rectangles and hypercubes, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.158-167, January 07-09, 2001, Washington, D.C., United States
• 29: Jacob Holm , Kristian de Lichtenberg , Mikkel Thorup, Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity, Journal of the ACM (JACM), v.48 n.4, p.723-760, July 2001 [doi>10.1145/502090.502095]
• 30: Joan P. Hutchinson , Thomas C. Shermer , Andrew Vince, On Representations of Some Thickness-Two Graphs, Proceedings of the Symposium on Graph Drawing, p.324-332, September 20-22, 1995
• 31: Imai, H. 1982. Finding connected components of an intersection graph of squares in the Euclidean plane. Inform. Proc. Lett. 15, 3, 125--128.
• 32: Imai, H., and Asano, T. 1983. Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane. J. Algorithms 4, 310--323.
• 33: Kainen, P. C. 1973. Thickness and coarseness of graphs. Abh. Math. Sem. Univ. Hamburg 39, 88--95.
• 34: Drago Krznaric , Christos Levcopoulos , Bengt J. Nilsson, Minimum Spanning Trees in d Dimensions, Proceedings of the 5th Annual European Symposium on Algorithms, p.341-349, September 15-17, 1997
• 35: Mansfield, A. 1983. Determining the thickness of a graph is NP-hard. Math. Proc. Cambridge Philos. Soc. 93, 9, 9--23.
• 36: Gary L. Miller , Shang-Hua Teng , William Thurston , Stephen A. Vavasis, Separators for sphere-packings and nearest neighbor graphs, Journal of the ACM (JACM), v.44 n.1, p.1-29, Jan. 1997 [doi>10.1145/256292.256294]
• 37: Gary L. Miller , Shang-Hua Teng , William Thurston , Stephen A. Vavasis, Geometric Separators for Finite-Element Meshes, SIAM Journal on Scientific Computing, v.19 n.2, p.364-386, March 1998 [doi>10.1137/S1064827594262613]
• 38: Walter Schnyder, Embedding planar graphs on the grid, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.138-148, January 22-24, 1990, San Francisco, California, United States
• 39: Micha Sharir , Pankaj K. Agarwal, Davenport-Schinzel sequences and their geometric applications, Cambridge University Press, New York, NY, 1996
• 40: W. D. Smith , N. C. Wormald, Geometric Separator Theorems and Applications, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.232, November 08-11, 1998
• 41: Tamassia, R., and Tollis, I. G. 1989. Tesselation representations of planar graphs. In Proceedings of the 27th Allerton Conference Communication Control Computation 48--57.
• 42: Robert Endre Tarjan, Efficiency of a Good But Not Linear Set Union Algorithm, Journal of the ACM (JACM), v.22 n.2, p.215-225, April 1975 [doi>10.1145/321879.321884]
• 43: Shang-Hua Teng, Points, spheres, and separators: a unified geometric approach to graph partitioning, Carnegie Mellon University, Pittsburgh, PA, 1992
• 44: Wood, D. R. 2003. Geometric thickness in a grid. Disc. Math. 273, 1--3, 221--234.
• 45: C. K. Yap, A geometric consistency theorem for a symbolic perturbation scheme, Proceedings of the fourth annual symposium on Computational geometry, p.134-142, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73407]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Theory

Keywords:
Bipartite graph, Hopcroft's problem, coin graph, disks, geometric thickness, graph coloring, intersection graph, line segments, minimum spanning tree