1. Small Universal Point Sets for k-Outerplanar Graphs.
- Author
-
Angelini, Patrizio, Bruckdorfer, Till, Di Battista, Giuseppe, Kaufmann, Michael, Mchedlidze, Tamara, Roselli, Vincenzo, and Squarcella, Claudio
- Subjects
POINT set theory ,PLANAR graphs ,EMBEDDINGS (Mathematics) ,GEOMETRIC vertices ,INTEGERS - Abstract
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(nlogn) -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). [ABSTRACT FROM AUTHOR] - Published
- 2018
- Full Text
- View/download PDF