Unit distance graphs with few crossings per edge
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908902713458688 |
|---|---|
| author | Gehér, Panna Pálvölgyi, Dömötör Simon, Dániel G. Tóth, Géza |
| author_facet | Gehér, Panna Pálvölgyi, Dömötör Simon, Dániel G. Tóth, Géza |
| contents | A graph is called a $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$ crossings. We investigate $u_k(n)$, the maximum number of edges of such graphs on $n$ vertices. For $k=1$, we improve the best known upper bound, by showing that $u_1(n) \leq 3n - c\sqrt{n}$ for some constant $c>0$. This bound is tight up to the value of the constant $c$. For $k=2$, we establish the first non-trivial upper bound by proving that $u_2(n) \leq 4n - 8$. Regarding lower bounds we give a construction for $k=2$ that shows $u_2(n) \geq u_0(n) + c\sqrt{n}$ if $n$ is sufficiently large. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_19848 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Unit distance graphs with few crossings per edge Gehér, Panna Pálvölgyi, Dömötör Simon, Dániel G. Tóth, Géza Combinatorics A graph is called a $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$ crossings. We investigate $u_k(n)$, the maximum number of edges of such graphs on $n$ vertices. For $k=1$, we improve the best known upper bound, by showing that $u_1(n) \leq 3n - c\sqrt{n}$ for some constant $c>0$. This bound is tight up to the value of the constant $c$. For $k=2$, we establish the first non-trivial upper bound by proving that $u_2(n) \leq 4n - 8$. Regarding lower bounds we give a construction for $k=2$ that shows $u_2(n) \geq u_0(n) + c\sqrt{n}$ if $n$ is sufficiently large. |
| title | Unit distance graphs with few crossings per edge |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2603.19848 |