论文标题
凸形的交叉图中的sublinear分离器
Sublinear separators in intersection graphs of convex shapes
论文作者
论文摘要
我们为在r^d中的紧凑型凸组集的相交图提供了足够的条件，具有平衡的sublinear尺寸分离器。该条件在交叉图中对均方根分离器的几个先前结果概括。此外，用于证明sublinear分离器的存在的参数是基于与一般着色号码的联系，而广义着色数字以前在几何设置中尚未探索过。
We give a natural sufficient condition for an intersection graph of compact convex sets in R^d to have a balanced separator of sublinear size. This condition generalizes several previous results on sublinear separators in intersection graphs. Furthermore, the argument used to prove the existence of sublinear separators is based on a connection with generalized coloring numbers which has not been previously explored in geometric settings.
