Edge densities of drawings of graphs with one forbidden cell
Benedikt Hahn, Torsten Ueckerdt, Birgit Vogtenhuber · 2025
Read Edge densities of drawings of graphs with one forbidden cell by Benedikt Hahn, Torsten Ueckerdt, Birgit Vogtenhuber (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-16368.txt.
Introduction
Drawings of graphs that avoid one cell type have bounded edge density, Benedikt Hahn, Torsten Ueckerdt, and Birgit Vogtenhuber study in a 2025 paper. A topological drawing divides the plane into cells, and each cell has a type given by the cyclic sequence of crossings and vertices along its boundary. Forbidding one such type restricts how edges can be arranged in the plane.
Earlier work showed that drawings without a certain triangular cell have at most a linear number of edges, and that the bound is tight. The authors initiate the study of drawings that avoid any one fixed cell type. They consider non-homotopic and simple drawings, multigraphs and simple graphs, and every possible cell type. Upper and lower bounds on the maximum edge count are given for each combination.
Catalog record
| CREATOR | Benedikt Hahn, Torsten Ueckerdt, Birgit Vogtenhuber |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 46 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-16368
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Edge densities of drawings of graphs with one forbidden cell Benedikt Hahn, Torsten Ueckerdt, Birgit Vogtenhuber Abstract A connected topological drawing of a graph divides the plane into a number of cells. The type of a cell c c is the cyclic sequence of crossings and vertices along the boundary walk of c c . For example, all triangular cells with three incident crossings and no incident vertex share the same cell type. When a non-homotopic drawing of an n n -vertex multigraph G G does not contain any such cells, Ackerman and Tardos [JCTA 2007] proved that G G has at most 8 n − 20 8n-20 edges, while Kaufmann, Klemz, Knorr, Reddy, Schröder, and Ueckerdt [GD 2024] showed that this bound is tight. In this paper, we initiate the in-depth study of non-homotopic drawings that do not contain one fixed cell type 𝔠 \mathfrak{c} , and investigate the edge density of the corresponding multigraphs, i.e., the maximum possible number of edges. We consider non-homotopic as well as simple drawings, multigraphs as well as simple graphs, and every possible type of cell. For every combination of drawing style, graph type, and cell type, we give upper and lower bounds on the corresponding edge density. With the exception of the cell type with four incident crossings and no incident vertex, we show for every cell type 𝔠 \mathfrak{c} that the edge density of n n -vertex (multi)graphs with 𝔠 \mathfrak{c} -free drawings is either quadratic in n n or linear in n n . In most cases, our bounds are tight up to an additive constant. Additionally, we improve the current lower bound on the edge density of simple graphs that admit a non-homotopic quasiplanar drawing from 7 n − 28 7n-28 to 7.5 n − 28 7.5n-28 . Graz University of Technology, [email protected]://orcid.org/0009-0004-2325-6997This research was funded in whole or in part by the Austrian Science Fund (FWF) 10.55776/DOC183. Karlsruhe Institute of Technology, [email protected]://orcid.org/0000-0002-0645-9715funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – 520708409. Graz University of Technology, [email protected]://orcid.org/0000-0002-7166-4467This research was funded in whole or in part by the Austrian Science Fund (FWF) 10.55776/DOC183. ccs Mathematics of computing Graph theory ccs Mathematics of computing Graphs and surfaces ccs Mathematics of computing Extremal graph theory keywords Edge density, cell types, forbidden substructures, non-homotopic drawings, simple drawings † † runningauthor: Benedikt Hahn, Torsten Ueckerdt, and Birgit Vogtenhuber † † copyright: Benedikt Hahn, Torsten Ueckerdt, and Birgit Vogtenhuber † † editors: Vida Dujmović and Fabrizio Montecchiani † † event-title: 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025) † † event-shorttitle: GD 2025 † † event-acronym: GD † † year: 2025 † † event-date: September 24–26, 2025 † † event-location: Norrköping, Sweden † † series-volume: 357 † † articleno: 31 1 Introduction Many fundamental classes of graphs are defined by admitting a drawing without a forbidden configuration or pattern. This includes planar graphs (forbidding two crossing edges), as well as many beyond-planar graph classes such as k -planar graphs (forbidding an edge with k+1 crossings), quasiplanar graphs (forbidding three pairwise crossing edges), fan planar graphs (forbidding an edge crossed by two independent edges 1 1 1 The actual definition is more complex but irrelevant here. ) and many others. Planar and beyond-planar graphs are of eminent importance, both from a practical and a theoretical point of view. Nevertheless, many fundamental properties are still not sufficiently well understood. One of the most fundamental questions in this area concerns the edge density of a beyond-planar graph class \mathcal{G} , that is, the maximum possible number of edges of any n -vertex graph in \mathcal{G} . There is a long history of edge density results ranging from k -planar graphs [ 21 , 20 , 2 ] , k -quasiplanar graphs [ 3 , 1 ] , k -bend RAC graphs [ 8 , 4 ] , (k,l) -grid free graphs [ 19 ] , and more to the recently introduced Density Formula [ 16 ] . We study the cells of a drawing, that is, the regions of \mathbb{R}^{2} delimited by the vertices and edges of the drawing. The type of a cell c is the cyclic order of edge segments, vertices, and crossings along the boundary of c . For example, a -cell is incident to three edge segments, three crossings, and no vertex. Distinguishing cells by their type is often useful when reasoning about drawings. The recently developed Density Formula [ 16 ] , whose many applications usually come down to counting and relating different cell types in drawings, has further increased the need for a good grasp on the relation between types of cells in a drawing and the structure of the underlying graph. Interestingly, Ackerman and Tardos [ 3 ] proved already in 2007 that n -vertex drawings with no -cell contain at most 8n-20 edges. Our contribution. In this paper, we consider for each cell type \mathfrak{c} the corresponding beyond-planar graph class \mathcal{G}_{\mathfrak{c}} consisting of all graphs that admit a drawing without \mathfrak{c} -cells. We present upper and lower bounds on the edge densities of graphs in \mathcal{G}_{\mathfrak{c}} . We determine the asymptotic edge density in the setting of arbitrary, non-homotopic, and simple drawings, except for one particular cell type. Depending on \mathfrak{c} , we obtain some linear and some quadratic edge densities. In many cases, our bounds are tight up to an additive constant. All our results and some previous related work are shown in table 1 . Our lower bounds entail various novel constructions, while our upper bounds are mostly proved via discharging. Additionally, we present a construction of simple graphs on 7.5n-28 edges that admit a non-homotopic quasiplanar drawing, beating a previous lower bound by \frac{n}{2} in the highest-order term. Forbidden cell Graph type Drawing type Lower Bound Upper Bound Any Simple No restriction 3 \binom{n}{2} \binom{n}{2} \multirow 3*[-1.6em] -cell Multi Non-homotopic [ 16 ] 8n-20 [ 3 ] 8n-20 Simple Non-homotopic 8 8n-28 [ 3 ] 8n-20 - Simple 6 7n-30 theorem 5 7n-20 \multirow 3*[-1.6em] -cell Multi Non-homotopic 5 9n-18 - Simple Non-homotopic 4 6n-12 \binom{n}{2} - Simple 4 6n-12 \binom{n}{2} -cell - Simple 9 \Omega(n^{2}) \binom{n}{2} \multirow 2*[-0.8em] -cell Multi Non-homotopic 4 6n-12 theorem 4 6n-12 - Simple 4 6n-12 theorem 4 6n-12 Others - Simple 1 \binom{n}{2} \binom{n}{2} Table 1: Results on edge densities of graphs admitting a drawing without one fixed type of cell. Upper bounds hold for all n\geq 3 , while lower bounds are proven for infinitely many values of n . Related work. Apart from the above-mentioned work of Ackerman and Tardos [ 3 ] and Kaufmann, Klemz, Knorr, Reddy, Schröder, and Ueckerdt [ 16 ] on -free drawings, we are (as far as we know) the first to consider graph drawings with a forbidden type of cell. However, some beyond-planar drawing styles are characterized by forbidding a configuration that is somewhat similar to a particular cell type. For example, in a fan-crossing-free drawing [ 7 ] there is no edge crossed by two adjacent edges, which resembles the -cell. Secondly, in a quasiplanar drawing, there are no three pairwise crossing edges, which resembles the -cell. And in a (2,2) -grid-free drawing, there are