Edge densities of drawings of graphs with one forbidden cell

Imagine you are an architect designing a city on a giant, flat piece of paper. In this city, the roads are the edges of a graph, and the intersections are the vertices. Sometimes, roads cross each other (like a bridge over a river or an overpass), creating a complex web.

When you draw this city, the roads and bridges divide the paper into different neighborhoods or cells. Some neighborhoods are small triangles, some are big squares, and some are weird, jagged shapes.

This paper is about a very specific rule: What happens if we forbid one specific type of neighborhood from existing in our city?

The authors ask: "If we say, 'No triangular neighborhoods allowed,' or 'No square neighborhoods allowed,' how many roads can we still build before the city becomes too crowded?"

Here is the breakdown of their findings, using simple analogies:

1. The "Forbidden Neighborhood" Game

In math, a "cell" is just a space surrounded by lines. The "type" of a cell is defined by how many times the roads cross each other and how many city blocks (vertices) touch its border.

The Old Rule: Scientists already knew that if you forbid a specific "triangular" neighborhood (one with three crossings and no city blocks), you can't build more than about 8 roads per city block.
The New Game: This paper asks: What if we forbid any shape? What if we ban the "4-crossing square" or the "5-crossing pentagon"? How many roads can we fit then?

2. The Two Main Findings

A. The "Linear" vs. "Superlinear" Divide

The authors discovered that the answer depends entirely on the shape you ban.

The "Linear" City (The Boring but Safe Zone): For most forbidden shapes, the number of roads you can build grows slowly (linearly). If you have 100 blocks, you can build roughly 800 roads. If you have 1,000 blocks, you can build 8,000 roads. The city stays manageable.
The "Superlinear" City (The Chaos Zone): For a few specific shapes (like the "4-crossing square"), the rules change completely. You can build a massive number of roads—so many that the number of roads grows much faster than the number of blocks. It's like going from a small town to a sprawling metropolis where the road network explodes in complexity.

B. The "Simple" vs. "Messy" Drawings

The paper distinguishes between two ways of drawing the city:

Simple Drawings: Roads can cross each other, but only once. No road can loop back and cross itself or the same road twice. This is like a clean, well-organized city map.
Non-Homotopic Drawings: A slightly looser rule. Roads can't form "empty loops" (like a rubber band that can be shrunk to a point without hitting anything). This allows for a bit more messiness.

The Surprise: For some forbidden shapes, the "messy" city allows for way more roads than the "clean" city. For example, if you ban the "4-crossing square," a messy city can have a quadratic number of roads (like $n^2$ ), while a clean city might be stuck with a lower number.

3. The "Almost All Graphs" Discovery

The authors also asked a different question: "Can we draw any random city without creating a specific forbidden neighborhood?"

