Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
418967 | Discrete Applied Mathematics | 2008 | 10 Pages |
Abstract
The neighbourhood-width of a graph G=(V,E)G=(V,E) is introduced in [F. Gurski, Linear layouts measuring neighbourhoods in graphs, Discrete Math. 306 (15) (2006) 1637–1650.] as the smallest integer k such that there is a linear layout ϕ:V→{1,…,|V|}ϕ:V→{1,…,|V|} such that for every 1⩽i<|V|1⩽i<|V| the vertices uu with ϕ(u)⩽iϕ(u)⩽i can be divided into at most k subsets each members having the same neighbours with respect to the vertices vv with ϕ(v)>iϕ(v)>i.In this paper we show first bounds for the neighbourhood-width of general graphs, caterpillars, trees and grid graphs and give applications of the layout parameter neighbourhood-width in graph drawing and VLSI design.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Frank Gurski,