Here's a graph drawing problem I don't know how to solve: find the smallest 3-regular graph that is not 1-planar.

The examples I tried with up to 24 vertices are 1-planar. Below are the 20-vertex Desargues graph,

1-planar drawing of the Desargues graph

the 24-vertex McGee graph (7-cage),

1-planar drawing of the McGee graph

and the 24-vertex Nauru graph:

1-planar drawing of the Nauru graph

(I'm not requiring the edges to be straight line segments; they're just drawn that way.)

On the other hand, for the 28-vertex Coxeter graph and 30-vertex Tutte–Coxeter graph (8-cage) I have been unable to find a 1-planar drawing. So my guess is that the answer is somewhere in this range.

The fastest method I know of for testing whether graphs are 1-planar algorithmically (try all pairings of edges, for each pair of edges insert a dummy node to represent their crossing, and test planarity of the result) is going to max out at 14 or so vertices, I think, not good enough to solve the problem. On the other hand, lately there's been some progress on solving other crossing number problems exactly by formulating them as logic problems using the Hanani–Tutte theorem and throwing SAT solvers at them. Maybe something like that can work here, too.


Do you know if recognition of 1-planar graphs for 3-regular graphs is NP-hard?
It would surprise me if it weren't NP-hard, but I don't think it has been proved.
I'm probably being naive, but have you tried the Franklin graph?
1-planar drawing of the Franklin graph