A LinearTime Algorithm for Testing Outer1PlanarityHong, SeokHee and Eades, Peter and Katoh, Naoki and Liotta, Giuseppe and Schweitzer, Pascal and Suzuki, Yusuke (2013) A LinearTime Algorithm for Testing Outer1Planarity. In: 21st International Symposium, GD 2013, September 2325, 2013 , pp. 7182(Official URL: http://dx.doi.org/10.1007/9783319038414_7). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783319038414_7
AbstractA graph is 1planar if it can be embedded in the plane with at most one crossing per edge. A graph is outer1planar 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 outer1planar. The algorithm can be used to produce an outer1planar embedding in linear time if it exists.
Actions (login required)
