Recognizing Outer 1-Planar Graphs in Linear Time

摘要: A graph is outer 1-planar o1p if it can be drawn in the plane such that all vertices are on face and each edge crossed at most once. graphs generalize outerplanar graphs, which recognized linear time specialize whose recognition $\mathcal{NP}$ -hard. Our main result a linear-time algorithm first tests whether graphi¾?G o1p, then computes an embedding. Moreover, augment G to maximal graph. If not includes one of six minors see Fig. 3, also detected by algorithm. Hence, returns positive or negative witness for o1p.