2023/01/04 by Thérèse Biedl, Biedl, Therese, John Wittnebel +1
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2301.01394
openalex publication_date 2023/01/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
It is well-known that every maximal planar graph has a matching of size at least \tfracn+83 if n≥ 14. In this paper, we investigate similar matching-bounds for maximal 1-planar graphs, i.e., graphs that can be drawn such that every edge has at most one crossing. In particular we show that every 3-connected simple-maximal 1-planar graph has a matching of size at least \tfrac2n+65; the bound decreases to \tfrac3n+1410 if the graph need not be 3-connected. We also give (weaker) bounds when the graph comes with a fixed 1-planar drawing or is not simple. All our bounds are tight in the sense that some graph that satisfies the restrictions has no bigger matching.