A note on maximal plane subgraphs of the complete twisted graph containing perfect matchings

Abstract

The twisted graph $T_n$ is a drawing of the complete graph with $n$ vertices $v_1,v_2,\dots ,v_n$ in which two edges $v_i{v}_j$ ($i<j$) and $v_s{v}_t$ ($s<t$) cross if and only if $i<s<t<j$ or $s<i<j<t$. We show that for any maximal plane subgraphs $S$ and $R$ of $T_n$, each containing at least one perfect matching, there is a sequence $S=F_0,F_1,\dots ,F_m=R$ of maximal plane subgrahs of $T_n$, also containing perfect matchings, such that for $i=0,1,\dots ,m-1$, $F_{i+1}$ can be obtained from $F_i$ by a single edge exchange.