Recognizing Outer 1Planar Graphs in Linear TimeAuer, Christopher and Bachmaier, Christian and Brandenburg, Franz J. and Gleißner, Andreas and Hanauer, Kathrin and Neuwirth, Daniel and Reislhuber, Josef (2013) Recognizing Outer 1Planar Graphs in Linear Time. In: 21st International Symposium, GD 2013, September 2325, 2013 , pp. 107118(Official URL: http://dx.doi.org/10.1007/9783319038414_10). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783319038414_10
AbstractA graph is outer 1planar (o1p) if it can be drawn in the plane such that all vertices are on the outer face and each edge is crossed at most once. o1p graphs generalize outerplanar graphs, which can be recognized in linear time and specialize 1planar graphs, whose recognition is NP hard. Our main result is a lineartime algorithm that first tests whether a graph G is o1p, and then computes an embedding. Moreover, the algorithm can augment G to a maximal o1p graph. If G is not o1p, then it includes one of six minors (see Fig. 3), which are also detected by the recognition algorithm. Hence, the algorithm returns a positive or negative witness for o1p.
Actions (login required)
