Structure And Properties Of Locally Outerplanar Graphs

This paper studies convex geometric graphs in which no path of length 3 self-intersects. A main result gives a decomposition of such graphs into induced outerplanar graph drawings. The resulting structure theorem is then used to compute a sharp, linear upper bound on the size of the edge set in terms of the number of vertices and the number and type of graphs in the decomposition. The paper also shows that though locally outerplanar graphs have hereditary properties, no graph property that is closed under the taking of minors can hold for all locally outerplanar graphs. Each of these results is generalized to convex geometric graphs in which no path of length \( k \) self-intersects.