Linear Size Universal Point Sets for Classes of Planar Graphs

arXiv2303.00109MaRDI QIDQ6427982FDOQ6427982

Authors: Stefan Felsner, Hendrik Schrezenmaier, Felix Schröder, Raphael Steiner 

Publication date: 28 February 2023

Abstract: A finite set $P$ of points in the plane is $n$-universal with respect to a class $mathcalC$ of planar graphs if every $n$-vertex graph in $mathcalC$ admits a crossing-free straight-line drawing with vertices at points of $P$. For the class of all planar graphs the best known upper bound on the size of a universal point set is quadratic and the best known lower bound is linear in $n$. Some classes of planar graphs are known to admit universal point sets of near linear size, however, there are no truly linear bounds for interesting classes beyond outerplanar graphs. In this paper, we show that there is a universal point set of size $2n-2$ for the class of bipartite planar graphs with $n$ vertices. The same point set is also universal for the class of $n$-vertex planar graphs of maximum degree $3$. The point set used for the results is what we call an exploding double chain, and we prove that this point set allows planar straight-line embeddings of many more planar graphs, namely of all subgraphs of planar graphs admitting a one-sided Hamiltonian cycle. The result for bipartite graphs also implies that every $n$-vertex plane graph has a $1$-bend drawing all whose bends and vertices are contained in a specific point set of size $4n-6$, this improves a bound of $6n-10$ for the same problem by L"offler and T'oth.

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10)

This page was built for publication: Linear Size Universal Point Sets for Classes of Planar Graphs

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