Finding All Convex Cuts of a Plane Graph in Cubic Time
Finding All Convex Cuts of a Plane Graph in Cubic Time
复制标题
在立方时间内求平面图的所有凸割
DOI：
10.1007/978-3-642-38233-8_21
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Henning Meyerhenke
中科院分区：
文献类型：
--
作者：
R. Glantz;Henning Meyerhenke
在本文中，我们解决的任务，找到凸割的一个图。除了在几何和组合对象之间绘制连接的理论价值之外，具有此或相关属性的切割在各种应用中可能是有益的，例如，道路网络中的路由和网格划分。已知判定一个一般图是否k-凸的问题对于固定的k ≥ 2是NP-完全的。然而，我们表明，对于平面图的所有凸割（即，k = 2）可以在多项式时间内计算。为此，我们首先限制我们的考虑，以一个子集的平面图，所谓的交替切割可以嵌入平面曲线，使平面曲线形成一个安排的伪线。对于这个集合中的一个图G，我们用公式表示了一个二分图的平面曲线和凸割之间的一一对应关系，由此可以恢复G。由于它们的局部性质，交替割不能指导在更一般的图中搜索凸割。因此，我们修改的概念交替削减使用的Djokovic关系，这是全球性的，并产生削减的二分图。本文首先给出了一个算法，该算法计算了一个（不一定是平面的）二分图H′ =（V，E）在\（\mathcal{O}（|E| ^3）\）时间。然后，我们建立了图H的凸割与H的（二部）剖分H′上的Djokovic关系之间的联系。最后，我们使用这个连接来计算一个平面图在立方时间内的所有凸割。
In this paper we address the task of finding convex cuts of a graph. In addition to the theoretical value of drawing a connection between geometric and combinatorial objects, cuts with this or related properties can be beneficial in various applications, e.g., routing in road networks and mesh partitioning. It is known that the decision problem whether a general graph is k-convex is \(\mathcal{NP}\)-complete for fixed k ≥ 2. However, we show that for plane graphs all convex cuts (i.e., k = 2) can be computed in polynomial time. To this end we first restrict our consideration to a subset of plane graphs for which the so-called alternating cuts can be embedded as plane curves such that the plane curves form an arrangement of pseudolines. For a graph G in this set we formulate a one-to-one correspondence between the plane curves and the convex cuts of a bipartite graph from which G can be recovered. Due to their local nature, alternating cuts cannot guide the search for convex cuts in more general graphs. Therefore we modify the concept of alternating cuts using the Djokovic relation, which is of global nature and gives rise to cuts of bipartite graphs. We first present an algorithm that computes all convex cuts of a (not necessarily plane) bipartite graph H′ = (V,E) in \(\mathcal{O}(|E|^3)\) time. Then we establish a connection between convex cuts of a graph H and the Djokovic relation on a (bipartite) subdivision H′ of H. Finally, we use this connection to compute all convex cuts of a plane graph in cubic time.