Abstract:A graph is 1-planar if it admits a drawing in the plane such that each edge is crossed at most once. Let G be a bipartite 1-planar graph with bipartition sets X and Y . A 1-disk OX drawing of G is a 1-planar drawing such that all vertices of X lie on the boundary of O and all vertices of Y and all edges of G locate in the interior of O, where O is a disk on the plane. The concept was first proposed by Huang, Ouyang and Dong when they solved a conjecture about the edge density of bipartite 1-planar graphs. Additionally, they presented a problem of determining the maximum number of edges in a bipartite graph with a 1-disk OX drawing. In this paper, we solve this problem and prove that every bipartite graph G which has a 1-disk OX drawing has at most 2|V(G)|+|X|-6 edges. Moreover, we demonstrate that this upper bound is tight, in the sense that there are infinitely many graphs for which this bound is attained exactly.
From: Guiping Wang [view email]
[v1]
Sat, 26 Jul 2025 03:29:42 UTC (9 KB)
[v2]
Sun, 13 Sep 2026 07:55:47 UTC (10 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。