Minimizing Vertical Length in Linked Bar Charts
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866917096485552128 |
|---|---|
| author | Broek, Steven van den van Kreveld, Marc Meulemans, Wouter Simons, Arjen |
| author_facet | Broek, Steven van den van Kreveld, Marc Meulemans, Wouter Simons, Arjen |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_16812 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Minimizing Vertical Length in Linked Bar Charts Broek, Steven van den van Kreveld, Marc Meulemans, Wouter Simons, Arjen Computational Geometry 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. |
| title | Minimizing Vertical Length in Linked Bar Charts |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2511.16812 |