Testing Maximal 1Planarity of Graphs with a Rotation System in Linear TimeEades, Peter and Hong, SeokHee and Katoh, Naoki and Liotta, Giuseppe and Schweitzer, Pascal and Suzuki, Yusuke (2013) Testing Maximal 1Planarity of Graphs with a Rotation System in Linear Time. In: 20th International Symposium, GD 2012, September 1921, 2012 , pp. 339345(Official URL: http://link.springer.com/chapter/10.1007/9783642...). Full text not available from this repository.
Official URL: http://link.springer.com/chapter/10.1007/9783642...
AbstractA 1planar graph is a graph that can be embedded in the plane with at most one crossing per edge. It is known that testing 1planarity of a graph is NPcomplete. A 1planar embedding of a graph G is maximal if no edge can be added without violating the 1planarity of G. In this paper we show that the problem of testing maximal 1planarity 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 1planar embedding of G that preserves the given rotation system, and our algorithm produces such an embedding in linear time, if it exists.
Actions (login required)
