Efficient outerplanarity testing
Maciej M. Sysło, Masao Iri · Fundamenta Informaticae · 1979
This paper describes an efficient algorithm for finding whether a graph G has an outerplanar embedding in the plane. The algorithm is a realization of an inductive characterization of outerplanar graphs and uses depth-first search for coding a structure of a graph which is represented by adjacency lists. The algorithm has O(V) time and space bounds, where V is the number of vertices in G.