论文标题
在几何相交图中查找三角形和其他小子图
Finding Triangles and Other Small Subgraphs in Geometric Intersection Graphs
论文作者
论文摘要
我们考虑与寻找短周期，小集团，小型独立集和小小的子图相关的问题。我们获得了许多新结果。例如： *对于飞机上$ n $线段的交点图，我们给出算法以在$ O（n^{1.408}）$ time中找到3个周期$（n^{1.652}）$（n^{1.652}）$（n^{1.652}）$ time，一个4 clique in-4-cliquique，in-4-clique in-y-$ o（n^$ o（n^$ o）$（n^$ o）诱导子图）in $ o（n^{0.565k+o（1）}）$时间对于任何常数$ k $;我们还可以在接近$ o（n^{3/2}）$时间中计算腰围。 *对于$ n $ axis对准框的交叉图$ d $，我们给出算法以在$ o（n^{1.408}）中找到3个周期的$（n^{1.408}）$时间，任何$ d $，4-clique（或任何4-vertex诱导的子套件）中的$（n^n^$ o（n^1.715}），以获取$ o（或任何4-vertex诱导子），以获取$ o（n^{1.715}），任何$ d $，接近$ o（n^{3/2}）$时间，一个size-5独立设置为$ o（n^{4/3}）$ d = 2 $的时间和$ k $ -clique（或任何$ k $ -k $ -vertex诱导的sub-graph in $ o（n^0.429k+o（n nyy for in nothing）$ o（n^0.429k+o（b） *对于在任何恒定尺寸$ d $中的$ n $脂肪对象的交叉图，我们给出了一种算法，以在任何常数$ k $的$ o（n \ log n）$中找到任何$ k $ vertex（非引起的）子图，以$ o（n \ log n）$时间为$ k $，概述了由Kaplan，kaplan，klost，klost，mulzer，roddity，seifter和sherirs cys conters contrence contrence conterment $ k $的结果。 使用了各种技术，包括几何范围搜索，双式覆盖物，“高低”技巧，图形脱落和分离器以及转移的四分之一。我们还证明了一个接近$ω（n^{4/3}）$有条件的下限，以找到用于盒子的Size-4独立集。
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-$Ω(n^{4/3})$ conditional lower bound for finding a size-4 independent set for boxes.
