论文标题
$ k_n $的简单图纸中兼容跨越树
Compatible Spanning Trees in Simple Drawings of $K_n$
论文作者
论文摘要
对于简单的图形$ d $的完整图$ k_n $，如果它们的联合是平面，则两个（平面）亚抽奖是兼容的。令$ \ MATHCAL {T} _D $为$ d $和$ \ \ \ \ \ \ \ \ \ \ \ \ \ mathcal {f}（\ Mathcal {t} _d）$的所有平面的集合，是一个兼容图，是每个元素在$ \ Mathcal {t} _d $和两个vertice中都具有$ \ Mathcal {t} _d $和两个vertice的兼容性，并且仅相互构成。一方面，如果$ \ Mathcal {f}（\ Mathcal {t} _d）$显示，如果$ d $是圆柱形，单调或强烈的C-主酮绘图，则连接。另一方面，我们表明$ \ Mathcal {f}（\ Mathcal {t} _d）$的子图也连接了。在所有情况下，相应兼容图的直径最多在$ n $中是线性的。
For a simple drawing $D$ of the complete graph $K_n$, two (plane) subdrawings are compatible if their union is plane. Let $\mathcal{T}_D$ be the set of all plane spanning trees on $D$ and $\mathcal{F}(\mathcal{T}_D)$ be the compatibility graph that has a vertex for each element in $\mathcal{T}_D$ and two vertices are adjacent if and only if the corresponding trees are compatible. We show, on the one hand, that $\mathcal{F}(\mathcal{T}_D)$ is connected if $D$ is a cylindrical, monotone, or strongly c-monotone drawing. On the other hand, we show that the subgraph of $\mathcal{F}(\mathcal{T}_D)$ induced by stars, double stars, and twin stars is also connected. In all cases the diameter of the corresponding compatibility graph is at most linear in $n$.
