• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Graph Drawing; Lecture Notes in Computer Science; 4372 >Planar Decompositions and the Crossing Number of Graphs with an Excluded Minor
【24h】

Planar Decompositions and the Crossing Number of Graphs with an Excluded Minor

机译：平面分解和具有次要图的图的交叉数

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

摘要

Tree decompositions of graphs are of fundamental importance in structural and algorithmic graph theory. Planar decompositions generalise tree decompositions by allowing an arbitrary planar graph to index the decomposition. We prove that every graph that excludes a fixed graph as a minor has a planar decomposition with bounded width and a linear number of bags. The crossing number of a graph is the minimum number of crossings in a drawing of the graph in the plane. We prove that planar decompositions are intimately related to the crossing number, in the sense that a graph with bounded degree has linear crossing number if and only if it has a planar decomposition with bounded width and linear order. It follows from the above result about planar decompositions that every graph with bounded degree and an excluded minor has linear crossing number. Analogous results are proved for the convex and rectilinear crossing numbers. In particular, every graph with bounded degree and bounded tree-width has linear convex crossing number, and every K_(3,3)-minor-free graph with bounded degree has linear rectilinear crossing number.
机译：图的树分解在结构图和算法图论中至关重要。平面分解通过允许任意平面图索引分解来概括树分解。我们证明，每个排除固定图作为次要图的图都具有平面分解，该分解具有有限的宽度和线性的袋数。图的交叉数是平面图中图形的最小交叉数。我们证明平面分解与相交数密切相关，从某种意义上说，当且仅当有界图具有边界宽度和线性阶数的平面分解时，带界度图才具有线性相交数。从上面关于平面分解的结果可以得出，每个有界度和排除次要图都具有线性相交数。证明了凸和直线交叉数的相似结果。特别是，每个有界度和有界树宽的图都具有线性凸交叉数，每个有界度的K_（3,3）-次要无图都具有线性直线交叉数。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号