Testing Maximal 1-Planarity of Graphs with a Rotation System in Linear Time

Eades, Peter and Hong, Seok-Hee and Katoh, Naoki and Liotta, Giuseppe and Schweitzer, Pascal and Suzuki, Yusuke (2013) Testing Maximal 1-Planarity of Graphs with a Rotation System in Linear Time. In: 20th International Symposium, GD 2012, September 19-21, 2012 , pp. 339-345(Official URL: http://link.springer.com/chapter/10.1007/978-3-642...).

Full text not available from this repository.


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. A 1-planar embedding of a graph G is maximal if no edge can be added without violating the 1-planarity of G. In this paper 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 preserves the given rotation system, and our algorithm produces such an embedding in linear time, if it exists.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-642-36763-2_30
Classifications: G Algorithms and Complexity > G.490 Embeddings
G Algorithms and Complexity > G.770 Planarity Testing
Depositing User: Administration GDEA
Date Deposited: 21 Nov 2013 16:13
Last Modified: 21 Nov 2013 16:13
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1322

Actions (login required)

View Item View Item