On the Complexity of the Balanced Vertex Ordering Problem

. We consider the problem of nding a balanced ordering of the vertices of a graph. More precisely, we want to minimise the sum, taken over all vertices v, of the di erence between the number of neigh-bours to the left and right of v. This problem, which has applications in graph drawing, was recently introduced by Biedl et al. [1]. They proved that the problem is solvable in polynomial time for graphs with maxi-mum degree three, but NP-hard for graphs with maximum degree six. One of our main results is closing the gap in these results, by proving NP-hardness for graphs with maximum degree four. Furthermore, we prove that the problem remains NP-hard for planar graphs with maxi-mum degree six and for 5-regular graphs. On the other hand we present a polynomial time algorithm that determines whether there is a vertex ordering with total imbalance smaller than a xed constant, and a poly-nomial time algorithm that determines whether a given multigraph with even degrees has an `almost balanced'ordering.