首页> 外文会议>International symposium on graph drawing >Density Theorems for Intersection Graphs of t-Monotone Curves
【24h】

Density Theorems for Intersection Graphs of t-Monotone Curves

机译:t-单调曲线的相交图的密度定理

获取原文

摘要

A curve γ in the plane is t-monotone if its interior has at most t - 1 vertical tangent points. A family of t-monotone curves F is simple if any two members intersect at most once. It is shown that if F is a simple family of n t-monotone curves with at least ∈n~2 intersecting pairs (disjoint pairs), then there exists two subfamilies F_1, F_2 is contained in F of size δn each, such that every curve in F_1 intersects (is disjoint to) every curve in F_2, where δ depends only on ∈. We apply these results to find pairwise disjoint edges in simple topological graphs.
机译:如果平面中的曲线γ的内部最多具有t-1个垂直切点,则它是t单调的。如果任意两个成员最多相交一次,则t单调曲线F族很简单。结果表明,如果F是n个t单调曲线的简单族,且具有至少∈n〜2个相交对(不相交对),则存在两个子族F_1,每个F_2都包含δn大小的F,每个子族F_1中的曲线与F_2中的每条曲线相交(不相交),其中δ仅取决于∈。我们应用这些结果在简单的拓扑图中找到成对的不相交的边。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号