# How to construct a 5-regular 1-planar bipartite graph?

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.