Can a 3-regular non-1-planar graph be constructed?

Question

A $1$-planar graph is a graph which has a drawing on the plane such that each edge has at most one crossing.

I used nauty to generate all 3-regular graphs up to order 12, and checked each one of them individually. They all turned out to be 1-planar graphs.

My question is whether it is possible to construct a 3-regular non-1-planar graph.

I believe that it definitely exists.

I also conducted experiments on graphs with relatively large crossing numbers, but unfortunately, they were all 1-planar graphs. For example: The smallest 6-crossing cubic graph is the Desargues graph, with 20 vertices.

Or see this link for the hexagonal graph.

This problem is related to the question Why is the crossing number of Tutte 12-cage 170?, because we know that the crossing number of an $n$-order 1-planar graph is less than or equal to $n-2$ (see [1]).

• [1] Czap J, Hudák D. On drawings and decompositions of 1-planar graphs[J]. the electronic journal of combinatorics, 2013: P54-P54.

If the crossing number of Tutte 12-cage (126 vertices)is greater than or equal to $125$, then it is the 3-regular non- 1-planar graph we are looking for. Unfortunately, it seems that the crossing number of Tutte 12-cage is unknown. It would still be helpful if we knew a good lower bound of Tutte 12-cage.

---

Edit 1： As reminded by Joseph O'Rourke, Coxeter graph is a candidate. The following embedding is from Wikipedia and it almost has a 1-planar embedding, except for one edge that will cross twice.

Edit 2: Thanks to Sam Hopkins for the reminder, the above sentence in Edit 1 should be corrected to: 3 of the edges will cross twice (not just one edge).

Answer 1

For each $t$, there are $3$-regular graphs that are not $t$-planar. In fact, a random $3$-regular $n$-vertex graph, for large $n$, has this property. As we'll in the proof, one can take $n=Ct(\log t)^6$ for a suitable absolute constant $C$.

Indeed, let $G$ be such a graph and suppose that it admits a $t$-planar drawing. Pick a drawing in which no three edges intersect at the same point. By adding a vertex at the intersection points, we obtain a planar graph $G'$ with at most $3tn$ vertices and at most $3tn$ edges. Maximum degree of $G'$ is at most $4$. By the Ungar--Lipton--Tarjan separator theorem, there is a set $S_1$ of $O(\sqrt{tn})$ vertices whose removal splits $G'$ into two disconnected vertex sets $V_1$ and $V_2$, of size at most $2|V(G')|/3$ each.

Suppose that each both $|V_1\cap V(G)|$ and $|V_2\cap V(G)|$ are at least $n/r$ (where $r$ will be chosen later). In this case, the drawing of each edge of $G$ from $V_1\cap V(G)$ to $V_2\cap V(G)$ passes through $S_1$, and there are $\Omega(n/r^2)$ such edges in view of $G$ being an expander graph. Because the drawing of each such path passes through $S_1$, and no vertex of $S_1$ has degree more than $4$, it follows that $n/r^2\leq O(\sqrt{tn})$, i.e., $n=O(r^4 t)$.

This leaves the case when one of $|V_1\cap V(G)|$ or $|V_2\cap V(G)|$ is smaller than $n/r$. Say, $|V_1\cap V(G)|\leq n/100$. Then $|V_2\cap V(G)\geq (1-2/r)n$. We can then apply the separator theorem to the subgraph of $G'$ induced by $V_2$ to find a subset $S_2$ separating it into $V_2'$ and $V_3$. Again, if both $V_2'$ and $V_3$ contain $n/r$ vertices of $G$, then we find $\Omega(n)$ edges of $G$ whose drawing goes through $S_1\cup S_2$. Hence, we may assume that one of the parts, say $V_2'$, satisfies $|V_2\cap V(G)|\leq n/r$. We then repeat the argument on $V_3$, etc.

In the nested sequence $V(G')\supset V_2\supset V_3\supset\dotsb$, each next set is $\tfrac{2}{3}$ of the size of the preceding. So, $|V_{\ell}|=O\bigl( (\tfrac{2}{3})^\ell tn\bigr)$ which contradicts $|V_{\ell}\cap V(G)|\geq (1-2\ell/r)n$ if $\ell=r/4$ and $r=20\log t$. So, at some step we must have $\Omega(n/r^2)\leq |S_1|+\dotsb+|S_i|\leq O(i\sqrt{tn})$, i.e., $n=O(r^6 t)=O\bigl(t(\log t)^6\bigr)$.

The power of $\log t$ is likely improvable with more careful choice of parameters, and more careful choice of separators.

Answer 2

The following is overkill compared to Boris Bukh’s answer, but it will give you a more deterministic example.

It has been proved by Bonamy et al. that 1-planar (even more, (g,k)-planar for any genus $g$ and $k\in \mathbb{N}$) graphs have asymptotic dimension at most 2 (Corollary 1.6). On the other hand, we know plenty of 3-regular graphs with asymptotic dimension >2. For a concrete example, take the cubic lattice $\mathbb{Z^3}$. It is 6-regular, but you can blow up each vertex into a sub-cubic tree to make it 3-regular without affecting its asymptotic dimension, which is 3. This graph $G$ is infinite, but you can use a compactness argument to deduce that for large enough $n$, the ball of radius $n$ in $G$ is not $k$-planar.

You could try to prove this directly, by decomposing a portion of $G$ into planar `slices’, each of which is 3-connected, and therefore embeds essentially uniquely in $\mathbb{S}^2$. Thus each slice will intersect a lot with other slices.

Answer 3

Did you check the Coxeter graph?