On Universal Point Sets for Planar Graphs
Vol. 19, no. 1, pp. 529-547, 2015. Regular paper.
Abstract A set P of points in R2 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 ≥ 15. Conversely, we use a computer program to show that there exist universal point sets for all n ≤ 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.
Submitted: November 2014.
Reviewed: June 2015.
Revised: August 2015.
Reviewed: October 2015.
Revised: October 2015.
Accepted: October 2015.
Final: October 2015.
Published: October 2015.
Communicated by Stephen G. Kobourov
article (PDF)