Charles Explorer logo
🇬🇧

Universal Point Sets for Planar Three-Trees

Publication at Faculty of Mathematics and Physics |
2013

Abstract

For every n ∈ N, we present a set S(n) of O ( n^ 5 / 3 ) points in the plane such that every planar 3-tree with n vertices has a straight-line embedding in the plane in which the vertices are mapped to a subset of S(n). This is the first subquadratic upper bound on the size of universal point sets for planar 3-trees, as well as for the class of 2-trees and serial parallel graphs