Unit distance graphs with few crossings per edge
Panna Gehér, Dömötör Pálvölgyi, Dániel G. Simon, Géza Tóth · 2026
Read Unit distance graphs with few crossings per edge by Panna Gehér, Dömötör Pálvölgyi, Dániel G. Simon, Géza Tóth (2026) 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-2603-19848.txt.
Introduction
Gehér and co-authors study unit distance graphs that allow few crossings per edge. Each edge is a unit segment, and at most k edges may cross it. They ask how many edges such a graph on n points can have. For one crossing per edge, they improve the best known upper bound. The new bound is tight apart from the constant term. For two crossings, they prove the first strong upper bound. They also give a construction that beats the crossing-free case.
Catalog record
| CREATOR | Panna Gehér, Dömötör Pálvölgyi, Dániel G. Simon, Géza Tóth |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 39004 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.19848
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Unit distance graphs with few crossings per edge Panna Gehér, Dömötör Pálvölgyi, Dániel G. Simon, Géza Tóth Abstract A graph is called a k k -planar unit distance graph if it can be drawn in the plane such that every edge is a unit line segment and is involved in at most k k crossings. We investigate u k ( n ) u_{k}(n) , the maximum number of edges of such graphs on n n vertices. For k = 1 k=1 , we improve the best known upper bound, by showing that u 1 ( n ) ≤ 3 n − c n u_{1}(n)\leq 3n-c\sqrt{n} for some constant c > 0 c>0 . This bound is tight up to the value of the constant c c . For k = 2 k=2 , we establish the first non-trivial upper bound by proving that u 2 ( n ) ≤ 4 n − 8 u_{2}(n)\leq 4n-8 . Regarding lower bounds we give a construction for k = 2 k=2 that shows u 2 ( n ) ≥ u 0 ( n ) + c n u_{2}(n)\geq u_{0}(n)+c\sqrt{n} if n n is sufficiently large. 1 Introduction A graph is called a matchstick graph if it can be drawn in the plane with no crossings such that all of its edges are unit segments. This graph class was introduced by Harborth [ 7 , 8 ] . He conjectured that the maximum number of edges of a matchstick graph on n vertices is 3n-\left\lfloor\sqrt{12n-3}\right\rfloor and he proved it [ 6 ] in the special case where the unit distance is the minimum distance among the points. These graphs are known as penny graphs . After almost 40 years, his conjecture was settled by Lavollée and Swanepoel [ 10 ] . This result is tight, as shown by a hexagonal piece of the regular triangular lattice. For any k\geq 0 , a graph is called k -planar if it can be drawn in the plane such that each edge is involved in at most k crossings; such a drawing is called a k -plane drawing. Let e_{k}(n) denote the maximum number of edges of a k -planar graph on n vertices. For general k , we have e_{k}(n)\leq c\sqrt{k}n for some constant c>0 , which is tight apart from the value of c [ 11 , 1 ] . For small values of k , the exact values of the maximum number of edges are known. Since 0 -planar graphs are the well-known planar graphs, we have e_{0}(n)=3n-6 for n\geq 3 , which is tight for triangulations. It is also known that e_{1}(n)=4n-8 for n\geq 4 (proved independently in [ 2 ] and [ 11 ] ) and that e_{2}(n)\leq 5n-10 [ 11 ] . These results are tight for infinitely many values of n . Introduced in [ 5 ] , a graph is called a k -planar unit distance graph if it can be drawn in the plane such that each edge is a unit segment and is involved in at most k crossings. Clearly, 0 -planar unit distance graphs are exactly the matchstick graphs. The maximum number of edges a k -planar unit distance graph on n vertices can have is denoted by u_{k}(n) . Since 0 -planar unit distance graphs are the matchstick graphs, by the result of Lavollée and Swanepoel [ 10 ] , we have u_{0}(n)=3n-\left\lfloor\sqrt{12n-3}\right\rfloor . For k=1 , we have u_{1}(n)\leq e_{1}(n)=4n-8 . It was shown by the two extremal authors in [ 5 ] that u_{1}(n)\leq 3n-\sqrt[4]{n}/15 . Here we improve this upper bound. Theorem 1 . For the maximum number of edges of a 1 -planar unit distance graph, u_{1}(n) , we have u_{1}(n)\leq 3n-\sqrt{n}/100. This result is tight apart from the coefficient of the \sqrt{n} term, as u_{1}(n)\geq u_{0}(n)=3n-\left\lfloor\sqrt{12n-3}\right\rfloor . We did not attempt to find the optimal coefficient, probably 1/100 is far from the optimal value. Our proof is based on a recently introduced tool, called the Density Formula [ 9 ] . For a given drawing, it describes the connection between the number of edges, vertices, crossings, and sizes of its cells. This result is particularly powerful in establishing upper bounds on the number of edges for many so-called beyond planar graph classes. Another important tool in our proof is the Isoperimetric inequality [ 3 ] . It states that a closed Jordan curve \gamma of given length in the plane encloses the maximum area if it is a circle. For k=2 , we have u_{2}(n)\leq e_{2}(n)=5n-10 . We establish the first improvement of this bound. Theorem 2 . For the maximum number of edges of a 2 -planar unit distance graph, u_{2}(n) , we have u_{2}(n)\leq 4n-8. Our proof uses the technique developed in [ 11 ] . We choose a maximal plane subgraph in a given 2-plane drawing, and estimate the number of the remaining edges using the discharging method. Clearly, for every n , we have u_{2}(n)\geq u_{1}(n)\geq u_{0}(n) . As we have mentioned, the edge number 3n-\left\lfloor\sqrt{12n-3}\right\rfloor can be achieved on n vertices, even for matchstick graphs, by considering a hexagonal piece of the regular triangular lattice. However, it is not obvious that if we allow a few crossings per edge, we can improve this construction. Recently, Červenková and Kratochvíl [ 4 ] proved that u_{1}(n)>u_{0}(n) if n is large enough. Moreover, they showed that for any constant \alpha<\sqrt[4]{1/3} , we have u_{1}(n)\geq u_{0}(n)+\alpha\sqrt[4]{n} if n is sufficiently large. For k=3 , an easy example (two copies of a proper piece of a triangular grid, shifted by a unit vector) gives u_{3}(n)\geq 3.5n-c\sqrt{n} , for some constant c>0 . Here we give a construction for 2-planar unit distance graphs with roughly u_{0}(n)+0.58\sqrt{n} edges, if n is large enough. Theorem 3 . For all n large enough, we have u_{2}(n)\geq u_{0}(n)+0.58\sqrt{n}. Remark 1 . According to our definition, a k -planar unit distance graph admits a drawing satisfying both conditions simultaneously: each edge is a unit segment and involved in at most k crossings. Note that this is not the same class as graphs that are k -planar and unit distance graphs; for instance, the Moser spindle is a planar graph and also a unit distance graph. However, it does not admit a crossing-free drawing such that each edge is a unit segment, and thus it is not a matchstick graph. 2 1-planar unit distance graphs Proof of Theorem 1 . In this section, we prove Theorem 1 . Our proof is based on the Density Formula [ 9 ] . First we need some preparation. Fix a drawing \Gamma of some graph G and let \mathcal{X} denote the set of all crossings in \Gamma . The planarization of the drawing \Gamma is the plane drawing obtained from \Gamma by adding new vertices at each crossing point and splitting the involved edges into edge-segments. We say that the drawing \Gamma is connected if the graph underlying its planarization is connected. Furthermore, let \mathcal{C} denote the set of cells i.e., the connected components of \mathbb{R}^{2} remaining after removing all edges and vertices in \Gamma . We say that a crossing