Geodesic
A Note on Universal Point Sets for Planar Graphs
Journal of Graph Algorithms and Applications, Tome 24 (2020) no. 3, pp. 247-267.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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).
DOI : 10.7155/jgaa.00529
Keywords: simultaneously embedded, stacked triangulation, order type, boolean satisfiability (SAT), integer programming (IP) 
@article{JGAA_2020_24_3_a5,
     author = {Manfred  Scheucher and Hendrik Schrezenmaier and Raphael Steiner},
     title = {A {Note} on {Universal} {Point} {Sets} for {Planar} {Graphs}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {247--267},
     publisher = {mathdoc},
     volume = {24},
     number = {3},
     year = {2020},
     doi = {10.7155/jgaa.00529},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00529/}
}
TY  - JOUR
AU  - Manfred  Scheucher
AU  - Hendrik Schrezenmaier
AU  - Raphael Steiner
TI  - A Note on Universal Point Sets for Planar Graphs
JO  - Journal of Graph Algorithms and Applications
PY  - 2020
SP  - 247
EP  - 267
VL  - 24
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00529/
DO  - 10.7155/jgaa.00529
LA  - en
ID  - JGAA_2020_24_3_a5
ER  - 
%0 Journal Article
%A Manfred  Scheucher
%A Hendrik Schrezenmaier
%A Raphael Steiner
%T A Note on Universal Point Sets for Planar Graphs
%J Journal of Graph Algorithms and Applications
%D 2020
%P 247-267
%V 24
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00529/
%R 10.7155/jgaa.00529
%G en
%F JGAA_2020_24_3_a5
Manfred  Scheucher; Hendrik Schrezenmaier; Raphael Steiner. A Note on Universal Point Sets for Planar Graphs. Journal of Graph Algorithms and Applications, Tome 24 (2020) no. 3, pp. 247-267. doi : 10.7155/jgaa.00529. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00529/

Cité par Sources :