论文标题
点集的几何图的交叉和与几何图的家族
Crossing and intersecting families of geometric graphs on point sets
论文作者
论文摘要
让$ s $是一组$ n $点的$ n $点。如果有共同点，则两个线段连接$ s $交叉点的点。如果有两个边缘，每个图中有两个，一个$ s $ cross的顶点几何图，一个$ s $交叉。一组带有$ S $顶点的顶点分离几何图被称为相互交叉，如果其中有两个交叉。 我们表明存在一个常数的$ c $，使得从任何$ n $互跨三角形的家庭中，人们总是可以获得一个至少$ n^c $相互交叉的$ 2 $ paths的家庭（每个都是从一个三角形中删除优势的结果），然后提供$ c $的示例，这意味着$ c $不能以$ c $比$ 2/3 $更大。对于每$ n $，我们都会确定一组$ n $点的哈密顿周期可能具有的最大交叉数。接下来，我们构建了一个最长的完美匹配的点集，其中不包含交叉点。我们还考虑由水平和垂直线段组成的边缘连接到$ s $的点对，我们称之为肘部，并证明在任何点集合$ s $中都存在$ \ lfloor n/4 \ rfloor $ pertex n/4 \ rfloor $ pertex distex discoint discoint buthe sprothally Crossing Elbows。此外，我们展示了一个积分套装，该套装承认不超过$ N/3 $相互交叉的肘部。 最终，我们研究了图形的相交家族，这些家族不一定是顶点脱节的。一组带有$ s $顶点的边缘分离图称为一个相交家族，如果对于集合中的任何两个图，我们都可以在每个图中选择一个边缘，以使它们交叉。我们证明了Lara和Rubio-Montiel的猜想，即，任何设定$ n $ n $点的$ s $ s $ n $ suption in Contristion Points都承认了一个相交三角形的家族，其中有二次元素。 在整个工作中还获得了其他一些结果。
Let $S$ be a set of $n$ points in the plane in general position. Two line segments connecting pairs of points of $S$ cross if they have an interior point in common. Two vertex disjoint geometric graphs with vertices in $S$ cross if there are two edges, one from each graph, which cross. A set of vertex disjoint geometric graphs with vertices in $S$ is called mutually crossing if any two of them cross. We show that there exists a constant $c$ such that from any family of $n$ mutually crossing triangles, one can always obtain a family of at least $n^c$ mutually crossing $2$-paths (each of which is the result of deleting an edge from one of the triangles) and then provide an example that implies that $c$ cannot be taken to be larger than $2/3$. For every $n$ we determine the maximum number of crossings that a Hamiltonian cycle on a set of $n$ points might have. Next, we construct a point set whose longest perfect matching contains no crossings. We also consider edges consisting of a horizontal and a vertical line segment joining pairs of points of $S$, which we call elbows, and prove that in any point set $S$ there exists a family of $\lfloor n/4 \rfloor$ vertex disjoint mutually crossing elbows. Additionally, we show a point set that admits no more than $n/3$ mutually crossing elbows. Finally we study intersecting families of graphs, which are not necessarily vertex disjoint. A set of edge disjoint graphs with vertices in $S$ is called an intersecting family if for any two graphs in the set we can choose an edge in each of them such that they cross. We prove a conjecture by Lara and Rubio-Montiel, namely, that any set $S$ of $n$ points in general position admits a family of intersecting triangles with a quadratic number of elements. Some other results are obtained throughout this work.
