کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
414675 | 681003 | 2014 | 14 صفحه PDF | دانلود رایگان |
A topological graph G is a graph drawn in the plane with vertices represented by points and edges represented by continuous arcs connecting the vertices. If every edge is drawn as a straight-line segment, then G is called a geometric graph. A k-grid in a topological graph is a pair of subsets of the edge set, each of size k, such that every edge in one subset crosses every edge in the other subset. It is known that every n-vertex topological graph with no k -grid has Ok(n)Ok(n) edges.We conjecture that the number of edges of every n-vertex topological graph with no k-grid such that all of its 2k edges have distinct endpoints is Ok(n)Ok(n). This conjecture is shown to be true apart from an iterated logarithmic factor log⁎n. A k-grid is natural if its edges have distinct endpoints, and the arcs representing each of its edge subsets are pairwise disjoint. We also conjecture that every n-vertex geometric graph with no natural k -grid has Ok(n)Ok(n) edges, but we can establish only an Ok(nlog2n) upper bound. We verify the above conjectures in several special cases.
Journal: Computational Geometry - Volume 47, Issue 7, August 2014, Pages 710–723