2015/08/24 by Angelini, Patrizio, Bruckdorfer, Till, Kaufmann, Michael +1
#05C10 #Computational Geometry (cs.CG) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1508.05784
A point set S ⊆ ℝ2 is universal for a class \cal G if every graph of \cal 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 sub-quadratic universal point set for them is one of the most fascinating open problems in Graph Drawing. Motivated by the fact that outerplanarity is a key property for the existence of small universal point sets, we study 2-outerplanar graphs and provide for them a universal point set of size O(n log n).