9-13 June 2013
Koper, Slovenia
UTC timezone
Home > Timetable > Contribution details

On Universal Point Sets and Simultaneous Geometric Embeddings

Presented by Michael HOFFMANN
Type: Oral presentation
Track: Discrete and Computational Geometry


A set $P$ of points in $R^2$ is $n$-universal, if every planar graph on $n$ vertices admits a plane straight-line embedding on $P$. Answering a question by Kobourov, we show that there is no $n$-universal point set of size $n$, for any $n\ge 15$. Conversely, we use a computer program to show that there exist universal point sets for all $n\le 10$ and to enumerate all corresponding order types. Finally, we describe a collection $G$ of $7'393$ planar graphs on $35$ vertices that do not admit a simultaneous geometric embedding without mapping, that is, no set of $35$ points in the plane supports a plane straight-line embedding of all graphs in $G$. (Joint work with Jean Cardinal and Vincent Kusters.)


Location: Koper, Slovenia

Primary authors