Topological Graphs with No Large Grids
Topological Graphs with No Large Grids
复制标题
没有大网格的拓扑图
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
G. Tóth
中科院分区：
文献类型：
--
作者：
J. Pach;R. Pinchasi;M. Sharir;G. Tóth
设G是一个有n个顶点的拓扑图，即，在平面上画的一种图，其边画成简单的乔丹曲线。证明了对任意常数k，l，存在另一个常数C（k，l），使得若G至少有C（k，l）n条边，则它包含k× l-格状构形，即它包含k+l条边，使得前k条边中的每一条与后l条边中的每一条相交.此外，可以要求前k条边入射到同一顶点。
Let G be a topological graph with n vertices, i.e., a graph drawn in the plane with edges drawn as simple Jordan curves. It is shown that, for any constants k,l, there exists another constant C(k,l), such that if G has at least C(k,l)n edges, then it contains a k×l-gridlike configuration, that is, it contains k+l edges such that each of the first k edges crosses each of the last l edges. Moreover, one can require the first k edges to be incident to the same vertex.