Near-perfect matchings in highly connected 1-planar graphs with a local crossing constraint

Read full text
Authors: Licheng Zhang Yuanqiu Huang Zhangdong Ouyang
Cited by: 0

Abstract

For planar graphs, it is well known that high connectivity implies a Hamiltonian cycle and hence any 4-connected planar graph has a near-perfect matching. Nevertheless, whether 6-connected 1-planar graphs admit near-perfect matchings remains largely open. The prior art established this for 4-connected 1-planar graphs only when each crossing involves four endpoints that induce a $K_4$. In this paper, we study 6-connected 1-planar graphs that are drawn such that at all crossings the four endpoints induce a 4-cycle (plus perhaps more edges). We show that these have a near-perfect matching, and in fact even stronger, their scattering number is at most one. Moreover, under the local crossing restriction, the requirement of 6-connectivity is best possible; this is witnessed by explicit constructions due to Biedl and Fabrici et al.

Fields of Study & Subjects

Advanced Graph Theory Research Limits and Structures in Graph Theory Complexity and Algorithms in Graphs

Publication details

Journal / source
arXiv (Cornell University)
Publication date
5 February 2026
Document type
Preprint