Finding Triangles and Other Small Subgraphs in Geometric Intersection Graphs

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publication34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023
PublisherAssociation for Computing Machinery
Pages1777-1805
Number of pages29
ISBN (Electronic)9781611977554
StatePublished - 2023
Externally publishedYes
Event34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023 - Florence, Italy
Duration: Jan 22 2023Jan 25 2023

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume2023-January

Conference

Conference34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023
Country/TerritoryItaly
CityFlorence
Period1/22/231/25/23

ASJC Scopus subject areas

  • Software
  • General Mathematics

Fingerprint

Dive into the research topics of 'Finding Triangles and Other Small Subgraphs in Geometric Intersection Graphs'. Together they form a unique fingerprint.

Cite this