ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 24 (2024) #P1.05
https://doi.org/10.26493/1855-3974.2805.b49
(Also available at http://amc-journal.eu)
Saturated 2-plane drawings with few edges
János Barát *
Department of Mathematics, University of Pannonia and
Alfréd Rényi Institute of Mathematics, Budapest, Hungary
Géza Tóth †
Alfréd Rényi Institute of Mathematics, Budapest, Hungary
Received 12 January 2022, accepted 24 May 2023, published online 18 August 2023
Abstract
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.
Keywords: Saturated drawing, 2-planar, graphs, discharging.
Math. Subj. Class. (2020): 05C10, 05C35
*Corresponding author. Supported by NKFIH grant K-131529 and ERC Advanced Grant “GeoScape”
No. 882971.
†Supported by NKFIH grant K-131529 and ERC Advanced Grant “GeoScape” No. 882971.
E-mail addresses: barat@mik.uni-pannon.hu (János Barát), toth.geza@renyi.mta.hu (Géza Tóth)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
ISSN 1855-3966 (tiskana izd.), ISSN 1855-3974 (elektronska izd.)
ARS MATHEMATICA CONTEMPORANEA 24 (2024) #P1.05
https://doi.org/10.26493/1855-3974.2805.b49
(Dostopno tudi na http://amc-journal.eu)
Nasičene 2-ravninske risbe z malo povezavami
János Barát *
Department of Mathematics, University of Pannonia and
Alfréd Rényi Institute of Mathematics, Budapest, Hungary
Géza Tóth †
Alfréd Rényi Institute of Mathematics, Budapest, Hungary
Prejeto 12. januarja 2022, sprejeto 24. maja 2023, objavljeno na spletu 18. avgusta 2023
Povzetek
Risba grafa je k-ravninska, če vsaka povezava vsebuje največ k presečišč. k-ravninska
risba je nasičena, če ne moremo dodati nobene povezave, tako da bi risba ostala k-ravninska.
Dobro znano je, da imajo nasičene 0-ravninske risbe – maksimalni ravninski grafi na n vo-
zliščih – natančno 3n−6 povezav. Za k > 0 lahko število povezav nasičenih n-vozliščnih
k-ravninskih grafov zavzame mnogo različnih vrednosti. V tem prispevku določimo nekate-
re meje minimalnega števila povezav nasičenih 2-ravninskih grafov pri različnih pogojih.
Ključne besede: Nasičena risba, 2-ravninski, grafi, praznjenje.
Math. Subj. Class. (2020): 05C10, 05C35
*Kontaktni avtor. Podprt z NKFIH dotacijo K-131529 in s sredstvi ERC Advanced Grant “GeoScape”
št. 882971.
†Podprt s strani NKFIH dotacijo K-131529 in s sredstvi ERC Advanced Grant “GeoScape” št. 882971.
E-poštna naslova: barat@mik.uni-pannon.hu (János Barát), toth.geza@renyi.mta.hu (Géza Tóth)
cb To delo je objavljeno pod licenco https://creativecommons.org/licenses/by/4.0/