Small Point Sets for Simply-Nested Planar Graphs

Angelini, Patrizio and Di Battista, Giuseppe and Kaufmann, Michael and Mchedlidze, Tamara and Roselli, Vincenzo and Squarcella, Claudio (2012) Small Point Sets for Simply-Nested Planar Graphs. In: Graph Drawing 19th International Symposium, GD 2011, September 21-23, 2011 , pp. 75-85(Official URL: 10.1007/978-3-642-25878-7_8).

Full text not available from this repository.


A point set P ⊆ R2 is universal for a class G if every graph of G has a planar straight-line embedding into P. We prove that there exists a log n O(n( log log n )2 ) size universal point set for the class of simply-nested n-vertex planar graphs. This is a step towards a full answer for the well-known open problem on the size of the smallest universal point sets for planar graphs.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-642-25878-7_8
Classifications: G Algorithms and Complexity > G.490 Embeddings
M Methods > M.600 Planar

Actions (login required)

View Item View Item