Star-Based Separators for Intersection Graphs of c-Colored Pseudo-Segments
M. de Berg, B. M. P. Jansen, J. S. K. Lamme
平面分离定理指出,任何平面图𝒢都存在一个由O(√(n))个节点组成的分离器,其移除可将𝒢划分为大小至多为2n/3的分量,这是获得平面图上快速算法的广泛使用工具。圆盘的交图(推广了平面图)不允许这样的分离器。最近研究表明,圆盘图确实允许所谓的基于团的分离器,由O(√(n))个团组成。这一结果已推广到各种其他类型圆盘状对象的交图。不幸的是,线段交图不允许小的基于团的分离器,因为它们可能包含任意大的双团。即使在简单的轴对齐线段情况下也是如此。因此,本文引入基于双团的分离器(特别是基于星的分离器),即由少量双团(或星)组成的分离器。我们证明平面上任何c向的n条线段集合(其中c为常数)允许由O(√(n))个星组成的基于星的分离器。实际上,我们的结果更为一般,因为它适用于任何被划分为c个子集的n条伪线段集合,其中同一子集中的伪线段两两不相交。我们将结果扩展到c向多边形的交图。这些结果立即导致对此类交图的几乎精确距离预言机,具有O(n√(n))存储和O(√(n))查询时间,并且可以报告任意两个查询节点在交图中的跳数距离,其加性误差至多为2。这是此类交图的第一个具有次二次存储、次线性查询时间且仅具有加性误差的距离预言机。
The Planar Separator Theorem, which states that any planar graph 𝒢 has a separator consisting of O(√(n)) nodes whose removal partitions 𝒢 into components of size at most 2n3, is a widely used tool to obtain fast algorithms on planar graphs. Intersection graphs of disks, which generalize planar graphs, do not admit such separators. It has recently been shown that disk graphs do admit so-called clique-based separators that consist of O(√(n)) cliques. This result has been generalized to intersect...