论文标题
在计算1平面图的顶点连接性上
On Computing Vertex Connectivity of 1-Plane Graphs
论文作者
论文摘要
图$ g $的顶点连接是最小的顶点$ s $的大小，因此断开了$ g \ setminus s $。对于平面图的类别，从结构和算法的角度来看，顶点连接的问题都是经过充分研究的。令$ g $为嵌入式图的平面，而$λ（g）$是通过将脸顶点插入每个脸部并将其连接到与脸部入射的$ g $的所有顶点获得的辅助图。如果$ s $是$ g $的最小顶点切割，则存在一个长度为$ 2 | s | $的周期，其顶点在$ s $和face顶点之间的顶点替代。该结构有助于设计线性时间算法，以找到平面图的最小顶点切割。在本文中，我们尝试针对1平面图类的类似方法 - 这些图是在平面上最多一次交叉的平面上的图形。 我们考虑了基于交叉终点引起的子图的不同类别图。对于1平面图，每个交叉的端点都会诱导完整的图$ k_4 $，我们表明最小顶点切割的结构与平面图中的结构相同，如上所述。对于1平面图，每个交叉点的端点至少诱导三个边缘（即，除了边缘的交叉对外，一个边缘），我们表明，对于任何最小的顶点切割$ s $，都存在直径$ o（| s | s |）$λ（g）$（g）$的循环。该结构使我们能够设计一种线性时间算法，以计算所有此类1平面图的顶点连接。
The vertex connectivity of a graph $G$ is the size of the smallest set of vertices $S$ such that $G \setminus S$ is disconnected. For the class of planar graphs, the problem of vertex connectivity is well-studied, both from structural and algorithmic perspectives. Let $G$ be a plane embedded graph, and $Λ(G)$ be an auxiliary graph obtained by inserting a face vertex inside each face and connecting it to all vertices of $G$ incident with the face. If $S$ is a minimal vertex cut of $G$, then there exists a cycle of length $2|S|$ whose vertices alternate between vertices of $S$ and face vertices. This structure facilitates the designing of a linear-time algorithm to find minimum vertex cuts of planar graphs. In this paper, we attempt a similar approach for the class of 1-plane graphs -- these are graphs with a drawing on the plane where each edge is crossed at most once. We consider different classes of 1-plane graphs based on the subgraphs induced by the endpoints of crossings. For 1-plane graphs where the endpoints of every crossing induce the complete graph $K_4$, we show that the structure of minimum vertex cuts is identical to that in plane graphs, as mentioned above. For 1-plane graphs where the endpoints of every crossing induce at least three edges (i.e., one edge apart from the crossing pair of edges), we show that for any minimal vertex cut $S$, there exists a cycle of diameter $O(|S|)$ in $Λ(G)$ such that all vertices of $S$ are in the neighbourhood of the cycle. This structure enables us to design a linear time algorithm to compute the vertex connectivity of all such 1-plane graphs.
