论文标题
在完整图的简单图中找到平面结构的扭曲方法
Twisted Ways to Find Plane Structures in Simple Drawings of Complete Graphs
论文作者
论文摘要
简单的图纸是图形的图纸，其中边缘为Jordan Arcs，每对边缘最多共享（一个正确的交叉或一个常见的端点）。我们介绍了一种特殊的简单图纸，我们称之为广义扭曲图纸。如果有一个$ o $ $ $ $ $ o $散发出图纸的每个边缘，则简单的图形是概括性扭曲的。 通过此新类的简单图纸，我们显示了完整图的每一个简单图纸都包含$ω（n^{\ frac {\ frac {1} {2}} {2}}）$成对偏置边缘和长度$ω（\ frac {\ frac {\ log n} {\ log log n} {\ log \ log \ log n n}）$。两种结果都比以前已知的最佳下限有所改善。在途中，我们显示了有关广义扭曲图纸的几个结构性结果和特性。我们进一步提出了广义扭曲图的不同特征，这可能具有独立的兴趣。
Simple drawings are drawings of graphs in which the edges are Jordan arcs and each pair of edges share at most one point (a proper crossing or a common endpoint). We introduce a special kind of simple drawings that we call generalized twisted drawings. A simple drawing is generalized twisted if there is a point $O$ such that every ray emanating from $O$ crosses every edge of the drawing at most once and there is a ray emanating from $O$ which crosses every edge exactly once. Via this new class of simple drawings, we show that every simple drawing of the complete graph with $n$ vertices contains $Ω(n^{\frac{1}{2}})$ pairwise disjoint edges and a plane path of length $Ω(\frac{\log n }{\log \log n})$. Both results improve over previously known best lower bounds. On the way we show several structural results about and properties of generalized twisted drawings. We further present different characterizations of generalized twisted drawings, which might be of independent interest.
