The Vertex Separation of Unicyclic Graphs

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.


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).

We reformulate this method and show how to compute the vertex separation of unicylic graphs in:

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

This algorithm runs in time O(n log n), but it seems that adding one edge to a tree necessitates a considerably more elaborate algorithm.