论文标题
在完整拓扑图的平面子图上
On Plane Subgraphs of Complete Topological Drawings
论文作者
论文摘要
拓扑图是平面中图的表示形式，其中顶点由点表示，而边缘通过连接点的简单曲线。如果两个边在单个点，无论是在公共端点还是在正确的交叉点处，则图纸很简单。在本文中，我们研究了简单图纸的最大平面子图的属性$ d_n $的完整图$ k_n $上的$ n $顶点。我们的主要结构结果是最大平面子图是2个连接的，我们称之为3边缘连接。此外，任何最大平面子图都至少包含$ \ lceil 3n/2 \ rceil $边缘。我们还解决了获得$ d_n $的平面子图具有最大边缘数量的问题，证明此问题是NP完成的。但是，鉴于跨越$ d_n $的连接子图的飞机，可以在$ o（n^3）$ time中找到该子图的最大平面扩展。作为一个侧面的结果，我们还表明，找到两个标记点集的最大兼容平面直线图的问题是NP完整的。
Topological drawings are representations of graphs in the plane, where vertices are represented by points, and edges by simple curves connecting the points. A drawing is simple if two edges intersect at most in a single point, either at a common endpoint or at a proper crossing. In this paper we study properties of maximal plane subgraphs of simple drawings $D_n$ of the complete graph $K_n$ on $n$ vertices. Our main structural result is that maximal plane subgraphs are 2-connected and what we call essentially 3-edge-connected. Besides, any maximal plane subgraph contains at least $\lceil 3n/2 \rceil$ edges. We also address the problem of obtaining a plane subgraph of $D_n$ with the maximum number of edges, proving that this problem is NP-complete. However, given a plane spanning connected subgraph of $D_n$, a maximum plane augmentation of this subgraph can be found in $O(n^3)$ time. As a side result, we also show that the problem of finding a largest compatible plane straight-line graph of two labeled point sets is NP-complete.
