Linear layout of graphs/digraphs is one of the classical and important
optimization problems that have many practical applications.:
Recently Tamaki proposed an $O(mn^{k+1})$-time and $O(n^k)$-space algorithm for testing whether the pathwidth (or vertex separation) of a given digraph with $n$ vertices and $m$ edges is at most $k$.
In this paper, we show that linear layout of digraphs with an objective function such as cutwidth, minimum linear arrangement,
vertex separation (or pathwidth) and sum cut can be formulated as a linear layout problem on a submodular system $(V,f)$
and then propose a simple framework of search tree algorithms
for finding a linear layout (a sequence of $V$)
with a bounded width that minimizes a given cost function.:
According to our framework, we obtain
an $O( k m n^{2k })$-time and $O(n+m)$-space algorithm for
testing whether the pathwidth
of a given digraph is at most $k$.