The plane is a stage where graphs perform: vertices as dancers, edges as lines that sometimes cross. In this choreography, researchers ask not just how fast the performers move, but how many lines must cross to keep the dance intact when there are many dancers on stage. A 1-planar graph is a drawing in which each edge is allowed to cross at most once. It’s a natural middle ground between the clean elegance of planar graphs (no crossings) and the messy reality of dense networks where crossings pile up. When a drawing uses every edge to its limit of one crossing, we call it a 1-plane drawing. The authors Zhangdong Ouyang, Yuanqiu Huang, Licheng Zhang, and Fengming Dong in their collaboration across Hunan Normal University, Hunan First Normal University, Hunan University, and the National Institute of Education at Nanyang Technological University, Singapore, study a sharper, more structural version of this idea: maximal 1-plane graphs. These are 1-plane graphs from which you cannot add any edge without breaking 1-planarity or simplicity. In other words, they’re as full as a 1-planar drawing can be, given the way the lines cross.
Two questions loom large here. First, how many crossings must a maximal 1-plane graph have if you demand a certain level of connectivity? Connectivity, in graph terms, is a measure of resilience: how many vertices you’d need to remove before the graph falls apart. The second question asks how many edges such a graph must have in the first place. It’s a dual puzzle: you want a network that is robust (well-connected) but not so dense that crossings explode. The paper maps out sharp lower bounds for both crossing numbers and edge counts, for connectivity levels from 3 up to 7. And it doesn’t stop there: it shows these bounds are tight for infinitely many sizes, with a few spectacular finite-edge cases that crystallize the ideas. This is not mere counting. It’s about understanding the fundamental tension between readability (fewer crossings) and robustness (more edges) in a constrained drawing regime.
To ground this work, we should name the players. The study sits at the intersection of theory and construction, and it follows a thread of results about maximal 1-plane graphs that reach a delicate balance between sparsity and structure. The team builds on decades of exploration into how sparse a maximal 1-plane graph can be, while also ensuring a given connectivity, and then pushes further to pin down exact lower bounds for their crossings. The moral of the story, in plainer terms, is this: as you demand more resilience in a network drawn on a plane, you must pay in the currency of extra crossings — but only up to certain arithmetic rules that the authors precisely establish. The core takeaway is both elegant and useful: you can’t pretend to have a highly connected network on a plane without some minimum amount of crossing work, and there are concrete, repeatable ways to realize the most economical such networks for many sizes.
What exactly is being studied and why it matters
To appreciate the results, a quick tour of the key concepts helps. A graph is 1-planar if you can draw it so every edge is crossed at most once. If, in such a drawing, you can’t add any new edge without forcing some edge to be crossed more than once or creating multiple edges, the graph is maximal 1-planar. A 1-plane graph is the graph together with a particular 1-planar drawing. These objects live somewhere between planarity (no crossings) and general graphs (where crossings can be many and messy). They are especially relevant to modern graph drawing, where people want to visualize networks clearly, even when the networks are dense and highly interconnected. The human brain likes to see patterns in a drawing, and controlling the number and arrangement of crossings is a big part of that visual discipline.
Beyond the drawing itself, one more structural notion is central: connectivity. A graph is k-connected if you need to remove at least k vertices to disconnect it or reduce it to a trivial graph. Connectivity measures resilience: it’s a way of saying the network won’t fall apart if a few nodes fail. Earlier work showed that maximal 1-planar graphs can be as connected as 7, but not all at once with all their combinatorial baggage. This paper asks, for each possible level of connectivity k between 3 and 7, what are the minimal crossing numbers cr(G) and minimal edge counts |E(G)| you must accept for a maximal 1-plane graph with n vertices? The answers aren’t just abstract inequalities. They reveal the geometry of constraint: how connectivity forces a certain amount of “crossing cost” in the plane, and how that cost grows with the number of vertices.
Lower bounds on crossing numbers across different connectivities
The first pillar of the paper delivers a clean, formulaic look at cr(G) for maximal 1-plane graphs with a fixed connectivity k. The result is surprisingly structured. For graphs that are 3-connected, the minimum crossing number grows roughly as a third of the number of vertices minus a constant: cr(G) ≥ (n − 2)/3, for n large enough (n ≥ 5). For 4-connected graphs, the bound is cr(G) ≥ (n − 2)/2, again with the appropriate caveat on n. For the band of connectivities 5 and 6, the bound becomes cr(G) ≥ (3n − 6)/5. And for the nearly maximal case, 7-connected graphs, the bound tightens further to cr(G) ≥ 3n/4. In every case, the authors show that these aren’t just theoretical floor values. They construct explicit families of graphs that achieve these exact minima for infinitely many vertex counts, proving sharpness. In short: as you demand more resilience in a 1-plane graph, you have to accept a linearly growing minimum of crossing events, and the rate of growth can be pinned down precisely depending on the target connectivity.
The upshot is a kind of phase diagram for 1-plane graphs: at each connectivity level, there is a measurable, inevitable crossing tax you pay as the graph scales. The paper also carefully notes that the sharpness of these bounds holds for infinitely many n in most cases (3, 4, and 6), with explicit finite exemplars for the 7-connected case. That’s not just mathematics for the sake of math; it offers a map for what’s possible and impossible when you push the constraints in different directions. It’s a reminder that in the plane, connectivity and readability trade in a mathematic rhythm, not in a vague, uncontrollable fashion.
The other side of the coin: how many edges you need
If crossing counts measure how tangled a drawing is, the edge count tells you how dense the network itself must be. The second main result of the paper translates the crossing bounds into lower bounds on the number of edges. The reasoning rests on a classic trick: turning the 1-plane drawing into a triangulated plane graph by splitting every crossing into a small gadget, a process that preserves core invariants and makes counting feasible. Once this step is in place, the authors leverage Euler’s formula and standard triangulation theory to relate cr(G) to the total edge count.
Concretely, the paper proves that for 3-connected graphs, the edge count must satisfy |E(G)| ≥ (10/3)(n − 2) when n is at least 5. For 4-connected graphs, the bound tightens to |E(G)| ≥ (7/2)(n − 2) for n ≥ 6. For connectivity 5 or 6, you need at least |E(G)| ≥ (18/5)(n − 2). And for 7-connected graphs, the threshold is |E(G)| ≥ (15/4)(n − 2) plus a small constant term (3/2). As with cr(G), these results aren’t merely existential: the authors construct families of graphs that meet these bounds, demonstrating sharpness for the same ranges of n where the crossing bounds were tight. This creates a coherent narrative: the density of a maximal 1-plane graph scales with connectivity in a predictable, extremal way.
There’s a deeper structure here, too. The paper connects the extremal edge counts to the same triangulation framework that anchors the crossing-number results. In particular, once cr(G) is pinned and the augmented graph G× is known to be a triangulation, the edge count becomes a direct tally: |E(G)| = 3n − 6 + cr(G). That’s a crisp, almost surgical relationship between two seemingly different kinds of constraints. It also explains why the authors can talk about both quantities in parallel: the same underlying geometry of the drawing governs both how many edges you must have and how many times you must cross them.
How they prove it: triangulations, gadgets, and extremal families
The technical engine behind the results is a careful use of triangulations and a few clever constructions that serve as extremal witnesses. A recurring theme is to study the augmented plane graph G×, which replaces each crossing with a vertex of degree four. When the original 1-plane graph G is maximally 1-planar and suitably connected, G× turns out to be a triangulation — a graph where every face is a triangle, in the geometric sense. This is not just a neat trick; it’s the hinge that makes the combinatorics tractable. In a triangulation, each face boundary is well-behaved, and counting arguments become sharper, because the Euler characteristic and the regularity of faces constrain what can happen inside the drawing. The authors prove that for k ∈ {3,4,5,6}, the augmented graph G× indeed becomes a triangulation, which in turn ties cr×(G) to the number of “fake” vertices introduced by the crossings. The upshot is a precise, algebraic bridge between the geometry of the drawing and the combinatorics of the graph itself.
To show sharpness, the paper engineers explicit families of maximal 1-plane graphs that meet these lower bounds exactly. They start with carefully designed base graphs built from cycles and then layer in additional structure through a sequence of triangulation operations inside faces. The constructions are named with a kind of mathematician’s affection: Hk, XHk, YHk, and HK-like gadgets. Each family is crafted so that its underlying connectivity is exactly the target k, its augmented version G× is a triangulation, and the crossings scale in a controlled, predictable way as the order n grows. The authors demonstrate, for instance, that for certain infinite families, cr(G) equals 1/3(n − 2) when k = 3, or cr(G) equals 3/5(n − 2) in the most connected 7-edge cases, matching the lower bounds. They even pin down a couple of concrete, finite sizes where the strongest possible connectivity can be achieved with precisely the predicted number of edges and crossings (n = 24 and n = 56 for the 7-connected case). It’s a parade of explicit examples that not only verify the theory but also illuminate the mechanics of why these bounds hold in the first place.
Why this matters beyond the chalkboard
At first glance, these results look like an esoteric corner of graph theory. But there are gravitational pulls from this work that reach into the way we model, visualize, and even design networks. First, the existence of sharp, connectivity-dependent lower bounds for crossing numbers is a reminder that readability and robustness are not freely compatible in dense networks drawn on a plane. If you want a network that stays legible when drawn with limited crossings, you have to pay in a measurable way as the network grows, and the exact rate of that payment depends on how robust you want the network to be. This has implications for layouts in circuit design, data visualization, and any domain where large networks must be laid out on a two-dimensional surface without spiraling into visual chaos.
Second, the precise construction of extremal graphs is more than mathematical theater. It mirrors a broader philosophy in discrete geometry and graph drawing: to understand a boundary, you build the edge-case objects that just meet it. By showing explicit families of graphs that hit the lower bounds, the authors give a concrete toolkit that others can study, adapt, or refute. It’s the difference between a theoretical assertion and a testable, tangible world where you can print the graphs, play with their drawings, and see how close you are to the limit. In an age where networks grow denser and the demand for clear visual representations grows with them, such extremal portraits matter.
In short, this work not only answers questions about how sparse or how crossing-laden a highly connected maximal 1-plane graph must be; it also gives a precise, constructive lens through which to view the trade-offs between sparseness, connectivity, and drawability. That lens is likely to inform future explorations into beyond-planar graph families, where researchers seek the sweet spot between elegance and complexity in the drawings we rely on to understand our connected world.
Open questions and the horizon ahead
The authors aren’t done waving the flag. They sketch several open problems that feel both natural and tantalizing. One family of questions asks about the minimum crossing number for maximal 1-plane graphs with connectivity 2 — a case that remains less settled because the structure is looser and the triangulation dogma doesn’t apply as snugly. Another asks for the exact minimum cr(G) and |E(G)| for all n when the connectivity is exactly 3, and whether there exist 5-connected maximal 1-plane graphs that realize the extreme bounds to the letter. Finally, there are intriguing conjectures about the universality of their extremal families: can every minimal-density instance be traced back to the Hk-based constructions and their kin, or do other, unseen families lurk in the combinatorial shadows?
Beyond these direct questions, the paper nods to larger programs in graph drawing that explore what happens when you relax planarity, mix in different crossing allowances, or combine local constraints with global topology. The sense is that the problem is a puzzle with many pieces, and each resolved piece reveals more of the larger picture: how structure, density, and geometry interact in the graphs we use to model complex systems.
Takeaways: a concise map of the terrain
The study delivers three bold claims in one sweep. First, for each connectivity level k from 3 to 7, maximal 1-plane graphs with n vertices must have at least a certain number of crossings, cr(G), with precise formulas depending on k. Second, the same graphs must have at least a certain number of edges, |E(G)|, and these bounds align with cr(G) in a way that echoes a triangulation identity, namely |E(G)| = 3n − 6 + cr(G). Third, for k ∈ {3, 4, 6}, those lower bounds are proven tight for infinitely many n, while for k = 7 there are concrete finite instances (n = 24 and n = 56) that achieve the bound and are 7-connected. The authors even offer explicit constructions that realize these extremal graphs, showing that the bounds aren’t merely theoretical artifacts but attainable targets in the combinatorial landscape.
The findings sit at a satisfying crossroads of combinatorics, geometry, and graph drawing. They don’t just quantify a curiosity about how many lines must cross. They illuminate the deeper geometry of how a network’s resilience shapes its visual footprint on a plane. And they do so with a blend of rigorous bounds and concrete, repeatable constructions that can guide future explorations into the rich world of maximal 1-planar graphs and their many cousins in the universe beyond planarity.
Note on provenance: The study is a collaboration led by Zhangdong Ouyang and Yuanqiu Huang, with contributors from Hunan Normal University, Hunan First Normal University, Hunan University, and the National Institute of Education at Nanyang Technological University, Singapore. The authors behind these results include Zhangdong Ouyang, Yuanqiu Huang, Licheng Zhang, and Fengming Dong, among others. Their work extends a line of inquiry into how sparse maximal 1-plane graphs can be while preserving a given level of connectivity, and how the crossing number grows as the graph scales.
