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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

non 3-connected maximal 1-planar graph

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

Improve this answer
$\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).

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .