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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\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$
    – Licheng Zhang
    Commented 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
    Commented Sep 11, 2022 at 10:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .