2016/11/30 by Hazim Michman Trao, Gek L. Chia, Trao, Hazim Michman +6
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Combinatorics #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #Crossing number (knot theory) #Discrete mathematics #Disjoint sets #Disjoint union (topology) #FOS: Mathematics #General position #Graph #Line graph #Mathematics #Point processes and geometric inequalities #Trivially perfect graph #math.CO
paper · pdf · doi:10.48550/arxiv.1611.10058
18 pages, 4 figures
openalex publication_date 2016/11/30 · arxiv created 2017/09/13 · arxiv updated 2017/09/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study extremal type problem arising from the question: What is the maximum number of edge-disjoint non-crossing perfect matchings on a set S of 2n points in the plane such that their union is a triangle-free geometric graph? We approach this problem by considering four different situations of S. In particular, in the general position, we obtain (i) a sufficient condition for the existence of n edge-disjoint non-crossing perfect matchings in the general position whose union is a maximal triangle-free geometric graph, and (ii) a lower bound on the number of edge-disjoint non-crossing perfect matchings whose union is a triangle free geometric graph.