Every n-vertex maximal bipartite IC-plane graph with connectivity at least 2 has at least 3n/2 - 2 edges, and with connectivity at least 3 has at least 2n - 3 edges; both bounds are tight.
The minimum crossing number and minimum size of maximal 1-plane graphs with given connectivity
1 Pith paper cite this work. Polarity classification is still indexing.
abstract
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.
citation-role summary
citation-polarity summary
fields
math.CO 1years
2025 1verdicts
CONDITIONAL 1roles
background 1polarities
unclear 1representative citing papers
citing papers explorer
-
The minimum size of maximal bipartite IC-plane graphs with given connectivity
Every n-vertex maximal bipartite IC-plane graph with connectivity at least 2 has at least 3n/2 - 2 edges, and with connectivity at least 3 has at least 2n - 3 edges; both bounds are tight.