A note on universal point sets for planar graphs. (English) Zbl 1447.05065
Summary: 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 M. Kurowski [Inf. Process. Lett. 92, No. 2, 95–98 (2004; Zbl 1183.68430)].
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 J. Cardinal et al. [J. Graph Algorithms Appl. 19, No. 1, 529–547 (2015; Zbl 1323.05038)], that all planar graphs on \(n \leq 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 \geq 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 P. Brass et al. [Comput. Geom. 36, No. 2, 117–130 (2007; Zbl 1105.05015)].
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 J. Cardinal et al. [J. Graph Algorithms Appl. 19, No. 1, 529–547 (2015; Zbl 1323.05038)], that all planar graphs on \(n \leq 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 \geq 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 P. Brass et al. [Comput. Geom. 36, No. 2, 117–130 (2007; Zbl 1105.05015)].
MSC:
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 05C30 | Enumeration in graph theory |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 68R10 | Graph theory (including graph drawing) in computer science |
Online Encyclopedia of Integer Sequences:
Number of simplicial polyhedra with n vertices; simple planar graphs with n vertices and 3n-6 edges; maximal simple planar graphs with n vertices; planar triangulations with n vertices; triangulations of the sphere with n vertices; 3-connected cubic planar graphs on 2n-4 vertices.Number of inequivalent ways of dissecting a regular (n+2)-gon into n triangles by n-1 non-intersecting diagonals under rotations and reflections; also the number of (unlabeled) maximal outerplanar graphs on n+2 vertices.
Number of simple arrangements of n pseudolines in the projective plane with a marked cell. Number of Euclidean pseudo-order types: nondegenerate abstract order types of configurations of n points in the plane.
Number of 4-connected simplicial polyhedra with n nodes.
The number of Apollonian networks (planar 3-trees) with n+3 vertices.
References:
| [1] | IBM ILOG CPLEX Optimization Studio, 2018. |
| [2] | O. Aichholzer.Enumerating Order Types for Small Point Sets with Applications. · Zbl 1027.68127 |
| [3] | O. Aichholzer, F. Aurenhammer, and H. Krasser.Enumerating Order Types for Small Point Sets with Applications.Order, 19(3):265-281, 2002. · Zbl 1027.68127 · doi:10.1023/A:1021231927255 |
| [4] | O. Aichholzer and H. Krasser. Abstract Order Type Extension and New Results on the Rectilinear Crossing Number.Computational Geometry: Theory and Applications, 36(1):2-15, 2006. · Zbl 1110.65019 · doi:10.1016/j.comgeo.2005. |
| [5] | P. Angelini, T. Bruckdorfer, G. Di Battista, M. Kaufmann, T. Mchedlidze, V. Roselli, and C. Squarcella. Small universal point sets for k-outerplanar graphs.Discrete & Computational Geometry, pages 1-41, 2018. · Zbl 1398.05068 |
| [6] | M. Balko, R. Fulek, and J. Kynˇcl. Crossing Numbers and Combinatorial Characterization of Monotone Drawings ofKn.Discrete & Computational Geometry, 53(1):107-143, 2015. · Zbl 1307.05058 · doi:10.1007/s00454-014-9644-z |
| [7] | M. J. Bannister, Z. Cheng, W. E. Devanny, and D. Eppstein. Superpatterns and Universal Point Sets.Journal of Graph Algorithms and Applications, 18(2):177-209, 2014. · Zbl 1290.05142 · doi:10.7155/jgaa.00318 |
| [8] | F. J. Brandenburg. Drawing planar graphs on89n2area.Electronic Notes in Discrete Mathematics, 31:37-40, 2008. · Zbl 1267.05173 · doi:10.1016/j.endm.2008.06. |
| [9] | P. Brass, E. Cenek, C. A. Duncan, A. Efrat, C. Erten, D. P. Ismailescu, S. G. Kobourov, A. Lubiw, and J. S. Mitchell. On simultaneous planar graph embeddings.Computational Geometry, 36(2):117-130, 2007. · Zbl 1105.05015 |
| [10] | G. Brinkmann and B. D. McKay. Fast generation of some classes of planar graphs.Electronic Notes in Discrete Mathematics, 3:28-31, 1999. · Zbl 1039.05531 |
| [11] | S. Cabello. Planar embeddability of the vertices of a graph using a fixed point set is NP-hard.Journal of Graph Algorithms and Applications, 10(2):353-363, 2006. · Zbl 1161.68645 · doi:10.7155/jgaa.00132 |
| [12] | J. Cardinal, M. Hoffmann, and V. Kusters. On Universal Point Sets for Planar Graphs.Journal of Graph Algorithms and Applications, 19(1):529- 547, 2015. · Zbl 1323.05038 · doi:10.7155/jgaa.00374 |
| [13] | N. Casta˜neda and J. Urrutia. Straight Line Embeddings of Planar Graphs on Point Sets. InProceedings of the 8th Canadian Conference on Computational Geometry (CCCG’96), pages 312-318, 1996. |
| [14] | A. Choi, M. Chrobak, and K. Costello. An Ω(n2) Lower Bound for Random Universal Sets for Planar Graphs. 2019. |
| [15] | M. Chrobak and H. J. Karloff. A Lower Bound on the Size of Universal Sets for Planar Graphs.ACM SIGACT News, 20(4):83-86, 1989. |
| [16] | H. De Fraysseix, J. Pach, and R. Pollack. How to draw a planar graph on a grid.Combinatorica, 10(1):41-51, 1990. · Zbl 0728.05016 · doi:10.1007/BF02122694 |
| [17] | N. E´en and N. S¨orensson.An extensible SAT-solver.InProceedings of Theory and Applications of Satisfiability Testing - SAT 2003, volume 2919 ofLNCS, pages 502-518. Springer, 2003. · Zbl 1204.68191 · doi:10.1007/ |
| [18] | S. Felsner and J. E. Goodman.Pseudoline Arrangements.In Toth, O’Rourke, and Goodman, editors,Handbook of Discrete and Computational Geometry. CRC Press, 3 edition, 2018. · doi:10.1201/9781315119601 |
| [19] | S. Felsner and H. Weil. Sweeps, Arrangements and Signotopes.Discrete Applied Mathematics, 109(1):67-94, 2001. · Zbl 0967.68159 · doi:10.1016/S0166-218X(00) |
| [20] | R. Fulek and C. D. T´oth. Universal point sets for planar three-trees.Journal of Discrete Algorithms, 30:101-112, 2015. · Zbl 1320.68212 · doi:10.1016/j.jda.2014.12. |
| [21] | Gurobi Optimization, LLC. Gurobi Optimizer, 2018. |
| [22] | H. Krasser.Order Types of Point Sets in the Plane. PhD thesis, Institute for Theoretical Computer Science, Graz University of Technology, Austria, 2003. |
| [23] | M. Kurowski. A 1.235nlower bound on the number of points needed to draw alln-vertex planar graphs.Information Processing Letters, 92(2):95- 98, 2004. · Zbl 1183.68430 · doi:10.1016/j.ipl.2004.06.009 |
| [24] | B. D. McKay and A. Piperno. Practical graph isomorphism, II.Journal of Symbolic Computation, 60:94-112, 2014. · Zbl 1394.05079 · doi:10.1016/j.jsc.2013.09. |
| [25] | T. M. Moosa and M. Sohel Rahman. Improved algorithms for the point-set embeddability problem for plane 3-trees. InComputing and Combinatorics, pages 204-212, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg. · Zbl 1353.68215 |
| [26] | R. I. Nishat, D. Mondal, and M. S. Rahman. Point-set embeddings of plane 3-trees. InGraph Drawing, volume 6502 ofLNCS, pages 317-328. Springer, 2011. · Zbl 1314.68236 · doi:10.1007/978-3-642-18469-7_29 |
| [27] | J. Pach, P. Gritzmann, B. Mohar, and R. Pollack. Embedding a planar triangulation with vertices at specified points.American Mathematical Monthly, 98:165-166, 1991. · doi:10.2307/2323956 |
| [28] | M. Scheucher. Webpage: Source Codes and Data for Universal Point Sets. |
| [29] | M. Scheucher.On Order Types, Projective Classes, and Realizations. Bachelor’s thesis, Graz University of Technology, Austria, 2014. |
| [30] | M. Scheucher, H. Schrezenmaier, and R. Steiner.A Note On Universal Point Sets for Planar Graphs.InProc. 35th European Workshop on Computational Geometry (EuroCG’19), pages 21:1-21:9, 2019. URL: |
| [31] | M. Scheucher, H. Schrezenmaier, and R. Steiner.A Note On Universal Point Sets for Planar Graphs.InGraph Drawing and Network Visualization, volume 11904 ofLNCS, pages 350-362. Springer, 2019. · Zbl 1539.68234 |
| [32] | W. Schnyder. Embedding Planar Graphs on the Grid. InProceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, pages 138-148. Society for Industrial and Applied Mathematics, 1990. · Zbl 0786.05029 |
| [33] | W. A. Stein et al.Sage Mathematics Software (Version 8.1). The Sage Development Team, 2018. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
