A graph is 1-planar if it can be drawn on the plane such that each edge is
crossed at most once.
Let $G$ be a 1-planar bipartite graph with $n~(n > 4)$ vertices and $m$ edges. Karpov [1] showed that $m \ge 3n − 8$ holds for even $n \ge 8$ and $m \ge 3n − 9$ holds for odd $n \ge 7$.
[1]. D. V. Karpov. Upper bound on the number of edges of an almost planar bipartite
graph. J. Math. Sci., 196:737–746, 2014.
So the minimum degree of any 1-planar bipartite graph is at most $5$. Here is my question.
- Construct a 5-regular bipartite 1-planar graph.
I've noticed that $5n\le2(3n-8)$ implies that $n\ge 16$. Maybe we will find such graph with $16$ vertices.
As jpreen reminds us, the following are 41 5-regular bipartite graphs with 16 vertices (with graph6 format). It may not be easy to determine whether they are 1-planar or not.
O????Bw}FKWwlOUoDw?}?
O????Bw}FKWwfOUoEw@]?
O????Bw|Fo[WpoJoBw?}?
O????Bw|FcPw{ORoDw?}?
O????Bw|FSWwdoVOFW@]?
O????Bw|FSWwdoRoFg@u?
O????Bw|FEZ_woJoBw?}?
O????Bw|FE\OxOFoBw?}?
O????Bw|FEZOtOFoDw@]?
O????Bw|FEXojOUoBw@m?
O????Bw|FEXofOMoDwAm?
O????Bw|FEXokoVODw?}?
O????Bw|FEXokoNOHw?}?
O????Bw|FEXoeoToFg@]?
O????Bw|FE[Wz?FoBw?}?
O????Bw|FE[Wf_VODw?}?
O????Bw|FEXWl_VOBw@]?
O????Bwxei^?woJoBw?}?
O????BwxeiRotOYoFW@]?
O????BwxeiXW}?LoDw?}?
O????BwxeiXWn?XoFW?}?
O????BwxeiXWf_ZOFW@m?
O????BwpvoWwl_ZOFW?}?
O????BwpvgToxOUoFW?}?
O????BwpvgXWm_ZOEw?}?
O????BwpvgXWj_VOFW@m?
O????BwpvgXWj_[oFg?}?
O????Bwptw[W}?ToDw?}?
O????Bwptw[W{_VODw?}?
O????Bwptw[W{_NOHw?}?
O????BwptwUW}?XoBwA]?
O????BwptwUWm_XoJgA]?
O????BwptwUWioXoJoAy?
O????BwptwWw|?YoBw@u?
O????Bwptk\G|?MoHw?}?
O????BwptkTg|?YoJW?}?
O????BwptkTg|?RoJW@u?
O????BwptkTgl_]OJWA]?
O????BwptkTgl_VOJWBU?
O????BwptkTgj_VOJWBe?
O????BwptkTgeoZ_JgBe?
The problem comes from planar bipartite graphs. Any planar bipartite graph has minimum degree at most 3. The smallest order of 3-regular planar bipartite graph is 8; see the below graph.
Best Answer
There is such a graph on 32 vertices, which is best presented on a cylinder.
Among the vertices, 24 of them are on the circular edges of the cylinder, giving no more than 1 crossing on each edge.
However, the graph is only 4-regular rather than 5-regular. To solve the problem, paste this graph to the top and the bottom of the cylinder:
In this way, all vertices have degree 5.