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!

## 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.)