Minimum Linear Arrangement of Series-Parallel Graphs

Martina Eikel, Christian Scheideler, Alexander Setzer

We present a factor $14D^2$ approximation algorithm for the minimum linear arrangement problem on series-parallel graphs, where $D$ is the maximum degree in the graph. Given a suit…