Topological Bandwidth
Fillia S. Makedon, Christos H. Papadimitriou, Ivan Hal Sudborough · Lecture notes in computer science · 1983
An assignment of unique integers to the vertices of a graph is called a linear layout. The bandwidth of a linear layout is the maximum difference between integers assigned to adjacent vertices. The bandwidth of a graph is the minimum bandwidth of any layout of the graph. The topological bandwidth of a graph is the minimum bandwidth of all graphs that can be obtained from this graph by subdividing its edges with some number of degree two vertices. Topological bandwidth is compared to other, seemingly unrelated, parameters of a graph its cutwidth [5], [8], its modified cutwidth [12], its search number [16], and its node search number [20]. It is shown that the topological bandwidth of a graph is never greater than its modified cutwidth plus one and never smaller than its node search number. Furthermore, for any degree 3 graph G, the topological bandwidth of G is identical to the modified cutwidth of G plus one and is also identical to the node search number of G. It is also shown that the topological bandwidth of any graph is never greater than its cutwidth and never less than its search number minus one. The topological bandwidth of a binary tree is also considered. A forbidden subtree characterization of topological bandwith k, for each $k\geqq 1$, in binary trees is given. It is also noted that there is a $O ( n\log n )$ algorithm to compute the topological bandwidth of an arbitrary binary tree and that the topological bandwidth of a complete binary tree of height h is $\lceil h /2 \rceil $. Furthermore, a lower bound on the size of any binary tree with topological bandwidth k is given. It is shown that the problem of determining, given a graph G and an integer k, whether the topological bandwidth of G is at most k is NP-complete. In fact, the problem is shown to be NP-complete even when restricted to graphs with degree 3. It is also shown that the Min Cut Linear Arrangement problem, the Search Number problem, the Modified Cutwidth problem, and the Node Search Number problem are NP-complete even when restricted to graphs with maximum vertex degree three. Finally, graphs with topological bandwidth two are characterized. This suggests a linear time algorithm for recognizing graphs with topological bandwidth two. It is also noted that the problem of deciding, given a graph G, whether the topological bandwidth of G is at most k can be solved in $O ( | G |^k )$ steps, for all $k\geqq 1$.