On the Complexity of the Balanced Vertex Ordering Problem

Abstrakt

We consider the problem of finding a balanced ordering of the vertices of a graph. More precisely, we want to minimise the sum, taken over all vertices $v$, of the difference between the number of neighbours to the left and right of $v$.

We show that this problem is NP-complete for graphs with maximum degree four, 5-regular graphs and planar graphs with maximum degree six. We introduce a polynomial time algorithm that determines whether there is a vertex ordering with total imbalance smaller than a fixed constant.