2012/09/17 by Jean Cardinal, Cardinal, Jean, Michael M. Hoffmann +3 · 1 citation
Computer Science · Engineering · #Computational Geometry and Mesh Generation #3D Modeling in Geospatial Applications #Structural Analysis and Optimization
paper · pdf · doi:10.48550/arxiv.1209.3594
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.