2014/03/21 by Oswin Aichholzer, Aichholzer, Oswin, Andrei Asinowski +3
Business, Management and Accounting · Computer Science · Mathematics · #05A15 #05A18 #68R05 #68R10 #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Facility Location and Emergency Management #G.2.1 #acm:05A15 #acm:05A18 #acm:68R05 #acm:68R10 #cs.CG #cs.DM #math.CO #msc:05A15 #msc:05A18 #msc:68R05 #msc:68R10
paper · pdf · doi:10.48550/arxiv.1403.5546
46 pages, 30 figures
arxiv created 2014/03/21 · openalex publication_date 2014/03/21 · arxiv updated 2014/03/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let X2k be a set of 2k labeled points in convex position in the plane. We consider geometric non-intersecting straight-line perfect matchings of X2k. Two such matchings, M and M', are disjoint compatible if they do not have common edges, and no edge of M crosses an edge of M'. Denote by DCMk the graph whose vertices correspond to such matchings, and two vertices are adjacent if and only if the corresponding matchings are disjoint compatible. We show that for each k ≥ 9, the connected components of DCMk form exactly three isomorphism classes -- namely, there is a certain number of isomorphic small components, a certain number of isomorphic medium components, and one big component. The number and the structure of small and medium components is determined precisely.