Finding Triangles and Other Small Subgraphs in Geometric Intersection Graphs

Download PDF

We consider problems related to finding short cycles, small cliques, small independent sets, and small subgraphs in geometric intersection graphs. We obtain a plethora of new results. For example:
* For the intersection graph of n line segments in the plane, we give algorithms to find a 3-cycle in O(n^{1.408}) time, a size-3 independent set in O(n^{1.652}) time, a 4-clique in near-O(n^{24/13}) time, and a k-clique (or any k-vertex induced subgraph) in O(n^{0.565k+O(1)}) time for any constant k; we can also compute the girth in near-O(n^{3/2}) time.
* For the intersection graph of n axis-aligned boxes in a constant dimension d, we give algorithms to find a 3-cycle in O(n^{1.408}) time for any d, a 4-clique (or any 4-vertex induced subgraph) in O(n^{1.715}) time for any d, a size-4 independent set in near-O(n^{3/2}) time for any d, a size-5 independent set in near-O(n^{4/3}) time for d=2, and a k-clique (or any k-vertex induced subgraph) in O(n^{0.429k+O(1)}) time for any d and any constant k.
* For the intersection graph of n fat objects in any constant dimension d, we give an algorithm to find any k-vertex (non-induced) subgraph in O(n\log n) time for any constant k, generalizing a result by Kaplan, Klost, Mulzer, Roddity, Seiferth, and Sharir (1999) for 3-cycles in 2D disk graphs.
A variety of techniques is used, including geometric range searching, biclique covers, "high-low" tricks, graph degeneracy and separators, and shifted quadtrees. We also prove a near-\Omega(n^{4/3}) conditional lower bound for finding a size-4 independent set for boxes.