Geodesic
Disjoint compatibility graph of non-crossing matchings of points in convex position
Oswin Aichholzer1 ; Andrei Asinowski2 ; Tillmann Miltzow2
1Institut für Softwaretechnologie, Technische Universität Graz
2Institut für Informatik, Freie Universität Berlin
The electronic journal of combinatorics, Tome 22 (2015) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

Let $X_{2k}$ be a set of $2k$ labeled points in convex position in the plane. We consider geometric non-intersecting straight-line perfect matchings of $X_{2k}$. 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 $\rm{DCM}_k$ 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 \geq 9$, the connected components of $\rm{DCM}_k$ 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.
DOI : 10.37236/4403
Classification : 05C70, 05C10, 05C76, 05C62, 05A15, 05A18, 68R05, 68R10
Mots-clés : planar straight-line graphs, disjoint compatible matchings, reconfiguration graph, non-crossing geometric drawings, non-crossing partitions, combinatorial enumeration

Oswin Aichholzer  1   ; Andrei Asinowski  2   ; Tillmann Miltzow  2

1 Institut für Softwaretechnologie, Technische Universität Graz
2 Institut für Informatik, Freie Universität Berlin 
@article{10_37236_4403,
     author = {Oswin Aichholzer and Andrei Asinowski and Tillmann Miltzow},
     title = {Disjoint compatibility graph of non-crossing matchings of points in convex position},
     journal = {The electronic journal of combinatorics},
     year = {2015},
     volume = {22},
     number = {1},
     doi = {10.37236/4403},
     zbl = {1308.05086},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/4403/}
}
TY  - JOUR
AU  - Oswin Aichholzer
AU  - Andrei Asinowski
AU  - Tillmann Miltzow
TI  - Disjoint compatibility graph of non-crossing matchings of points in convex position
JO  - The electronic journal of combinatorics
PY  - 2015
VL  - 22
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/4403/
DO  - 10.37236/4403
ID  - 10_37236_4403
ER  - 
%0 Journal Article
%A Oswin Aichholzer
%A Andrei Asinowski
%A Tillmann Miltzow
%T Disjoint compatibility graph of non-crossing matchings of points in convex position
%J The electronic journal of combinatorics
%D 2015
%V 22
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/4403/
%R 10.37236/4403
%F 10_37236_4403
Oswin Aichholzer; Andrei Asinowski; Tillmann Miltzow. Disjoint compatibility graph of non-crossing matchings of points in convex position. The electronic journal of combinatorics, Tome 22 (2015) no. 1. doi: 10.37236/4403

Cité par Sources :