A Note on Universal Point Sets for Planar Graphs
From MaRDI portal
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 points are required to find a straight-line drawing of each -vertex planar graph (vertices are drawn as the given points); this improves the previous best constant 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 vertices can be simultaneously drawn on particular `universal' sets of points while there are no universal sets for . Moreover, we provide a set of 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).
Recommendations
- A note on universal point sets for planar graphs
- On universal point sets for planar graphs
- On universal point sets for planar graphs
- Universal point subsets for planar graphs
- A universal point set for 2-outerplanar graphs
- On point-sets that support planar graphs
- On point-sets that support planar graphs
- Universal Sets of n Points for 1-Bend Drawings of Planar Graphs with n Vertices
- Universal sets of \(n\) points for one-bend drawings of planar graphs with \(n\) vertices
- Small universal point sets for \(k\)-outerplanar graphs
Cites work
- scientific article; zbMATH DE number 432759 (Why is no real title available?)
- A 1.235 lower bound on the number of points needed to draw alln-vertex planar graphs
- A note on universal point sets for planar graphs
- Abstract order type extension and new results on the rectilinear crossing number
- Crossing numbers and combinatorial characterization of monotone drawings of \(K_n\)
- Drawing planar graphs on \(\frac{8}{9}n^2\) area
- Enumerating order types for small point sets with applications
- Fast generation of some classes of planar graphs
- How to draw a planar graph on a grid
- Improved algorithms for the point-set embeddability problem for plane 3-trees
- On simultaneous planar graph embeddings
- On universal point sets for planar graphs
- Planar embeddability of the vertices of a graph using a fixed point set is NP-hard
- Point-set embeddings of plane 3-trees (extended abstract)
- Practical graph isomorphism. II.
- Small universal point sets for \(k\)-outerplanar graphs
- Superpatterns and universal point sets
- Sweeps, arrangements and signotopes
- Theory and Applications of Satisfiability Testing
- Universal point sets for planar three-trees
Cited in
(16)- A 1.235 lower bound on the number of points needed to draw alln-vertex planar graphs
- Universal point sets for planar three-trees
- Universal sets of \(n\) points for one-bend drawings of planar graphs with \(n\) vertices
- An exponential bound for simultaneous embeddings of planar graphs
- On universal point sets for planar graphs
- On universal point sets for planar graphs
- Coloring circle arrangements: new 4-chromatic planar graphs
- A logarithmic bound for simultaneous embeddings of planar graphs
- On universal graphs for planar oriented graphs of a given girth
- Discrete geometry. Abstracts from the workshop held January 21--26, 2024
- A logarithmic bound for simultaneous embeddings of planar graphs
- Universal Point Sets for Drawing Planar Graphs with Circular Arcs
- A universality theorem for stressable graphs in the plane
- Proximity in triangulations and quadrangulations
- Universal geometric graphs
- Topological Drawings Meet Classical Theorems from Convex Geometry
This page was built for publication: A Note on Universal Point Sets for Planar Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5119378)
