Abstract of Paper

Starting with nondeterminism: the systematic derivation of linear-time graph layout algorithms
by ans L. Bodlaender, Michael R. Fellows, and Dimitrios M. Thilikos

Abstract:

This paper investigates algorithms for some related graph parameters.
Each of these asks for a linear ordering of the vertices of the graph (or can
be formulated as such), and there are constructive linear time algorithms for
the fixed parameter versions of the problems.
Examples are cutwidth, pathwidth, and directed or weighted variants of these.
However, these algorithms
have complicated technical details. This paper attempts to present ideas
in these algorithms in a different more easily accessible manner, by
showing that the algorithms can be obtained by a stepwise modification
of a trivial hypothetical non-deterministic algorithm.

The methodology is applied for a generalisation of the cutwidth problem to
weighted mixed graphs. As a consequence, we obtain new algorithmic results for
various problems like modified cutwidth, and rederive
known results for other related problems with simpler proofs.