6
$\begingroup$

A graph is $k$-planar if it can be drawn in the plane so that each edge is crossed at most $k$ times. A $k$-planar graph $G$ is maximal if $G+uv$ is not $k$-planar for any non-adjacent vertices $u,v\in V(G)$.

  • Is there any maximal $1$-planar graph that is not $3$-connected ?
  • Is there any maximal $2$-planar graph that is not $3$-connected ?

I believe those examples exist but didn't find any references mentioned this.

$\endgroup$

2 Answers 2

3
$\begingroup$

non 3-connected maximal 1-planar graph

This is a non-3-connected 1-planar example...

$\endgroup$
1
$\begingroup$

The paper On Properties of Maximal 1-planar Graphs by Dávid Hudák, Tomáš Madaras and Yusuke Suzuki describes the construction of maximal 1-planar graphs with minimum degree 2 and with (relatively) small number of edges, namely, (8/3)*(n-2) (which is far less than the number of edges of a maximal n-vertex planar graph).

$\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.