1-planar graphs are those can be drawn in the plane so that there is at most one crossing per edge. We know that the maximum number of edges of an $n$-vertex 1-planar graph is at most $4n-8$, and the maximum number of edges of a bipartite $n$-vertex 1-planar graph is at most $3n-8$. I remember that there is also a result on the the maximum number of edges of a tripartite $n$-vertex 1-planar graph but I can't find the source now. Does anyone know this result or the source? Thanks in advance!
$\begingroup$
$\endgroup$
2
-
$\begingroup$ By "density", do you mean "number of edges"? $\endgroup$– Gerry MyersonCommented Jan 19, 2021 at 6:26
-
$\begingroup$ Yes, it is the number of edges. $\endgroup$– Xin ZhangCommented Jan 19, 2021 at 8:49
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
I find the following source. The known bound is 3.5n-7 (Theorem 4.8, pp. 57).
https://www.springer.com/gp/book/9789811565328
Beyond Planar Graphs
Communications of NII Shonan Meetings
Editors: Hong, Seok-Hee, Tokuyama, Takeshi (Eds.)