On the complexity of the balanced vertex ordering problem

Jan Kára, Jan Kratochvi l, David R. Wood

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

8 Citations (Scopus)

Abstract

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. 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 maximum degree three, but NΡ-hard for graphs with maximum degree six. One of our main results is closing the gap in these results, by proving NΡ-hardness for graphs with maximum degree four. Furthermore, we prove that the problem remains NΡ-hard for planar graphs with maximum 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 fixed constant, and a polynomial time algorithm that determines whether a given multigraph with even degrees has an 'almost balanced' ordering.
Original languageEnglish
Title of host publicationComputing and combinatorics
PublisherSpringer
Pages849-858
Number of pages10
Volume3595
DOIs
Publication statusPublished - 2005
Externally publishedYes

Publication series

NameLecture Notes in Comput. Sci.
PublisherSpringer, Berlin

Cite this