TY - GEN

T1 - Finding Triangles and Other Small Subgraphs in Geometric Intersection Graphs

AU - Chan, Timothy M.

N1 - Publisher Copyright:
Copyright © 2023 by SIAM.

PY - 2023

Y1 - 2023

N2 - 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(n1.408) time, a size-3 independent set in O(n1.652) time, a 4-clique in near-O(n24/13) time, and a k-clique (or any k-vertex induced subgraph) in O(n0.565k+O(1)) time for any constant k; we can also compute the girth in near-O(n3/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(n1.408) time for any d, a 4-clique (or any 4-vertex induced subgraph) in O(n1.715) time for any d, a size-4 independent set in near-O(n3/2) time for any d, a size-5 independent set in near-O(n4/3) time for d = 2, and a k-clique (or any k-vertex induced subgraph) in O(n0.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-Ω(n4/3) conditional lower bound for finding a size-4 independent set for boxes.

AB - 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(n1.408) time, a size-3 independent set in O(n1.652) time, a 4-clique in near-O(n24/13) time, and a k-clique (or any k-vertex induced subgraph) in O(n0.565k+O(1)) time for any constant k; we can also compute the girth in near-O(n3/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(n1.408) time for any d, a 4-clique (or any 4-vertex induced subgraph) in O(n1.715) time for any d, a size-4 independent set in near-O(n3/2) time for any d, a size-5 independent set in near-O(n4/3) time for d = 2, and a k-clique (or any k-vertex induced subgraph) in O(n0.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-Ω(n4/3) conditional lower bound for finding a size-4 independent set for boxes.

UR - http://www.scopus.com/inward/record.url?scp=85151896372&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85151896372&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85151896372

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 1777

EP - 1805

BT - 34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023

PB - Association for Computing Machinery

T2 - 34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023

Y2 - 22 January 2023 through 25 January 2023

ER -