A linked bar chart is the augmentation of a traditional bar chart where each bar is partitioned into blocks and pairs of blocks are linked using orthogonal lines that pass over intermediate bars. The order of the blocks readily influences the legibility of the links. We study the algorithmic problem of minimizing the vertical length of these links, for a fixed bar order. The main challenge lies with ``dependent'' links, whose vertical link length cannot be optimized independently per bar. We show that, if the dependent links form a forest, the problem can be solved in $O(nm)$ time, for n bars and m links. If the dependent links between non-adjacent bars form a forest, the problem admits an $O(n^4m)$-time algorithm. Finally, we show that the general case is fixed-parameter tractable in the maximum number of links that are connected to one bar.
academic
Minimierung der vertikalen Länge in verknüpften Balkendiagrammen
Verknüpfte Balkendiagramme (Linked Bar Charts) sind eine erweiterte Version traditioneller Balkendiagramme, bei denen jeder Balken in mehrere Blöcke unterteilt wird, die durch orthogonale Linien verbunden sind. Diese Verbindungslinien müssen über dazwischenliegende Balken verlaufen. Die Anordnungsreihenfolge der Blöcke beeinflusst direkt die Lesbarkeit der Verbindungslinien. Dieses Papier untersucht das algorithmische Problem der Minimierung der vertikalen Länge von Verbindungslinien bei fester Balkenreihenfolge. Die Hauptherausforderung liegt in „abhängigen Verbindungen" (dependent links), deren vertikale Länge nicht unabhängig optimiert werden kann. Die Forschung zeigt: Wenn abhängige Verbindungen eine Waldstruktur bilden, kann das Problem in O(nm) Zeit gelöst werden (n Balken, m Verbindungen); wenn abhängige Verbindungen zwischen nicht benachbarten Balken einen Wald bilden, kann es in O(n⁴m) Zeit gelöst werden; im allgemeinen Fall ist das Problem unter dem Parameter der maximalen Balkengradation fixed-parameter tractable (FPT).
Traditionelle Balkendiagramme können nur Daten einer einzelnen Kategorie darstellen, aber in vielen praktischen Szenarien gehören bestimmte Zahlenwerte nicht eindeutig zu einer Kategorie, sondern sind mit mehreren Kategorien verbunden. Beispiele:
Gemeinsame Mengen: Kommunikationsvolumen zwischen Konten erscheint gleichzeitig in den Statistiken zweier Konten
Paarweise Unsicherheit: Wähler in Wahlumfragen, die zwischen zwei Parteien unschlüssig sind; Beitrag von Grenzfabriken zur Umweltverschmutzung beider Länder
Die Visualisierung kategorieübergreifender Daten ist ein wichtiges Anliegen der Datenanalyse. Verknüpfte Balkendiagramme stellen diese Beziehungen dar, indem Verbindungslinien zwischen Balken hinzugefügt werden, aber die Stapelreihenfolge der Blöcke beeinflusst direkt die vertikale Länge der Verbindungslinien und damit die Lesbarkeit und Ästhetik des Diagramms.
Standardbalkendiagramme können kategorieübergreifende Zahlenwerte nicht direkt visualisieren
Obwohl verknüpfte Balkendiagramme kürzlich vorgeschlagen wurden 17, wurde das Optimierungsproblem ihrer Blockstapelreihenfolge noch nicht untersucht
Traditionelle Graphzeichnungsprobleme (wie Single-Page Book Embedding) berücksichtigen nur die Vertexreihenfolge, nicht die neue Dimension des Blockstapelns
Dieses Papier untersucht erstmals systematisch das algorithmische Problem der Minimierung vertikaler Verbindungslängen in verknüpften Balkendiagrammen und bietet theoretische Grundlagen und effiziente Algorithmen für diese neue Visualisierungsmethode.
Problemformalisierung: Erstmalige Definition des Optimierungsproblems zur Minimierung vertikaler Verbindungslängen in verknüpften Balkendiagrammen mit Einführung eines Klassifizierungssystems für „unabhängige Verbindungen" und „abhängige Verbindungen"
Waldalgorithmus: Beweis, dass das Problem in O(nm) Zeit durch dynamische Programmierung gelöst werden kann, wenn der abhängige Verbindungsteilgraph einen Wald bildet (Theorem 3)
Nicht-benachbarter Waldalgorithmus: Beweis, dass das Problem in O(n⁴m) Zeit gelöst werden kann, wenn nicht-benachbarte abhängige Verbindungen einen Wald bilden (Theorem 6)
FPT-Algorithmus: Beweis, dass das Problem im allgemeinen Fall fixed-parameter tractable ist, mit dem Parameter der maximalen Balkengradation Δ und Zeitkomplexität O(Δ^(3δ)·δ·n) (Theorem 8)
Komplexitätsuntergrenzen: Beweis, dass das Problem stark NP-schwer ist, wenn Vertices mehrere unverknüpfte Blöcke mit beliebiger Sortierbarkeit haben (Theorem 12)
Das Papier unterteilt Verbindungen in zwei Hauptkategorien:
Unabhängige Verbindungen (IL): Vertikale Länge kann durch Platzierung eines Blocks an einem festen Ziel t unabhängig optimiert werden, mit Kosten |t - y| + |t - y'|. Drei Fälle:
Ein mittlerer Balken ist höher als die höchstmögliche Position eines Endpunkts → Ziel ist die Höhe des höchsten mittleren Balkens H
Die möglichen Positionsbereiche der beiden Endpunkte überlappen sich nicht intern → Ziel ist die niedrigste Position des höheren Bereichs
Eine Endpunktposition ist festgelegt (entsprechende Sequenz ist leer) → Ziel ist diese festgelegte Position
Abhängige Verbindungen (DL): Vertikale Länge hängt von der relativen Position zweier Blöcke ab und kann kein statisches Ziel zugewiesen bekommen. Weitere Unterteilung in:
Verbindungsklassifizierungssystem: Die Klassifizierung in unabhängige/abhängige Verbindungen ermöglicht Problemzerlegung, unabhängige Verbindungen können lokal optimiert werden, abhängige Verbindungen erfordern globale Betrachtung
Schichtweise dynamische Programmierung:
Algorithmus 1: Nutzt Waldstruktur zur Zerlegung
Algorithmus 2: Führt parametrisierte Zustände zur Behandlung von ADL ein
Algorithmus 3: Nutzt Baumzerlegung für allgemeinen Fall
Nutzung äußerer planarer Grapheigenschaften: Die äußere Planarität des abhängigen Verbindungsteilgraphs garantiert Baumbreite ≤ 2, bietet theoretische Grundlage für FPT-Algorithmus
Vorberechnungsstrategie: Vorberechnung der Kosten unabhängiger Blockuntermenge in Vergessensknoten vermeidet wiederholte Berechnung
Hinweis: Dieses Papier ist ein theoretisches Algorithmus-Papier und enthält keinen experimentellen Verifikationsteil. Das Papier konzentriert sich auf Algorithmusdesign und Komplexitätsanalyse.
Das Papier beweist die Schwierigkeit des Problems durch Reduktion:
Theorem 12 (Starke NP-Schwierigkeit): Wenn Vertices mehrere unverknüpfte Blöcke mit beliebiger Sortierbarkeit haben, ist die Minimierung vertikaler Verbindungslängen stark NP-schwer.
Beweismethode: Reduktion vom 3-Partition-Problem
Konstruktion: 2k-1 Balken, B₀ hat n unverknüpfte Blöcke (entsprechend 3-Partition-Instanz)
Schlüsseleigenschaft: Nur die Reihenfolge unverknüpfter Blöcke von B₀ ist anpassbar
Äquivalenz: Es existiert ein Schema mit Länge Null ⟺ Es existiert eine 3-Partition-Lösung
1 Bernhart & Kainen (1979): The book thickness of a graph - Grundlagentheorie des Single-Page Book Embedding
6 Cygan et al. (2015): Parameterized algorithms - Standardlehrbuch für FPT-Algorithmen
11 Frederickson & Hambrusch (1988): Planar linear arrangements of outerplanar graphs - Polynomialalgorithmen für äußere planare Graphoptimierung
17 van Beusekom et al. (2024): Visualizing set sizes with dependent and independent uncertainties - Ursprüngliche Vorschlag verknüpfter Balkendiagramme
Gesamtbewertung: Dies ist ein hochqualitatives theoretisches Papier der Computational Geometry, das das algorithmische Problem der Optimierung verknüpfter Balkendiagramme systematisch untersucht. Das Papier ist theoretisch streng, das Algorithmusdesign ist geschickt und die Komplexitätsanalyse ist vollständig. Der Hauptwert liegt in der Etablierung einer soliden theoretischen Grundlage für diese neue Visualisierungsmethode. Die Mängel sind das Fehlen experimenteller Verifikation und die unvollständige Komplexitätscharakterisierung des allgemeinen Falls. Wenn zukünftig echte Datenauswertung und Heuristik-Algorithmusdesign hinzugefügt werden können, wird der praktische Wert erheblich gesteigert.