2
$\begingroup$

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!

$\endgroup$
2
  • $\begingroup$ By "density", do you mean "number of edges"? $\endgroup$ Jan 19, 2021 at 6:26
  • $\begingroup$ Yes, it is the number of edges. $\endgroup$
    – Xin Zhang
    Jan 19, 2021 at 8:49

1 Answer 1

1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.