Small Universal Point Sets for k-Outerplanar Graphs.

A point set S⊆R2<inline-graphic></inline-graphic> is universal for a class G<inline-graphic></inline-graphic> of planar graphs if every graph of G<inline-graphic></inline-graphic> has a planar straight-line embedding on S<inline-graphic></inline-graphic>. It is well-known that the integer grid is a quadratic-size universal point set for planar graphs, while the existence of a subquadratic universal point set still remains one of the most fascinating open problems in Graph Drawing. In this paper we make a major step towards a solution for this problem. Motivated by the fact that each point set of size n in general position is universal for the class of n-vertex outerplanar graphs, we concentrate our attention on k-outerplanar graphs. We prove that they admit an O(nlogn)<inline-graphic></inline-graphic>-size universal point set in two distinct cases, namely when k=2<inline-graphic></inline-graphic> (2-outerplanar graphs) and when k is unbounded but each outerplanarity level is restricted to be a simple cycle (simply-nested graphs). [ABSTRACT FROM AUTHOR]