On the Complezity of the Balanced Vertez Ordering Problem
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 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 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.
Jan Kara Jan Kratochvil David R. Wood
Department of Applied Mathematics, Faculty of Mathematics and Physics Charles University, Prague, Cz Departament de Matematica Aplicada II Universitat Politecnica de Catalunya, Barcelona, Spain
国际会议
The 11th Annual International Computing and Combinatorics Conference COCOON 2005(第11届国际计算和组合会议)
昆明
英文
849-858
2005-08-01（万方平台首次上网日期，不代表论文的发表时间）