论文标题
最近的邻居分解图
Nearest-Neighbor Decompositions of Drawings
论文作者
论文摘要
令$ \ Mathcal {d} $成为飞机上的一组直线段，可能会越过，让$ c $为正整数。我们用$ p $表示$ \ mathcal {d} $的直线段的端点的联合以及对段对之间的交叉点的点。我们说，如果我们可以将$ p $ $ p $分配到$ c $ c $ point $ p_1，\ ldots，p_c $，则$ c $ c $零件的$ \ mathcal {d} $在$ c $零件中具有最近的neighbor分解。我们表明，决定是否可以将$ \ MATHCAL {D} $作为$ C \ geq 3 $最近的邻居图的结合，即使没有两个片段交叉也是如此。我们表明，对于$ c = 2 $，它在一般设置中是NP完整的，当没有两个段交叉时，可以解决多项式时间。我们展示了$ o（\ log n）$ - 近似算法在次指定时间内运行的近似算法，用于将$ \ Mathcal {d} $划分为最小数量的最近的neighbor图。 作为我们分析的主要工具，我们为图形$ \ Mathcal {d} $建立了冲突图的概念。冲突图的顶点是$ \ Mathcal {d} $的连接组件，假设每个连接的组件是其顶点的最接近的邻居图，并且在两个组件$ u $和$ v $之间存在优势，并且仅当$ u \ u \ cup v $的最近邻居图中$ \ u \ u \ cup v $ in Edge of vertex in $ u $ u $ u $ $ u $ $ u $ $ vertex in gertex in gertex中。我们表明字符串图是某些平面图的冲突图。对于平面图和完整的$ k $ - 分段图，我们提供了额外的，更高效的结构。我们此外表明，非平面图的细分不是冲突图。最后，我们显示了一个用于冲突图的分离器引理。
Let $\mathcal{D}$ be a set of straight-line segments in the plane, potentially crossing, and let $c$ be a positive integer. We denote by $P$ the union of the endpoints of the straight-line segments of $\mathcal{D}$ and of the intersection points between pairs of segments. We say that $\mathcal{D}$ has a nearest-neighbor decomposition into $c$ parts if we can partition $P$ into $c$ point sets $P_1, \ldots, P_c$ such that $\mathcal{D}$ is the union of the nearest neighbor graphs on $P_1, \ldots, P_c$. We show that it is NP-complete to decide whether $\mathcal{D}$ can be drawn as the union of $c\geq 3$ nearest-neighbor graphs, even when no two segments cross. We show that for $c = 2$, it is NP-complete in the general setting and polynomial-time solvable when no two segments cross. We show the existence of an $O(\log n)$-approximation algorithm running in subexponential time for partitioning $\mathcal{D}$ into a minimum number of nearest-neighbor graphs. As a main tool in our analysis, we establish the notion of the conflict graph for a drawing $\mathcal{D}$. The vertices of the conflict graph are the connected components of $\mathcal{D}$, with the assumption that each connected component is the nearest neighbor graph of its vertices, and there is an edge between two components $U$ and $V$ if and only if the nearest neighbor graph of $U \cup V$ contains an edge between a vertex in $U$ and a vertex in $V$. We show that string graphs are conflict graphs of certain planar drawings. For planar graphs and complete $k$-partite graphs, we give additional, more efficient constructions. We furthermore show that there are subdivisions of non-planar graphs that are not conflict graphs. Lastly, we show a separator lemma for conflict graphs.
