1-planar graphs are graphs that can be drawn in the plane such that any edge intersects with at most one other edge. Ackerman showed that the edges of a 1-planar graph can be partitioned into a planar graph and a forest, and claims that the proof leads to a linear time algorithm. However, it is not clear how one would obtain such an algorithm from his proof. In this paper, we first reprove Ackerman's result (in fact, we prove a slightly more general statement) and then show that the split can be found in linear time by using an edge-contraction data structure by Holm et al.
翻译:1-平面图是可在平面上绘制的图表,可以使任何边缘与其他边缘相交。 Ackerman 显示, 1-平面图的边缘可以分割成平面图和森林,并声称证据会导致线性时间算法。然而,尚不清楚如何从他的证据中获得这样的算法。在本文中,我们首先对Ackerman的结果进行重新论证(事实上,我们证明这是一个略微笼统的说明),然后通过使用Holm 等人的边缘合同数据结构来显示分割在线性时间。