Lower bound on the number of edges in a non-$k$-planar graph.

extremal-graph-theorygraph theoryplanar-graphs

Just for fun!

This problem is a generalization of the question I came across in the following post:

That means that every non-planar graph (non-1-planar graph) has at least $n+3$ edges.

A $k$ -planar graph is a graph that can be drawn in the Euclidean
plane in such a way that each edge has at most $k$ crossing point,
where it crosses other edges. Clearly, $k$-planar graphs are
one of the most natural generalizations of planar graphs.

Hence, I propose the following similar problem: What is the lower bound on the number of edges in a non $k$-planar graph?

Upon closer examination of the proof of kabenyuk, it has been determined that the presence or absence of 2-degree vertices and 1-degree vertices does not affect the planarity of the graph. At this point, we note that 2-degree vertices do have an impact on $k$-planarity when $k\ge 1$.

For exmaple, $K_7$ is not 1-planar, but when we insert 2-degree vertices, it can be changed a 1-planar graph.

enter image description here

A starting problem:

Can we construct infinitely many non-1-planar (connected) graphs with $n+3$ edges?

Best Answer

Rather than subdivide edges, another way to get bigger graphs while keeping the difference $|E|-|V|$ the same, and not affecting $k$-planarity, is to add leaf vertices. Most simply, just take a graph with $n$ vertices and $m$ edges, and add a path with $t$ new vertices and $t$ new edges from one of its vertices; the result has $n+t$ vertices and $m+t$ edges, and the new graph is $k$-planar if and only if the original graph was.

I do not think we will find infinitely many examples of non-$1$-planar graphs with $n$ vertices and $n+3$ edges, because I do not think we will find any. The question is: what is the best difference between edge and vertex count we can achieve?

I found many examples of non-$1$-planar graphs with $n$ vertices and $n+11$ edges. According to Wikipedia, $K_{3,7}$ (with $10$ vertices and $21$ edges), $K_{4,5}$ (with $9$ vertices and $20$ edges), $K_{1,3,4}$ (with $8$ vertices and $19$ edges), and $K_{1,1,1,1,3}$ (with $7$ vertices and $18$ edges) are not $1$-planar. This ultimately comes from 1-planarity of complete multipartite graphs by Czap and Hudák. Also, Minimal non-$1$-planar graphs by Korzhik points out that $K_{1,1,1,1,3} = K_7 - K_3$ is a minimal non-$1$-planar graph, and that subdividing one of the edges between its degree-$6$ vertices gives another minimal non-$1$-planar graph (with $8$ vertices and $19$ edges).

Of course, we can use the path-adding technique to construct infinitely many non-$1$-planar graphs with $n$ vertices and $n+11$ edges. I'm pointing out that there's a bunch of $n+11$ examples because I think it's evidence that we can't reach $n+10$; if we hit the same wall from many different directions, we can suspect that the wall is everywhere. (But it's not very strong evidence.)

Related Question