The minimum crossing number and minimum size of maximal 1-plane graphs with given connectivity
The minimum crossing number and minimum size of maximal 1-plane graphs with given connectivity
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.
Zhangdong Ouyang、Yuanqiu Huang、Licheng Zhang、Fengming Dong
数学
Zhangdong Ouyang,Yuanqiu Huang,Licheng Zhang,Fengming Dong.The minimum crossing number and minimum size of maximal 1-plane graphs with given connectivity[EB/OL].(2025-04-30)[2025-05-28].https://arxiv.org/abs/2504.21558.点此复制
评论