They found that for almost any shape you pick (as long as it doesn't involve a crossing on its border), you can draw almost any city without ever creating that shape.

Analogy: Imagine you are trying to build a city that has no perfect square parks. The authors proved that unless your city is tiny (like just 3 blocks) or a very specific star shape, you can almost always rearrange the roads to avoid creating a square park.
The Exception: The only time you can't avoid a shape is if your city is so simple that it forces that shape to exist (like a triangle of 3 blocks forcing a triangular neighborhood).

4. The "Quasiplanar" Upgrade

One specific shape they looked at is the "3-crossing triangle." This is related to a famous concept called Quasiplanar graphs (where no three roads cross each other at the same time).

The Old Limit: Scientists thought the maximum number of roads in such a city was $7n - 28$.
The New Record: The authors built a new, clever city design that fits $7.5n - 28$ roads. They didn't just tweak the numbers; they found a whole new way to pack the roads together, closing the gap between the theoretical maximum and what we can actually build.

5. The Big Mystery (The Open Problem)

There is one shape that stumped them: The "4-crossing square" in a simple, clean drawing.

They know you can build a lot of roads if you allow messy drawings.
They know you can build some extra roads if you keep it clean.
But: They don't know the exact limit for the clean version. Is it a small number, or can you build a massive, quadratic city? They suspect it's huge (quadratic), but they haven't proven it yet.

Summary

Think of this paper as a guide for urban planners of the mathematical world.

If you ban a weird shape: You can usually build a huge, dense city.
If you ban a simple shape: You are limited to a standard, manageable city.
The Twist: Sometimes, allowing a little bit of "mess" in your drawing (non-homotopic) lets you build a city twice as big as a "clean" one.
The Goal: They are trying to figure out exactly how many roads you can pack into a city before the forbidden shape inevitably appears, no matter how hard you try to avoid it.

They have solved most of the puzzle, but one specific shape (the 4-crossing square in a clean drawing) remains the "holy grail" that they are still trying to crack.

Here is a detailed technical summary of the paper "Edge densities of drawings of graphs with one forbidden cell" by Hahn, Ueckerdt, and Vogtenhuber.

1. Problem Statement

The paper investigates the edge density (maximum number of edges) of graphs that admit a drawing avoiding a specific cell type $c$ .

Context: In topological graph theory, a drawing divides the plane (or sphere) into regions called cells. The type of a cell is defined by the cyclic sequence of vertices, edge segments, and crossings along its boundary.
Goal: For a fixed cell type $c$ , determine the maximum number of edges $|E|$ an $n$ -vertex graph can have if it admits a drawing that is $c$ -free (contains no cell of type $c$ ).
Variables: The study varies three parameters:
1. Graph Type: Simple graphs vs. Multigraphs.
2. Drawing Style: Simple drawings (edges intersect at most once), Non-homotopic drawings (no empty lenses), and Arbitrary drawings.
3. Cell Type $c$ : Defined by the number of vertices and crossings on the boundary (e.g., a $\mathfrak{3}$ -cell has 3 crossings and 0 vertices).

The authors aim to classify these graph classes as having linear ( $O(n)$ ) or superlinear ( $\omega(n)$ ) edge densities and provide tight upper and lower bounds.

2. Methodology

The authors employ a combination of combinatorial construction, discharging arguments, and topological transformations:

Discharging Method (Upper Bounds): To prove upper bounds on edge density, the authors utilize the Density Formula and discharging arguments. They assign charges to cells based on their size and type (e.g., $3e(c) + 2v(c) - 12$) and sum these over the entire drawing. By relating the total charge to the number of vertices and edges (via Euler's formula variants), they derive linear bounds for specific forbidden cell types.
Explicit Constructions (Lower Bounds): To establish lower bounds, the authors design specific graph drawings that avoid the forbidden cell type.
- Complete Graphs: They show that for most cell types, complete graphs $K_n$ admit $c$ -free drawings, implying quadratic density ( $\binom{n}{2}$ ).
- Grid and Toroidal Constructions: For harder cases (like $\mathfrak{4}$ -free drawings), they use grid-based constructions on the torus and plane, and "interleaving" techniques where multiple copies of a graph are threaded through each other to avoid specific local configurations.
Topological Perturbation: To ensure drawings are simple or non-homotopic, they use local perturbations of edges (e.g., slightly shifting crossing points) to eliminate empty lenses or multiple intersections without creating the forbidden cell type.
Crossing-Maximal Drawings: In Section 7, they analyze convex straight-line drawings with the maximum possible number of crossings to characterize which graphs can avoid cells with no incident crossings.

3. Key Contributions and Results

A. General Classification of Edge Densities

The paper provides a comprehensive table (Table 1) of bounds for all cell types.

Linear vs. Superlinear: For every cell type $c$ (with one exception), the edge density of $c$ -free graphs is either linear ( $O(n)$ ) or superlinear ( $\Omega(n^{1.5})$ or $\Omega(n^2)$ ).
Tightness: In most cases, the upper and lower bounds match up to an additive constant.

B. Specific Cell Type Results

$\mathfrak{5}$ -Free Drawings (No 5-cells):
- Result: For non-homotopic multigraphs, the edge density is at most $6n - 12$.
- Significance: This bound is tight even for simple graphs. The authors provide a construction achieving $6n-12$ edges.
$\mathfrak{4}$ -Free Drawings (No 4-cells):
- Multigraphs (Non-homotopic): Lower bound of $9n - 18$.
- Simple Graphs (Non-homotopic): Lower bound of $6n - 12$.
- Simple Graphs (Simple Drawings): The authors construct a drawing with $\Omega(n^{3/2})$ edges.
- Open Question: It remains unknown if simple $\mathfrak{4}$ -free drawings in the plane can achieve quadratic density ( $\Omega(n^2)$ ). The authors conjecture they can, citing quadratic constructions on the torus and for non-homotopic drawings.
$\mathfrak{3}$ -Free and Quasiplanar Drawings:
- Context: $\mathfrak{3}$ -free drawings are closely related to quasiplanar drawings (no three pairwise crossing edges).
- Improvements:
  - Quasiplanar (Simple, Non-homotopic): Improved the lower bound from $7n - 28 $to **$ 7.5n - 28$**.
  - $\mathfrak{3}$ -Free (Simple, Non-homotopic): Improved the lower bound to **$8n - 28 $**, nearly matching the known upper bound of$ 8n - 20$.
  - $\mathfrak{3}$ -Free (Simple Drawings): Improved the lower bound to **$7n - 30 $**, nearly matching the upper bound of$ 7n - 20$.
- Separation: The authors prove that the class of graphs admitting a non-homotopic $\mathfrak{3}$ -free drawing is strictly larger than the class of graphs admitting a non-homotopic quasiplanar drawing. They construct a graph that is $\mathfrak{3}$ -free but not quasiplanar.

C. Characterization of Avoidable Cell Types

Complete Graphs: The authors show that for any cell type $c$ with size $\ge 6$ , or specific small types, $K_n$ admits a $c$ -free drawing.
Forbidden Cells with No Crossings: For cell types whose boundaries contain no crossings (e.g., a face bounded only by vertices and edges), the authors provide a complete characterization.
- Theorem: A connected simple graph $G$ admits a simple drawing avoiding such a cell type $c_m$ (bounded by $m$ vertices) if and only if $G$ is not $K_3$ (for $m=3$ ) or a specific star graph $K_{1, m/2}$ (for even $m$ ).
- Implication: Almost all connected simple graphs can be drawn without any cell type that has no incident crossings.

4. Significance

Foundational Study: This is the first systematic study of graph drawings defined by forbidding a single cell type, bridging the gap between classical planar graphs (forbidding crossings) and complex beyond-planar classes.
Refinement of Known Bounds: The paper significantly tightens the known bounds for quasiplanar and $\mathfrak{3}$ -free graphs, resolving long-standing gaps between lower and upper bounds.
New Constructions: The development of the "interleaving" construction (Construction 11) and toroidal grid perturbations (Construction 9) provides new tools for constructing dense non-planar graphs with specific topological constraints.
Open Problems: The paper identifies the quadratic density of simple $\mathfrak{4}$ -free drawings in the plane as a major open problem, suggesting that current methods may be insufficient to prove or disprove it.

Summary Table of Key Bounds (Selected)

Cell Type	Graph Type	Drawing Type	Lower Bound	Upper Bound	Status
$\mathfrak{5}$ -free	Multigraph	Non-homotopic	$6n-12 $\|$ 6n-12$	Tight
$\mathfrak{4}$ -free	Simple	Non-homotopic	$6n-12$	Open	Linear
$\mathfrak{4}$ -free	Simple	Simple	$\Omega(n^{1.5})$	$\binom{n}{2}$	Gap
$\mathfrak{3}$ -free	Simple	Non-homotopic	$8n-28 $\|$ 8n-20$	Near-Tight
Quasiplanar	Simple	Non-homotopic	$7.5n-28 $\|$ 8n-20$	Improved

The paper concludes that while many forbidden cell types lead to linear density constraints, others allow for superlinear or even quadratic densities, depending heavily on the drawing restrictions (simple vs. non-homotopic) and the specific topology of the forbidden cell.