Small Universal Point Sets for k-Outerplanar Graphs

A point set S⊆ R2 is universal for a class G of planar graphs if every graph of G has a planar straight-line embedding on S. 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(nlog n) -size universal point set in two distinct cases, namely when k= 2 (2-outerplanar graphs) and when k is unbounded but each outerplanarity level is restricted to be a simple cycle (simply-nested graphs).