A note on the sizes of bipartite 1-planar graphs
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916864994574336 |
|---|---|
| author | Wang, Guiping |
| author_facet | Wang, Guiping |
| contents | A graph is 1-planar if it admits a drawing in the plane such that each edge is crossed at most once. Let G be a bipartite 1-planar graph with partite sets X and Y. A 1-disk OX drawing of G is a 1-planar drawing such that all vertices of X lie on the boundary of O and all vertices of Y and all edges of G locate in the interior of O, where O is a disk on the plane. The concept was first proposed by Huang, Ouyang and Dong when they solved a conjecture about the edge density of bipartite 1-planar graphs. Additionally, they presented a problem of determining the maximum number of edges in a bipartite graph with a 1-disk OX drawing. In this paper, we solve this problem and prove that every bipartite graph G which has a 1-disk OX drawing has at most 2|V(G)|+|X|-6 edges. Moreover, we demonstrate that this upper bound is tight. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_19762 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A note on the sizes of bipartite 1-planar graphs Wang, Guiping Combinatorics 05C10, 05C35, 05C62 05C10, 05C35, 06C62 A graph is 1-planar if it admits a drawing in the plane such that each edge is crossed at most once. Let G be a bipartite 1-planar graph with partite sets X and Y. A 1-disk OX drawing of G is a 1-planar drawing such that all vertices of X lie on the boundary of O and all vertices of Y and all edges of G locate in the interior of O, where O is a disk on the plane. The concept was first proposed by Huang, Ouyang and Dong when they solved a conjecture about the edge density of bipartite 1-planar graphs. Additionally, they presented a problem of determining the maximum number of edges in a bipartite graph with a 1-disk OX drawing. In this paper, we solve this problem and prove that every bipartite graph G which has a 1-disk OX drawing has at most 2|V(G)|+|X|-6 edges. Moreover, we demonstrate that this upper bound is tight. |
| title | A note on the sizes of bipartite 1-planar graphs |
| topic | Combinatorics 05C10, 05C35, 05C62 05C10, 05C35, 06C62 |
| url | https://arxiv.org/abs/2507.19762 |