...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Random structures & algorithms >Biplanar Crossing Numbers. II. Comparing Crossing Numbers and Biplanar Crossing Numbers Using the Probabilistic Method
【24h】

Biplanar Crossing Numbers. II. Comparing Crossing Numbers and Biplanar Crossing Numbers Using the Probabilistic Method

机译：双平面交叉编号。二。使用概率方法比较交叉数和双平面交叉数

获取原文
获取原文并翻译 | 示例
   

获取外文期刊封面封底 >>

       
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

The biplanar crossing number cr(2)(G) of a graph G is min(G1UG2=G){cr(G(1)) + cr(G(2))}, where cr is the planar crossing number. We show that cr2(G) <= (3/8)cr(G). Using this result recursively, we bound the thickness by Theta(G) - 2 <= Kcr(2)(G)0.4057 log(2)n with some constant K. A partition realizing this bound for the thickness can be obtained by a polynomial time randomized algorithm. We show that for any size exceeding a certain threshold, there exists a graph G of this size, which simultaneously has the following properties: cr(G) is roughly as large as it can be for any graph of that size, and cr(2)(G) is as small as it can be for any graph of that size. The existence is shown using the probabilistic method. (C) 2008 Wiley Periodicals, Inc. Random Struct. Alg., 33, 480-496, 2008
机译：图G的双平面交叉数cr（2）（G）是min（G1UG2 ＝ G）{cr（G（1））+ cr（G（2））}，其中cr是平面交叉数。我们证明cr2（G）<=（3/8）cr（G）。递归地使用此结果，我们将厚度通过Theta（G）-2 <= Kcr（2）（G）0.4057 log（2）n加上一些常数K来限制。可以通过多项式获得实现厚度限制的分区时间随机算法。我们表明，对于任何超过特定阈值的大小，都存在该大小的图G，同时具有以下属性：cr（G）几乎与该大小的任何图一样大，并且cr（2 ）（G）尽可能小。使用概率方法显示存在。 （C）2008 Wiley Periodicals，Inc.随机结构。 Alg。，33，480-496，2008

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号