6
$\begingroup$

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. enter image description here

$\endgroup$

1 Answer 1

15
$\begingroup$

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.

enter image description here

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:

enter image description here

In this way, all vertices have degree 5.

$\endgroup$
2
  • 2
    $\begingroup$ It's very beautiful. So a more interesting question is what the minimum oder of 5-regular 1-planar bipartite graphs is. "16" or even "32"? $\endgroup$
    – L.C. Zhang
    Sep 10, 2022 at 14:17
  • 2
    $\begingroup$ There are only 41 5-regular bipartite graphs with 16 vertices (from nauty: "geng -C 16 40 -h -b -d5 -D5"), and it doesn't look to me like any of them are 1-planar... $\endgroup$
    – jpreen
    Sep 11, 2022 at 10:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.