The minimum crossing number and minimum size of maximal 1-plane graphs with given connectivity
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910923057266688 |
|---|---|
| author | Ouyang, Zhangdong Huang, Yuanqiu Zhang, Licheng Dong, Fengming |
| author_facet | Ouyang, Zhangdong Huang, Yuanqiu Zhang, Licheng Dong, Fengming |
| contents | A 1-planar graph is a graph which has a drawing on the plane such that each edge is crossed at most once. If a 1-planar graph is drawn in that way, the drawing is called a {\it 1-plane graph}. A graph is maximal 1-plane (or 1-planar) if no additional edge can be added without violating 1-planarity or simplicity. It is known that any maximal 1-plane graph is $k$-connected for some $k$ with $2\le k\le 7$. Recently, Huang et al. proved that any maximal 1-plane graph with $n$ ($\ge 5$) vertices has at least $\lceil\frac{7}{3}n\rceil-3$ edges, which is tight for all integers $n\ge 5$. In this paper, we study $k$-connected maximal 1-plane graphs for each $k$ with $3\le k\le 7$, and establish a lower bound for their crossing numbers and a lower bound for their edge numbers, respectively. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_21558 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The minimum crossing number and minimum size of maximal 1-plane graphs with given connectivity Ouyang, Zhangdong Huang, Yuanqiu Zhang, Licheng Dong, Fengming Combinatorics 05C10, 05C62 A 1-planar graph is a graph which has a drawing on the plane such that each edge is crossed at most once. If a 1-planar graph is drawn in that way, the drawing is called a {\it 1-plane graph}. A graph is maximal 1-plane (or 1-planar) if no additional edge can be added without violating 1-planarity or simplicity. It is known that any maximal 1-plane graph is $k$-connected for some $k$ with $2\le k\le 7$. Recently, Huang et al. proved that any maximal 1-plane graph with $n$ ($\ge 5$) vertices has at least $\lceil\frac{7}{3}n\rceil-3$ edges, which is tight for all integers $n\ge 5$. In this paper, we study $k$-connected maximal 1-plane graphs for each $k$ with $3\le k\le 7$, and establish a lower bound for their crossing numbers and a lower bound for their edge numbers, respectively. |
| title | The minimum crossing number and minimum size of maximal 1-plane graphs with given connectivity |
| topic | Combinatorics 05C10, 05C62 |
| url | https://arxiv.org/abs/2504.21558 |