A note on planar graphs with large width parameters and small grid-minors

Grigoriev A.; Marchal B.; Usotskaya N.; Todinca I.

首页> 外文期刊>Discrete Applied Mathematics >A note on planar graphs with large width parameters and small grid-minors

【24h】

A note on planar graphs with large width parameters and small grid-minors

机译：关于具有较大宽度参数和较小网格网格的平面图的注释

获取原文

获取原文并翻译 | 示例

掌桥外文数据库（机构版） >>

开具论文收录证明 >>

文献代查 >>

页面导航

摘要
著录项
相似文献
相关主题

摘要

Given a graph G with tree-width ω(G), branch-width β(G), and side size of the largest square grid-minor θ(G), it is known that θ(G)≤β(G)≤ω(G)+1≤32β(G). In this paper, we introduce another approach to bound the side size of the largest square grid-minor specifically for planar graphs. The approach is based on measuring the distances between the faces in an embedding of a planar graph. We analyze the tightness of all derived bounds. In particular, we present a class of planar graphs where θ(G)=β(G)<ω(G)=?32θ(G)?-1.

机译：给定一个具有树宽ω（G），分支宽度β（G）和最大正方形网格次方θ（G）的边尺寸的图G，已知θ（G）≤β（G）≤ ω（G）+1≤32β（G）。在本文中，我们引入了另一种方法来绑定最大的方形栅格小边的大小，专门用于平面图。该方法基于在平面图的嵌入中测量面之间的距离。我们分析所有派生边界的紧密度。特别地，我们提出了一类平面图，其中θ（G）=β（G）<ω（G）=？32θ（G）？-1。

著录项

来源
《Discrete Applied Mathematics》 |2012年第8期|共8页
作者
Grigoriev A.; Marchal B.; Usotskaya N.; Todinca I.;
展开▼
作者单位

展开▼
收录信息
原文格式 PDF
正文语种 eng
中图分类离散数学;
关键词
Branch-width; Grid-minor; Planar graph; Tree-width;

机译：分支宽度;网格小;平面图;树宽;

相似文献

外文文献
中文文献
专利

1. A note on planar graphs with large width parameters and small grid-minors [J] . Grigoriev A., Marchal B., Usotskaya N., Discrete Applied Mathematics . 2012,第7a8期

机译：关于具有较大宽度参数和较小网格网格的平面图的注释
2. On quasi-planar graphs: Clique-width and logical description [J] . Courcelle Bruno Discrete Applied Mathematics . 2020,第1期

机译：关于准平面图：Clique-宽和逻辑描述
3. C-Planarity Testing of Embedded Clustered Graphs with Bounded Dual Carving-Width [J] . Giordano Da Lozzo, David Eppstein, Michael T. Goodrich, LIPIcs : Leibniz International Proceedings in Informatics . 2019,第1期

机译：有界双雕刻宽度的嵌入式聚类图的C平面测试
4. An Estimate of the Tree-Width of a Planar Graph Which Has Not a Given Planar Grid as a Minor [C] . K.Yu. Gorbunov Graph-Theoretic concepts in computer science . 1998

机译：没有给定的平面网格作为次要平面图的树宽的估计
5. Part I. Isocratic and gradient elution reversed-phase liquid chromatography for the estimation of the hydrophobicity parameter log k(',w): Applications to newer generation stationary phases. Part II. Planar electrochromatographic instrumental design and results. [D] . Tate, Peter Anthony. 2005

机译：第一部分。等度和梯度洗脱反相液相色谱法，用于估计疏水性参数log k（'，w）：在新一代固定相中的应用。第二部分平面电色谱仪器的设计和结果。
6. Semi-Automatic Measurement of the Airway Dimension by Computed Tomography Using the Full-Width-Half-Maximum Method: a Study on the Measurement Accuracy according to the CT Parameters and Size of the Airway [O] . Namkug Kim, Joon Beom Seo, Koun-Sik Song, 2008

机译：半自动最大断面扫描技术通过半断层扫描半自动测量气道尺寸：根据CT参数和气道尺寸的测量精度研究
7. A note on planar graphs with large width parameters and small grid-minors [O] . 2012

机译：关于具有较大宽度参数和较小网格网格的平面图的注释
8. Operational parameters of an opto-electronic neural network employing fixed planar holographic interconnects. [R] . Keller, P. E., Gmitro, A. F. 1993

机译：采用固定平面全息互连的光电神经网络的操作参数。

A note on planar graphs with large width parameters and small grid-minors

摘要

著录项

相似文献

相关主题

期刊订阅