Minimisation de la Longueur Verticale dans les Diagrammes en Barres Liés

Informations Fondamentales

• ID de l'article: 2511.16812
• Titre: Minimizing Vertical Length in Linked Bar Charts
• Auteurs: Steven van den Broek (TU Eindhoven), Marc van Kreveld (Université d'Utrecht), Wouter Meulemans (TU Eindhoven), Arjen Simons (TU Eindhoven)
• Classification: cs.CG (Géométrie Computationnelle)
• Date de publication/Conférence: Soumis à arXiv le 20 novembre 2025, recherche initiée lors de l'atelier AGA 2024
• Lien de l'article: https://arxiv.org/abs/2511.16812

Résumé

Les diagrammes en barres liés (Linked Bar Chart) constituent une version améliorée des diagrammes en barres traditionnels, où chaque barre est divisée en plusieurs blocs (blocks) reliés entre eux par des lignes orthogonales qui doivent traverser les barres intermédiaires. L'ordre d'arrangement des blocs affecte directement la lisibilité des lignes de connexion. Cet article étudie le problème algorithmique de minimisation de la longueur verticale des lignes de connexion pour un ordre de barres fixe. Le défi principal réside dans les « liens dépendants » (dependent links), dont la longueur verticale ne peut être optimisée indépendamment. L'étude montre que : si les liens dépendants forment une structure de forêt, le problème peut être résolu en temps O(nm) (n barres, m liens) ; si les liens dépendants entre barres non adjacentes forment une forêt, il peut être résolu en temps O(n⁴m) ; dans le cas général, le problème est traitable à paramètre fixe (FPT) en fonction du degré maximal des barres.

Contexte et Motivation de la Recherche

1. Problème à Résoudre

Les diagrammes en barres traditionnels ne peuvent représenter que des données d'une seule catégorie, mais dans de nombreux scénarios pratiques, certaines valeurs ne sont pas exclusivement attribuées à une catégorie unique, mais sont plutôt associées à plusieurs catégories. Par exemple :

• Quantités partagées : le volume de communication entre comptes apparaît simultanément dans les statistiques de deux comptes
• Incertitude appariée : électeurs hésitant entre deux partis dans les sondages électoraux ; contribution des usines frontalières à la pollution des deux pays

2. Importance du Problème

La visualisation de données inter-catégories constitue un besoin important en analyse de données. Les diagrammes en barres liés représentent ces relations en ajoutant des lignes de connexion entre les barres, mais l'ordre d'empilement des blocs affecte directement la longueur verticale des lignes de connexion, influençant ainsi la lisibilité et l'esthétique du graphique.

3. Limitations des Méthodes Existantes

• Les diagrammes en barres standard ne peuvent pas visualiser directement les valeurs inter-catégories
• Bien que les diagrammes en barres liés aient été récemment proposés 17, le problème d'optimisation de l'ordre d'empilement des blocs n'a pas encore été étudié
• Les problèmes traditionnels de dessin de graphes (comme l'intégration de livres à une page) ne considèrent que l'ordre des sommets, pas cette nouvelle dimension d'empilement des blocs

4. Motivation de la Recherche

Cet article étudie pour la première fois de manière systématique le problème algorithmique de minimisation de la longueur verticale des liens dans les diagrammes en barres liés, fournissant une base théorique et des algorithmes efficaces pour cette nouvelle méthode de visualisation.

Contributions Principales

1. Formalisation du problème : Première définition du problème d'optimisation de minimisation de la longueur verticale des liens dans les diagrammes en barres liés, introduction d'une taxonomie classifiant les « liens indépendants » et les « liens dépendants »
2. Algorithme de structure forestière : Preuve que lorsque le sous-graphe de liens dépendants forme une forêt, le problème peut être résolu en temps O(nm) par programmation dynamique (Théorème 3)
3. Algorithme forestier non-adjacent : Preuve que lorsque les liens dépendants non-adjacents forment une forêt, le problème peut être résolu en temps O(n⁴m) (Théorème 6)
4. Algorithme FPT : Preuve que dans le cas général, le problème est traitable à paramètre fixe, le paramètre étant le degré maximal Δ des barres, avec une complexité temporelle O(Δ^(3δ)·δ·n) (Théorème 8)
5. Bornes de complexité inférieure : Preuve que lorsque les sommets peuvent avoir plusieurs blocs non-liés arbitrairement ordonnables, le problème est fortement NP-difficile (Théorème 12)

Détails de la Méthode

Définition de la Tâche

Entrée : Graphe pondéré G = (V, E, w), où :

• V : séquence fixe de n sommets v₁, ..., vₙ
• E ⊆ V² : m arêtes
• w: V ∪ E → ℝ⁺ : fonction de poids (poids des sommets = valeurs d'une seule catégorie, poids des arêtes = valeurs inter-catégories)

Sortie : Ordre d'empilement des blocs dans chaque barre, tel que :

• La longueur verticale totale des liens soit minimale
• Les liens partageant des extrémités ne se croisent pas

Contraintes :

• L'ordre horizontal des barres est fixe
• Les blocs non-liés sont placés au bas de la barre
• Les liens doivent traverser toutes les barres intermédiaires

Concepts Fondamentaux

1. Classification des Types de Liens

L'article classe les liens en deux grandes catégories :

Liens indépendants (IL) : La longueur verticale peut être optimisée indépendamment en plaçant le bloc à une cible fixe t, avec un coût de |t - y| + |t - y'|. Trois cas :

1. Une barre intermédiaire est plus haute que la position la plus élevée possible d'une extrémité → cible = hauteur de la barre intermédiaire la plus élevée H
2. Les intervalles de positions possibles des deux extrémités ne se chevauchent pas → cible = position la plus basse de l'intervalle le plus élevé
3. La position d'une extrémité est fixe (séquence correspondante vide) → cible = cette position fixe

Liens dépendants (DL) : La longueur verticale dépend de la position relative des deux blocs, ne pouvant pas être assignée à une cible statique. Subdivisés en :

• Liens dépendants adjacents (ADL) : reliant des barres adjacentes
• Liens dépendants non-adjacents (NADL) : reliant des barres non-adjacentes

Lemme clé 1 : Le sous-graphe de liens dépendants est un graphe planaire externe (outerplanar), donc sa largeur d'arbre ≤ 2.

2. Représentation des Positions et Calcul des Coûts

Pour un bloc b dans la barre Bⱼ (correspondant à une arête gauche lᵢ ∈ Lⱼ), sa coordonnée verticale du centre est :

y(b, k) = ½h(b) + w(vⱼ) + Σ(x=1 à i-1)h(lₓ) + Σ(x=1 à k)h(rₓ)

où k représente le nombre de blocs droits en dessous.

Fonction de coût :

• Bloc indépendant b en position i : λ(b, i) = |t - y(b, i)|
• Lien dépendant e en position (i,j) :

  λ(e, i, j) = {
    |H - y(b,i)| + |H - y(b',j)|  si les deux extrémités sont sous H
    |y(b,i) - y(b',j)|            sinon
  }
  

Conception des Algorithmes

Algorithme 1 : Liens Dépendants Formant une Forêt (Temps O(nm))

Idée centrale : Utiliser la structure d'arbre pour déterminer l'ordre de traitement des barres, calculer par programmation dynamique de bas en haut.

Étapes de l'algorithme :

1. Pour chaque arbre T de la forêt, choisir une racine arbitraire
2. Pour chaque barre B, soit lₚ* le bloc reliant le nœud parent (lien parent)
3. Définir la table de programmation dynamique :
   • P(B, k) : coût minimal du sous-arbre Tᵦ, avec k blocs droits sous le lien parent
   • D↓(p, q) : coût minimal des p premiers blocs gauches et q premiers blocs droits
   • D↑(p, q) : coût minimal des blocs suivants
4. Stratégie de décomposition : Le bloc lien parent lₚ* en position k divise la barre en deux parties indépendantes :

   P(B, k) = D↓(p*-1, k) + D↑(p*+1, k+1)
   

5. Calcul récursif de D↓ :

   D↓(p, q) = min{
     D↓(p-1, q) + coût(lₚ, q),
     D↓(p, q-1) + coût(rᵧ, p)
   }
   

   
   Pour les blocs dépendants, le coût est : minⱼ λ(e, i, j) + P(B', j)

Analyse de la complexité temporelle :

• Pour chaque barre de degré d, le calcul de la table D nécessite O(d²)
• Précomputation du coût des blocs dépendants : O(d·d')
• Temps total : O(Σd² + Σd·d') = O(nm)

Algorithme 2 : Liens Dépendants Non-Adjacents Formant une Forêt (Temps O(n⁴m))

Défi d'extension : Permettre les liens dépendants adjacents (ADL), nécessitant de gérer des relations de dépendance plus complexes.

Technique clé :

1. Forêt étendue F : contenant tous les NADL et l'ensemble maximal d'ADL (ne formant pas de cycle)
2. Représentation d'état améliorée : P*(B, k, l, r), paramétrée par trois liens dépendants à extrémité unique possibles
3. Traitement des ADL :
   • Soit a←,1, a←,2, ... les ADL de gauche, a→,1, a→,2, ... les ADL de droite
   • Les tables de programmation dynamique D↓(p, q, x, y) et D↑(p, q, x, y) doivent suivre les positions des ADL

Formule récursive (lorsque lₚ est un bloc dépendant) :

D↓(p, q, x, y) = min sur χ de [
  min sur x'(D↓(p-1, q, x', y) + λ(a←,i, χ, x')) +
  min sur k'(P(B', k', x, χ) + λ(lₚ, k', q))
]

Complexité temporelle :

• Pour chaque paire (p,q) : O(Δ³) précomputation + O(Δ³) calcul de D
• Au total O(d²) paires, O(Δ³d²) par barre
• Calcul de P : O(Δ⁴d)
• Temps total : O(n⁴m)

Algorithme 3 : Cas Général - Algorithme FPT (Temps O(Δ^(3δ)·δ·n))

Technique centrale : Décomposition d'arbre (Tree Decomposition)

Cadre algorithmique :

1. Construire une décomposition d'arbre nice (T, X, r) du sous-graphe de liens dépendants G'
   • Largeur d'arbre ≤ 2 (propriété des graphes planaires externes)
   • O(n) nœuds, chaque sac contient au maximum 3 barres
   • Constructible en temps O(n)
2. Définir l'état : P*(u, S₁, S₂, S₃)
   • u : nœud dans la décomposition d'arbre
   • Sᵢ : état de la barre Bᵢ du sac (position de chaque lien dépendant)
   • Représente le coût minimal de tous les blocs et liens du « passé » (past) de u
3. Nombre d'états (Lemme 9) :
   • Par barre : O(Δ^δ) états (fonctions injectives de δ liens dépendants vers Δ positions)
   • Par nœud : O(Δ^(3δ)) états
4. Traitement par type de nœud :
   • Nœud feuille : P*(u) = 0, temps O(1)
   • Nœud de jonction : P*(u, ...) = P*(v, ...) + P*(w, ...), temps O(Δ^(3δ)·δ)
   • Nœud d'introduction : héritage direct du nœud enfant, temps O(Δ^(3δ)·δ)
   • Nœud d'oubli : le plus complexe, doit traiter les blocs indépendants et les liens dépendants de la barre oubliée
5. Traitement du nœud d'oubli (Lemme 11) :

   P*(u, S₁, S₂) = min sur S∈Sf [
     P*(v, S₁, S₂, S) + IL(S) + DL(S, S₁) + DL(S, S₂)
   ]
   

   • Précomputation de Dᵢ,ⱼ(p, q) : coût minimal des sous-ensembles de blocs indépendants, temps O(Δ³)
   • Par état : temps O(Δ^δ·δ)
   • Total : temps O(Δ^(3δ)·δ)

Complexité temporelle : O(n) nœuds × O(Δ^(3δ)·δ) = O(Δ^(3δ)·δ·n)

Corollaires :

• Lorsque Δ = O(1), l'algorithme s'exécute en temps polynomial
• Lorsque seul δ = O(1) (degré de lien dépendant borné), l'algorithme reste en temps polynomial O(n)

Points d'Innovation Technique

1. Taxonomie de classification des liens : La classification indépendant/dépendant permet de décomposer le problème d'optimisation, les liens indépendants pouvant être optimisés localement, les liens dépendants nécessitant une considération globale
2. Programmation dynamique hiérarchisée :
   • Algorithme 1 : exploite la structure d'arbre pour la décomposition
   • Algorithme 2 : introduit des états paramétrés pour gérer les ADL
   • Algorithme 3 : utilise la décomposition d'arbre pour le cas général
3. Exploitation de la propriété de graphe planaire externe : La nature planaire externe du sous-graphe de liens dépendants garantit une largeur d'arbre ≤ 2, fournissant une base théorique pour l'algorithme FPT
4. Stratégie de précomputation : Précomputation du coût des sous-ensembles de blocs indépendants au nœud d'oubli, évitant les recalculs

Configuration Expérimentale

Note : Cet article est un article d'algorithmes théoriques et ne contient pas de section de vérification expérimentale. L'article se concentre sur la conception d'algorithmes et l'analyse de complexité.

Preuves de Complexité

L'article prouve la difficulté du problème par réduction :

Théorème 12 (Difficulté NP-forte) : Lorsque les sommets peuvent avoir plusieurs blocs non-liés arbitrairement ordonnables, la minimisation de la longueur verticale des liens est fortement NP-difficile.

Méthode de preuve : Réduction du problème 3-Partition

• Construction : 2k-1 barres, B₀ contient n blocs non-liés (correspondant à l'instance 3-Partition)
• Propriété clé : seul l'ordre des blocs non-liés de B₀ peut être ajusté
• Équivalence : existence d'un schéma de longueur verticale zéro ⟺ existence d'une solution 3-Partition

Résultats Expérimentaux

Cet article est un travail purement théorique, sans section de résultats expérimentaux. Les résultats principaux sont :

Résumé de la Complexité des Algorithmes

Découvertes Théoriques

1. Dépendance structurelle : La complexité du problème dépend fortement de la structure graphique des liens dépendants
2. Paramétrisation par degré : Le cas général est FPT-soluble, devenant polynomial lorsque le degré de lien dépendant est borné
3. Structure de hauteur de barre :
   • Maximum local unique → liens dépendants forment un ensemble de chemins
   • Minimum local unique → liens dépendants non-adjacents forment une forêt

Travaux Connexes

1. Domaine du Dessin de Graphes

• Intégration de livres à une page : Les graphes planaires externes sont exactement ceux pouvant être dessinés sans croisement 1
• Objectifs d'optimisation traditionnels :
  • Minimisation du nombre de croisements 5,13,14
  • Minimisation de la longueur des arêtes 15,16
  • Minimisation du nombre de coudes 2,10,13,15
• Contribution de cet article : Première considération de cette nouvelle dimension d'ordre d'empilement des blocs

2. Mesures de Qualité de Visualisation

• Visualisation de lignes narratives : Considération de la distance verticale 9
• Graphes de coordonnées parallèles : Mesures d'espace écran 7
• Extension de cet article : Application de la mesure de distance verticale aux diagrammes en barres liés

3. Problèmes d'Optimisation de Graphes

• Graphes planaires externes : Minimisation de la longueur totale/maximale des arêtes, cutwidth, bandwidth solubles en temps polynomial 11
• Graphes généraux : Ces problèmes sont NP-difficiles 12
• Position de cet article : Entre polynomial et NP-difficile, analysé via complexité paramétrée

4. Diagrammes en Barres Liés

• Proposition originale : van Beusekom et al. 17 pour visualiser les incertitudes dépendantes et indépendantes
• Contribution de cet article : Première étude systématique du problème d'optimisation algorithmique

Conclusion et Discussion

Conclusions Principales

1. Complexité hiérarchisée : La complexité du problème varie de O(nm) (structure forestière) à FPT (cas général) à fortement NP-difficile (version étendue)
2. Algorithmes pratiques : Pour les structures de données courantes (comme les distributions de hauteur unimodales/univalley), il existe des algorithmes polynomiaux efficaces
3. Solubilité paramétrée : Dans le cas général, lorsque le degré des barres est borné, le problème peut être résolu efficacement

Limitations

1. Ordre de barres fixe : Les algorithmes supposent que l'ordre des barres est prédéterminé, sans considérer l'optimisation conjointe
2. Propriétés théoriques : La complexité exacte du cas général (P vs NP) reste indéterminée
3. Absence de vérification expérimentale : Pas d'implémentation réelle ni d'évaluation de performance des algorithmes
4. Exigences de structure d'instance : L'algorithme FPT peut ne pas être pratique sur des instances de haut degré

Directions Futures

L'article identifie explicitement les directions de recherche suivantes :

1. Détermination de complexité : Déterminer si le cas général avec ordre de barres fixe est NP-difficile
2. Optimisation conjointe : Optimiser simultanément l'ordre des barres et l'ordre d'empilement des blocs
3. Extensions de conception :
   • Liens asymétriques : Blocs d'extrémité de hauteurs différentes
   • Autres mesures : Minimisation du nombre de coudes, etc.
   • Graphes dirigés et multigraphes : Ordonnancement et regroupement de liens multiples
   • Hypergraphes : Liens entre trois barres ou plus
4. Applications pratiques : Évaluation de la performance des algorithmes sur des ensembles de données réelles

Évaluation Approfondie

Points Forts

1. Rigueur théorique :
   • Hiérarchie complète de complexité (du polynomial au FPT au NP-difficile)
   • Preuves mathématiques rigoureuses et analyse de complexité temporelle
   • Formalisation claire du problème
2. Conception algorithmique ingénieuse :
   • La classification indépendant/dépendant fournit une décomposition efficace du problème
   • Les trois algorithmes exploitent respectivement différentes techniques (structure forestière, décomposition d'arbre, etc.)
   • La conception de programmation dynamique est sophistiquée, exploitant pleinement la structure du problème
3. Complétude des résultats :
   • Couvre plusieurs cas particuliers et le cas général
   • Fournit des bornes supérieures (algorithmes) et inférieures (NP-difficulté)
   • L'analyse paramétrée fournit une caractérisation de complexité fine
4. Clarté de la rédaction :
   • Définitions de concepts claires (types de liens, past, etc.)
   • Illustrations d'appui à la compréhension (figures 3-8)
   • Présentation progressive des algorithmes

Insuffisances

1. Absence de vérification de praticité :
   • Aucune expérience sur données réelles
   • L'efficacité réelle de l'algorithme FPT pour Δ grand est inconnue
   • Absence de comparaison avec des algorithmes heuristiques
2. Lacune de complexité pour le cas général :
   • La question de savoir si le problème est NP-difficile avec ordre de barres fixe reste ouverte
   • La preuve de réduction dépend de l'hypothèse de blocs multiples non-liés, différente du problème original
3. Complexité algorithmique élevée :
   • L'algorithme 2 en O(n⁴m) peut ne pas être pratique pour les grandes instances
   • L'algorithme 3 avec dépendance exponentielle Δ^(3δ) explose pour degré élevé
4. Limitation de la portée du problème :
   • Considère uniquement l'objectif unique de longueur verticale
   • Ne considère pas d'autres indicateurs de qualité importants comme la minimisation des croisements
   • L'hypothèse d'ordre de barres fixe est relativement restrictive

Impact

1. Contribution théorique :
   • Étude pionnière du problème algorithmique des diagrammes en barres liés
   • Ouvre une nouvelle direction de recherche en optimisation de visualisation
   • Démontre l'application de la complexité paramétrée en visualisation
2. Valeur pratique :
   • Fournit des orientations théoriques pour les systèmes réels
   • Les algorithmes pour cas particuliers peuvent être directement appliqués
   • Fournit des références pour la conception d'algorithmes heuristiques
3. Reproductibilité :
   • Description d'algorithmes détaillée
   • Dérivations mathématiques complètes
   • Mais absence d'implémentation de code

Scénarios d'Application

1. Application directe :
   • Données avec distribution de hauteur de barre unimodale/univalley (algorithmes 1, 2)
   • Graphes avec degré de barre petit (algorithme 3)
   • Scénarios avec structure de liens dépendants simple
2. Nécessitant extension :
   • Graphes denses à grande échelle (nécessitant algorithmes heuristiques)
   • Scénarios nécessitant optimisation conjointe de l'ordre des barres
   • Optimisation multi-objectif (longueur + croisements + coudes)
3. Orientation théorique :
   • Conception de systèmes de visualisation
   • Prétraitement de données (comme tri de barres pour former une structure forestière)
   • Évaluation de références pour algorithmes d'approximation

Références Clés

1 Bernhart & Kainen (1979): The book thickness of a graph - Théorie fondamentale de l'intégration de livres à une page

6 Cygan et al. (2015): Parameterized algorithms - Manuel standard des algorithmes FPT

11 Frederickson & Hambrusch (1988): Planar linear arrangements of outerplanar graphs - Algorithmes polynomiaux pour optimisation de graphes planaires externes

17 van Beusekom et al. (2024): Visualizing set sizes with dependent and independent uncertainties - Proposition originale des diagrammes en barres liés

Évaluation globale : Ceci est un article de haute qualité en géométrie computationnelle théorique, étudiant systématiquement le problème algorithmique d'optimisation des diagrammes en barres liés. L'article est théoriquement rigoureux, la conception algorithmique est ingénieuse, et l'analyse de complexité est complète. La valeur principale réside dans l'établissement d'une base théorique solide pour cette nouvelle méthode de visualisation. Les insuffisances sont l'absence de vérification expérimentale et la caractérisation incomplète de la complexité du cas général. Si l'on peut à l'avenir combiner l'évaluation sur données réelles et la conception d'algorithmes heuristiques, cela augmentera considérablement sa valeur pratique.