A Note on Universal Point Sets for Planar Graphs

摘要

We investigate which planar point sets allow simultaneous straight-line embeddings of all planar graphs on a fixed number of vertices. We first show that at least (1.293 — o(1))n points are required to find a straight-line drawing of each n-vertex planar graph (vertices are drawn as the given points); this improves the previous best constant 1.235 by Kurowski (2004). Our second main result is based on exhaustive computer search: We show that no set of 11 points exists, on which all planar 11-vertex graphs can be simultaneously drawn plane straight-line. This strengthens the result by Cardinal, Hoffmann, and Kusters (2015), that all planar graphs on n ≤ 10 vertices can be simultaneously drawn on particular n-universal sets of n points while there are no n-universal sets of size n for n > 15. We also provide 49 planar 11-vertex graphs which cannot be simultaneously drawn on any set of 11 points. This, in fact, is another step towards a (negative) answer of the question, whether every two planar graphs can be drawn simultaneously - a question raised by Brass, Cenek, Duncan, Efrat, Erten, Ismailescu, Kobourov, Lubiw, and Mitchell (2007).