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. 247-267, 2020. Regular paper.
Abstract 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 \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 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).
|
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
|