Universal Point Sets for Planar Three-Trees

DOI10.1007/978-3-642-40104-6_30zbMATH Open1390.68500arXiv1212.6148OpenAlexW1883860785MaRDI QIDQ2842172

Radoslav Fulek, Csaba D. Tóth

Publication date: 12 August 2013

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: For every $ninmathbbN$, we present a set $S_n$ of $O(n^{3/2}logn)$ 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.

Full work available at URL: https://arxiv.org/abs/1212.6148

zbMATH Keywords

universal point setstraight-line embeddingplanar 3-tree

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items (1)

Universal point sets for planar three-trees

This page was built for publication: Universal Point Sets for Planar Three-Trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2842172)