کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
436749 | 690032 | 2013 | 12 صفحه PDF | دانلود رایگان |

A 1-planar graph is a graph that can be embedded in the plane with at most one crossing per edge. It is known that testing 1-planarity of a graph is NP-complete.In this paper, we consider maximal 1-planar graphs. A graph G is maximal 1-planar if addition of any edge destroys 1-planarity of G. We first study combinatorial properties of maximal 1-planar embeddings. In particular, we show that in a maximal 1-planar embedding, the graph induced by the non-crossing edges is spanning and biconnected.Using the properties, we show that the problem of testing maximal 1-planarity of a graph G can be solved in linear time, if a rotation system Φ (i.e., the circular ordering of edges for each vertex) is given. We also prove that there is at most one maximal 1-planar embedding ξ of G that is consistent with the given rotation system Φ. Our algorithm also produces such an embedding in linear time, if it exists.
Journal: Theoretical Computer Science - Volume 513, 18 November 2013, Pages 65–76