On the complexity of the balanced vertex ordering problem

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. [Discrete Applied Math. 148:27―48, 2005]. 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 to close 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 four and for 5-regular graphs. On the other hand, we introduce a polynomial time algorithm that determines whetherthere 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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2007, 9 (1), pp.193--202
Liste complète des métadonnées

Littérature citée [9 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00966505
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mercredi 26 mars 2014 - 16:59:22
Dernière modification le : samedi 3 mars 2018 - 01:04:58
Document(s) archivé(s) le : jeudi 26 juin 2014 - 11:55:33

Fichier

503-2521-1-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00966505, version 1

Collections

Citation

Jan Kára, Jan Kratochvil, David R. Wood. On the complexity of the balanced vertex ordering problem. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2007, 9 (1), pp.193--202. 〈hal-00966505〉

Partager

Métriques

Consultations de la notice

87

Téléchargements de fichiers

295