Saturated 2-plane drawings with few edges
DOI:
https://doi.org/10.26493/1855-3974.2805.b49Keywords:
Saturated drawing, 2-planar, graphs, dischargingAbstract
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.
Downloads
Published
2023-08-18
Issue
Section
Articles
License
Articles in this journal are published under Creative Commons Attribution 4.0 International License
https://creativecommons.org/licenses/by/4.0/