universal set

Universal point sets for planar graphs ★★★

Author(s): Mohar

We say that a set $P \subseteq {\mathbb R}^2$ is $n$-\emph{universal} if every $n$ vertex planar graph can be drawn in the plane so that each vertex maps to a distinct point in $P$, and all edges are (non-intersecting) straight line segments.

\begin{question} Does there exist an $n$-universal set of size $O(n)$? \end{question}

Keywords: geometric graph; planar graph; universal set

Syndicate content