On the minimum weight of a 3-connected 1-planar graph
Bull. Korean Math. Soc. 2017 Vol. 54, No. 3, 763-787 https://doi.org/10.4134/BKMS.b160296 Published online November 3, 2016 Printed May 31, 2017
Zai Ping Lu and Ning Song Nankai University, Nankai University
Abstract : A graph is called \emph{$1$-planar} if it can be drawn in the Euclidean plane $\mathbb{R}^2$ such that each edge is crossed by at most one other edge. The \emph{weight} of an edge is the sum of degrees of two ends. It is known that every planar graph of minimum degree $\delta\ge3$ has an edge with weight at most $13$. In the present paper, we show the existence of edges with weight at most $25$ in $3$-connected $1$-planar graphs.
