The Maximal 1-Planarity and Crossing Numbers of Graphs
2021
A 1-planar graph is a graph which has a drawing on the plane such that each edge has at most one crossing. Czap and Hudak showed that every 1-planar graph with n vertices has crossing number at most $$n-2$$
. In this paper, we prove that every maximal 1-planar graph G with n vertices has crossing number at most $$n-2-(2\lambda _1+2\lambda _2+\lambda _3)/6$$
, where $$\lambda _1$$
and $$\lambda _2$$
are respectively the numbers of 2-degree and 4-degree vertices in G, and $$\lambda _3$$
is the number of odd vertices w in G such that either $$d_G(w)\le 9$$
or $$G-w$$
is 2-connected. Furthermore, we show that every 3-connected maximal 1-planar graph with n vertices and m edges has crossing number $$m-3n+6$$
.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
14
References
0
Citations
NaN
KQI