Cubic 1-planarity

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,

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

and the 24-vertex 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.

Comments:

11011110:
2014-05-17T05:46:20Z