The Vertex Separation of Trees

Pathwidth, node search number and vertex separation are different ways of defining the same notion. Path decompositions and search strategies can be derived from linear layouts. Computing this parameter is, in general, an NP-complete problem and remains NP-complete even for planar graphs of maximum degree three.

In:

The Vertex Separation and Search Number of a Graph",
J. A. Ellis and I. H. Sudborough and J. S. Turner,
Information and Computation, vol. 113, pp. 50--79, (1994),

we showed how to compute the vertex separation of trees in linear time. That paper suggested an algorithm for the computation of optimal layouts in time O(n log n).

It was not until later that a way of computing the layouts themselves in linear time was described in:

"Computing optimal strategies for trees in linear time", K. Skodinis,
Proceedings of the 8th Annual European Symposium on Algorithms, pp. 403--414, (2000).

A reformulation of this method can also be found in:

"Computing the Vertex Separation of Unicyclic Graphs",
J. Ellis and M. Markov, Information and Computation, Volume 192, Issue 2, pp. 123-161, 2004.