Edge-intersection graphs of grid paths: The bend-number
Edge-intersection graphs of grid paths: The bend-number
复制标题
网格路径的边相交图：弯曲数
DOI：
10.1016/j.dam.2013.10.035
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Torsten Ueckerdt
中科院分区：
文献类型：
--
作者：
Daniel Heldt;Kolja B. Knauer;Torsten Ueckerdt
本文研究了平面网格中路径的边交图，其中引入了一个参数bend数，即每个顶点都由一条网格路径表示，且两个顶点相邻当且仅当两条网格路径至少共享一条网格边。弯曲数是最小的k，使得具有至多k个弯曲的网格路径每个足以表示给定的图。该参数与图形的区间数和轨迹数有关。我们证明了对每个k，都有一个弯曲数为k的图。此外，我们还根据图的退化度、树宽、边团覆盖和最大度给出了图的弯曲数的新的上界和下界。进一步给出了Km，n的弯曲数的界，并对某些m和n对精确地确定了它.最后，我们证明了识别单弯图是NP-完全的，在这个领域提供了第一个这样的结果。
We investigate edge-intersection graphs of paths in the plane grid, regarding a parameter called the bend-number, ie, every vertex is represented by a grid path and two vertices are adjacent if and only if the two grid paths share at least one grid-edge. The bend-number is the minimum k such that grid-paths with at most k bends each suffice to represent a given graph. This parameter is related to the interval-number and the track-number of a graph. We show that for every k there is a graph with bend-number k. Moreover we provide new upper and lower bounds of the bend-number of graphs in terms of degeneracy, treewidth, edge clique covers and the maximum degree. Furthermore we give bounds on the bend-number of K m, n and determine it exactly for some pairs of m and n. Finally, we prove that recognizing single-bend graphs is NP-complete, providing the first such result in this field.
登录
查看更多内容
每个外平面图都是两个区间图的并集
DOI：
--
发表时间：
1999
期刊：
影响因子：
--
作者：
A. Kostochka;D. West
通讯作者：
D. West
关于平面图中的一些树木现象
DOI：
--
发表时间：
2005
期刊：
Electron. Notes Discret. Math.
影响因子：
--
作者：
D. Gonçalves;P. Ochem
通讯作者：
P. Ochem
影响因子：
1.1
作者：
Minghui Jiang
通讯作者：
Minghui Jiang
覆盖图表的三种方法
DOI：
10.1016/j.disc.2015.10.023
发表时间：
2016
期刊：
Discret. Math.
影响因子：
--
作者：
Kolja B. Knauer;Torsten Ueckerdt
通讯作者：
Torsten Ueckerdt
关于平面图和外平面图的弯曲数
DOI：
--
发表时间：
2011
期刊：
Latin American Symposium on Theoretical Informatics
影响因子：
--
作者：
Daniel Heldt;K. Knauer;T. Ueckerdt
通讯作者：
T. Ueckerdt