...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of Combinatorial Theory, Series B >Crossing number, pair-crossing number, and expansion
【24h】

Crossing number, pair-crossing number, and expansion

机译：交叉数，对交叉数和扩展

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

The crossing number cr(G) of a graph G is the minimum possible number of edge crossings in a drawing of G in the plane, while the pair-crossing number pcr(G) is the smallest number of pairs of edges that cross in a drawing of G in the plane. While cr(G) greater than or equal topcr(G) holds trivially, it is not known whether a strict inequality can ever occur (this question was raised by Mohar and Pach and Toth). We aim at bounding cr(G) in terms of pcr(G). Using the methods of Leighton and Rao, Bhatt and Leighton, and Even, Guha and Schieber, we prove that cr(G) = O(log(3) n(pcr(G) + ssqd(G))), where n = V(G) and ssqd(G) = Sigma(nuis an element ofV(G)) deg(G)(v)(2). One of the main steps is an analogy of the well-known lower bound cr(G) = Omega(b(G)(2)) - O(ssqd(G)), where b(G) is the bisection width of G, that is, the smallest number of edges that have to be removed so that no component of the resulting graph has more than 2/3 n vertices. We show that pcr(G) = Omega(b(G)(2)/log(2) n) - O(ssqd(G)).We also prove by similar methods that a graph G with crossing number k = cr(G) > Crootssqd(G) m log(2) n has a nonplanar subgraph on at most O(Deltanm log(2) n/k) vertices, where in is the number of edges, A is the maximum degree in G, and C is a suitable sufficiently large constant. (C) 2004 Elsevier Inc. All rights reserved.
机译：图G的交叉数cr（G）是平面中G的图形中的最小边交叉数，而对交叉数pcr（G）是在a中交叉的最小边对数。在平面上绘制G。尽管cr（G）大于或等于topcr（G）成立，但尚不知道是否会出现严格的不平等现象（Mohar和Pach和Toth提出了这个问题）。我们旨在以pcr（G）为边界来限制cr（G）。使用Leighton和Rao，Bhatt和Leighton以及Even，Guha和Schieber的方法，我们证明cr（G）= O（log（3）n（pcr（G）+ ssqd（G））），其中n = V（G）和ssqd（G）= Sigma（是V（G）的元素）deg（G）（v）（2）。主要步骤之一是类比众所周知的下界cr（G）= Omega（b（G）（2））-O（ssqd（G）），其中b（G）是G的对分宽度，也就是说，必须删除的边的最小数量，以使所得图形的组成部分中的顶点均不超过2/3 n个。我们证明pcr（G）= Omega（b（G）（2）/ log（2）n）-O（ssqd（G））。我们还通过类似方法证明了交叉数为k = cr（ G）> Crootssqd（G）m log（2）n在最多O（Deltanm log（2）n / k）顶点上具有一个非平面子图，其中in是边数，A是G中的最大度数，并且C是适当的足够大的常数。 （C）2004 Elsevier Inc.保留所有权利。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号