1-planar unit distance graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915318628089856 |
|---|---|
| author | Gehér, Panna Tóth, Géza |
| author_facet | Gehér, Panna Tóth, Géza |
| contents | A matchstick graph is a plane graph with edges drawn as unit distance line segments. This class of graphs was introduced by Harborth who conjectured that a matchstick graph on $n$ vertices can have at most $\lfloor 3n - \sqrt{12n - 3}\rfloor$ edges. Recently, his conjecture was settled by Lavollée and Swanepoel. In this paper we consider $1$-planar unit distance graphs. We say that a graph is a $1$-planar unit distance graph if it can be drawn in the plane such that all edges are drawn as unit distance line segments while each of them are involved in at most one crossing. We show that such graphs on $n$ vertices can have at most $3n-\sqrt[4]{n}/15$ edges, which is almost tight. We also investigate some generalizations, namely $k$-planar and $k$-quasiplanar unit distance graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_00940 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | 1-planar unit distance graphs Gehér, Panna Tóth, Géza Combinatorics 05C10, 05C12, 05C62 A matchstick graph is a plane graph with edges drawn as unit distance line segments. This class of graphs was introduced by Harborth who conjectured that a matchstick graph on $n$ vertices can have at most $\lfloor 3n - \sqrt{12n - 3}\rfloor$ edges. Recently, his conjecture was settled by Lavollée and Swanepoel. In this paper we consider $1$-planar unit distance graphs. We say that a graph is a $1$-planar unit distance graph if it can be drawn in the plane such that all edges are drawn as unit distance line segments while each of them are involved in at most one crossing. We show that such graphs on $n$ vertices can have at most $3n-\sqrt[4]{n}/15$ edges, which is almost tight. We also investigate some generalizations, namely $k$-planar and $k$-quasiplanar unit distance graphs. |
| title | 1-planar unit distance graphs |
| topic | Combinatorics 05C10, 05C12, 05C62 |
| url | https://arxiv.org/abs/2310.00940 |