Universal point sets for planar three-tree

2012/12/26 by Radoslav Fulek, Csaba D. Tóth, Fulek, Radoslav +1
Computer Science · Engineering · #Advanced Numerical Analysis Techniques #Combinatorics (math.CO) #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Digital Image Processing Techniques #FOS: Computer and information sciences #FOS: Mathematics

paper · pdf · doi:10.48550/arxiv.1212.6148

openalex publication_date 2012/12/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

For every n∈ ℕ, we present a set S_n of O(n^3/2log n) 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.

Related

• On Universal Point Sets for Planar Graphs
• Linear Size Universal Point Sets for Classes of Planar Graphs
• Subgraph-universal planar graphs for trees
• A Note On Universal Point Sets for Planar Graphs
• A Universal Point Set for 2-Outerplanar Graphs