We relate two concepts in graph theory and algorithmic complexity, namely the search number and the vertex separation of a graph. Let s (G ) denote the search number and vs (G ) denote the vertex separation of a connected, undirected graph G . We show that vs (G ) ≤ s (G ) ≤ vs (G ) + 2 and we give a simple We characterize those trees having a given vertex separation and describe the smallest such trees. We also note that there exist trees for which the difference between search number and vertex separation is indeed 2. We give algorithms that, for any tree T , compute vs (T ) in linear time and compute an optimal layout with respect to vertex separation in time O (n log n ). Vertex separation has previously been related to progressive black/white pebble demand and has been shown to be identical to a variant of search number, node search number, and to path width, which has been related directly to gate matrix layout cost. All these properties are known to be computationally intractable. For fixed k , an O (n log 2 n ) algorithm is known which decides whether a graph has path width at most k .
Relations between the search number and vertex separation are established in REF and methods to compute the vertex-separation layout problem were shown to be applicable to compute strategies in O(n log n) and determine the search number in O(n) for certain instances of the problem.
The Vertex Separation and Search Number of a Graph
Inf. Comput.
Mathematics Computer Science