Saturated 2-plane drawings with few edges. (English) Zbl 1539.05105
Summary: A drawing of a graph is \(k\)-plane if every edge contains at most \(k\) crossings. A \(k\)-plane drawing is saturated if we cannot add any edge so that the drawing remains \(k\)-plane. It is well-known that saturated 0-plane drawings, that is, maximal plane graphs, of \(n\) vertices have exactly \(3n - 6\) edges. For \(k > 0\), the number of edges of saturated \(n\)-vertex \(k\)-plane graphs can take many different values. In this note, we establish some bounds on the minimum number of edges of saturated 2-plane graphs under various conditions.
MSC:
| 05C62 | Graph representations (geometric and intersection representations, etc.) |
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 05C35 | Extremal problems in graph theory |
References:
| [1] | C. Auer, F. J. Brandenburg, A. Gleißner and K. Hanauer, On sparse maximal 2-planar graphs, in: W. Didimo and M. Patrignani (eds.), Graph Drawing, Springer Berlin Heidelberg, Berlin, Heidelberg, 2013 pp. 555-556. |
| [2] | J. Barát and G. Tóth, Improvements on the density of maximal 1-planar graphs, J. Graph Theory 88 (2018), 101-109, doi:10.1002/jgt.22187, https://doi.org/10.1002/jgt.22187. · Zbl 1391.05151 · doi:10.1002/jgt.22187 |
| [3] | F. J. Brandenburg, D. Eppstein, A. Gleißner, M. T. Goodrich, K. Hanauer and J. Reislhu-ber, On the density of maximal 1-planar graphs, in: Graph drawing. 20th international sym-posium, GD 2012, Redmond, WA, USA, Springer, Berlin, pp. 327-338, 2013, doi:10.1007/ 978-3-642-36763-2 29, https://doi.org/10.1007/978-3-642-36763-2_29. · Zbl 1377.68165 · doi:10.1007/978-3-642-36763-2_29 |
| [4] | S. Chaplick, F. Klute, I. Parada, J. Rollin and T. Ueckerdt, Edge-minimum saturated k-planar drawings, 2021, arXiv:2012.08631 [math.CO]. |
| [5] | F. Klute and I. Parada, Saturated k-plane drawings with few edges, 2021, arXiv:2012.02281 [math.CO]. |
| [6] | J. Pach and G. Tóth, Graphs drawn with few crossings per edge, Combinatorica 17 (1997), 427-439, doi:10.1007/bf01215922, https://doi.org/10.1007/bf01215922. · Zbl 0902.05017 · doi:10.1007/bf01215922 |
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.
