A Linear-Time Algorithm for Testing Outer-1-Planarity

Hong, Seok-Hee and Eades, Peter and Katoh, Naoki and Liotta, Giuseppe and Schweitzer, Pascal and Suzuki, Yusuke (2013) A Linear-Time Algorithm for Testing Outer-1-Planarity. In: 21st International Symposium, GD 2013, September 23-25, 2013 , pp. 71-82(Official URL: http://dx.doi.org/10.1007/978-3-319-03841-4_7).

Full text not available from this repository.


A graph is 1-planar if it can be embedded in the plane with at most one crossing per edge. A graph is outer-1-planar if it has an embedding in which every vertex is on the outer face and each edge has at most one crossing. We present a linear time algorithm to test whether a graph is outer-1-planar. The algorithm can be used to produce an outer-1-planar embedding in linear time if it exists.

Item Type: Conference Paper
Classifications: G Algorithms and Complexity > G.420 Crossings
G Algorithms and Complexity > G.490 Embeddings
G Algorithms and Complexity > G.770 Planarity Testing
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1362

Actions (login required)

View Item View Item