Minimal Obstructions for 1‐Immersions and Hardness of 1‐Planarity Testing
Minimal Obstructions for 1‐Immersions and Hardness of 1‐Planarity Testing
复制标题
DOI：
10.1002/jgt.21630
复制
发表时间：
2009-02
影响因子：
0.9
通讯作者：
V. P. Korzhik;B. Mohar
中科院分区：
文献类型：
--
作者：
V. P. Korzhik;B. Mohar
一个图是1-平面的，如果它可以在平面上画，使得每条边不超过一条边（并且任何一对交叉边只交叉一次）。如果图G-e对于G的每条边e都是1-平面的，则非1-平面图G是最小的。我们构造了两个极小非1-平面图的无限族，并证明了对任意整数n≥63，至少存在2（n-54）/4个n阶非同构极小非1-平面图.证明了1-平面性检验是NP-完全的。
A graph is 1‐planar if it can be drawn on the plane so that each edge is crossed by no more than one other edge (and any pair of crossing edges cross only once). A non‐1‐planar graph G is minimal if the graph G−e is 1‐planar for every edge e of G. We construct two infinite families of minimal non‐1‐planar graphs and show that for every integer n≥63 , there are at least 2(n−54)/4 nonisomorphic minimal non‐1‐planar graphs of order n. It is also proved that testing 1‐planarity is NP‐complete.