Near-perfect matchings in highly connected 1-planar graphs with a local crossing constraint
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