Home  Issues  About JGAA  Instructions for Authors 
DOI: 10.7155/jgaa.00529
A Note on Universal Point Sets for Planar Graphs
Vol. 24, no. 3, pp. 247267, 2020. Regular paper.
Abstract We investigate which planar point sets allow
simultaneous straightline embeddings of all planar graphs on a fixed number of vertices.
We first show that at least $(1.293o(1))n$ points are required
to find a straightline 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 11vertex graphs can be simultaneously drawn plane straightline.
This strengthens the result by Cardinal, Hoffmann, and Kusters (2015),
that all planar graphs on $n \le 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 \ge 15$.
We also provide 49 planar 11vertex 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).

Submitted: September 2019.
Reviewed: March 2020.
Revised: March 2020.
Accepted: April 2020.
Final: April 2020.
Published: April 2020.
Communicated by
Stephen G. Kobourov

Journal Supporters
