Algorithms and Complexity Group
  • People
  • Research
  • Courses
  • Talks
  • Jobs
  • Contact

Engineering Linear Ordering Algorithms for Optimizing Data Visualizations (Research Project)

Funding Organisation: Vienna Science and Technology Fund, WWTF
Project Number: ICT19-035
Duration: 07/2020 - 06/2024

Project Team

Alexander Dobler (Doctoral Student)
Markus Wallinger (Doctoral Student)
Jules Wulms (Postdoc, 2021-2022)
Martin Nöllenburg (Professor, Principal Investigator)

Project team members together with the director of WWTF

Alexander Dobler, Michael Stampfer, Martin Nöllenburg at the 20th anniversary of WWTF

Topic

Optimizing linear orderings of objects is a fundamental problem for many types of data visualizations ranging from graph layouts over geospatial data to abstract sets and sequences or time-series data. Yet a systematic investigation of algorithms for solving novel constrained and application-specific ordering problems that go beyond well-studied and NP-hard classic ordering problems is missing. Practical work in visualization often resorts to heuristics without rigorous performance and quality guarantees for solving these algorithmic problems. In this project we will take an algorithmic perspective on several different ordering problems in data visualization. In the algorithm engineering sense we want to cross the gap between fundamental theory and practical applications and aim to bring the benefit of rigorous formal methods into practically relevant implementations and at the same time define new algorithmic challenges inspired by recent visualization problems. On the one hand, we will investigate the complexity of new problem settings with special input configurations, structural constraints on feasible orderings, and dependencies between multiple objects and orderings. On the other hand, we will design and implement new and sufficiently scalable algorithms with formally proven performance guarantees to compute optimal and approximate solutions. We thoroughly evaluate the improvements over existing state-of-the-art heuristics in computational experiments and user studies.

Publications

31 results
2025
[31]Constrained Boundary Labeling
Thomas Depian, Martin Nöllenburg, Soeren Terziadis, Markus Wallinger
Comput. Geom. Theory Appl., volume 129, pages 102191, 2025.
[bibtex] [doi]
[30]On Minimizing Wiggle in Stacked Area Charts
Alexander Dobler, Martin Nöllenburg
Algorithms and Data Structures (WADS'25) (Pat Morin, Eunjin Oh, eds.), 2025, Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
Note: To appear.
[bibtex]
[29]Representing Hypergraphs by Point-Line Incidences
Alexander Dobler, Stephen G. Kobourov, Debajyoti Mondal, Martin Nöllenburg
Theory and Practice of Computer Science (SOFSEM'25) (Rastislav Královic, Vera Kurková, eds.), volume 15538 of LNCS, pages 241–254, 2025, Springer.
[bibtex] [doi]
2024
[28]Computing Hive Plots: A Combinatorial Framework
Martin Nöllenburg, Markus Wallinger
J. Graph Algorithms Appl., volume 28, number 2, pages 101–129, 2024.
[bibtex] [doi]
[27]Computing Data-driven Multilinear Metro Maps
Martin Nöllenburg, Soeren Terziadis
The Cartographic Journal, pages 1–16, 2024.
[bibtex] [doi]
[26]Improving Temporal Treemaps by Minimizing Crossings
Alexander Dobler, Martin Nöllenburg
Comput. Graph. Forum, volume 43, number 3, pages e15087, 2024.
[bibtex] [doi]
[25]On the Complexity of the Storyplan Problem
Carla Binucci, Emilio Di Giacomo, William J. Lenhart, Giuseppe Liotta, Fabrizio Montecchiani, Martin Nöllenburg, Antonios Symvonis
J. Computer and Systems Sciences, volume 139, pages 103466, 2024.
[bibtex] [doi]
[24]Hoop Diagrams: A Set Visualization Method
Peter Rodgers, Peter Chapman, Andrew Blake, Martin Nöllenburg, Markus Wallinger, Alexander Dobler
Diagrammatic Representation and Inference (DIAGRAMS'24), volume 14981 of LNCS, pages 377-392, 2024, Springer.
[bibtex] [doi]
[23]GdMetriX - A NetworkX Extension For Graph Drawing Metrics
Martin Nöllenburg, Sebastian Röder, Markus Wallinger
Graph Drawing and Network Visualization (GD'24) (Stefan Felsner, Karsten Klein, eds.), volume 320 of LIPIcs, pages 45:1–45:3, 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
Note: Poster abstract
[bibtex] [doi]
[22]Constrained Boundary Labeling
Thomas Depian, Martin Nöllenburg, Soeren Terziadis, Markus Wallinger
Algorithms and Computation (ISAAC'24) (Julian Mestre, Anthony Wirth, eds.), volume 322 of LIPIcs, pages 26:1–26:16, 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
[bibtex] [pdf] [doi]
[21]Revisiting ILP Models for Exact Crossing Minimization in Storyline Drawings
Alexander Dobler, Michael Jünger, Paul J. Jünger, Julian Meffert, Petra Mutzel, Martin Nöllenburg
Graph Drawing and Network Visualization (GD'24) (Stefan Felsner, Karsten Klein, eds.), volume 320 of LIPIcs, pages 31:1–31:19, 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
[bibtex] [pdf] [doi]
[20]Minimizing Corners in Colored Rectilinear Grids
Thomas Depian, Alexander Dobler, Christoph Kern, Jules Wulms
Algorithms and Computation (WALCOM'24) (Ryuhei Uehara, Katsuhisa Yamanaka, Hsu-Chun Yen, eds.), volume 14549 of LNCS, pages 134–148, 2024, Springer.
[bibtex] [doi]
[19]Boundary Labeling in a Circular Orbit
Annika Bonerath, Martin Nöllenburg, Soeren Terziadis, Markus Wallinger, Jules Wulms
Graph Drawing and Network Visualization (GD'24) (Stefan Felsner, Karsten Klein, eds.), volume 320 of LIPIcs, pages 22:1–22:17, 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
[bibtex] [pdf] [doi]
[18]Bundling-Aware Graph Drawing
Daniel Archambault, Giuseppe Liotta, Martin Nöllenburg, Tommaso Piselli, Alessandra Tappini, Markus Wallinger
Graph Drawing and Network Visualization (GD'24) (Stefan Felsner, Karsten Klein, eds.), volume 320 of LIPIcs, pages 15:1–15:19, 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
[bibtex] [doi]
2023
[17]LinSets.zip: Compressing Linear Set Diagrams
Markus Wallinger, Alexander Dobler, Martin Nöllenburg
IEEE Trans. Visualization and Computer Graphics, volume 29, number 6, pages 2875–2887, 2023.
[bibtex] [doi]
[16]Faster Edge-Path Bundling Through Graph Spanners
Markus Wallinger, Daniel Archambault, David Auber, Martin Nöllenburg, Jaakko Peltonen
Computer Graphics Forum, volume 42, number 6, pages e14789, 2023.
[bibtex] [doi]
[15]MosaicSets: Embedding Set Systems into Grid Graphs
Peter Rottmann, Markus Wallinger, Annika Bonerath, Sven Gedicke, Martin Nöllenburg, Jan-Henrik Haunert
IEEE Trans. Visualization and Computer Graphics, 2023.
[bibtex] [pdf]
[14]Splitting Vertices in 2-Layer Graph Drawings
Reyan Ahmed, Patrizio Angelini, Michael A. Bekos, Giuseppe Di Battista, Michael Kaufmann, Philipp Kindermann, Stephen Kobourov, Martin Nöllenburg, Antonios Symvonis, Anaïs Villedieu, Markus Wallinger
IEEE Computer Graphics and Applications, volume 43, number 3, pages 24–35, 2023.
[bibtex] [doi]
[13]Computing Hive Plots: A Combinatorial Framework
Martin Nöllenburg, Markus Wallinger
Graph Drawing and Network Visualization (GD'23) (Michael Bekos, Markus Chimani, eds.), volume 14466 of LNCS, pages 153–169, 2023, Springer.
[bibtex] [pdf] [doi]
[12]Planarizing Graphs and their Drawings by Vertex Splitting
Martin Nöllenburg, Manuel Sorge, Soeren Terziadis, Anaïs Villedieu, Hsiang-Yun Wu, Jules Wulms
Graph Drawing and Network Visualization (GD'22) (Patrizio Angelini, Reinhard von Hanxleden, eds.), volume 13764 of LNCS, pages 232–246, 2023, Springer.
[bibtex] [pdf] [doi]
[11]On Families of Planar DAGs with Constant Stack Number
Martin Nöllenburg, Sergey Pupyrev
Graph Drawing and Network Visualization (GD'23) (Michael Bekos, Markus Chimani, eds.), volume 14465 of LNCS, pages 135–151, 2023, Springer.
[bibtex] [pdf] [doi]
[10]The Influence of Dimensions on the Complexity of Computing Decision Trees
Stephen G. Kobourov, Maarten Löffler, Fabrizio Montecchiani, Marcin Pilipczuk, Ignaz Rutter, Raimund Seidel, Manuel Sorge, Jules Wulms
Conference on Artificial Intelligence (AAAI'23) (Brian Williams, Yiling Chen, Jennifer Neville, eds.), pages 8343–8350, 2023, AAAI Press.
[bibtex] [doi]
[9]Crossing Minimization in Time Interval Storylines
Alexander Dobler, Martin Nöllenburg, Daniel Stojanovic, Anaïs Villedieu, Jules Wulms
European Workshop on Computational Geometry (EuroCG'23) (Clemens Huemer, Carlos Seara, eds.), pages 36:1–36:7, 2023.
[bibtex] [pdf]
[8]Block Crossings in One-Sided Tanglegrams
Alexander Dobler, Martin Nöllenburg
Algorithms and Data Structures (WADS'23) (Pat Morin, Subhash Suri, eds.), volume 14079 of LNCS, pages 386–400, 2023, Springer.
[bibtex] [pdf] [doi]
2022
[7]Edge-Path Bundling: A Less Ambiguous Edge Bundling Approach
Markus Wallinger, Daniel Archambault, David Auber, Martin Nöllenburg, Jaakko Peltonen
IEEE Trans. Visualization and Computer Graphics, volume 28, number 1, pages 313–323, 2022.
[bibtex] [doi]
[6]Turbocharging Heuristics for Weak Coloring Numbers
Alexander Dobler, Manuel Sorge, Anaïs Villedieu
European Symposium on Algorithms (ESA 2022) (Shiri Chechik, Gonzalo Navarro, Eva Rotenberg, Grzegorz Herman, eds.), volume 244 of LIPIcs, pages 44:1–44:18, 2022, Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
[bibtex] [doi]
[5]On Computing Optimal Linear Diagrams
Alexander Dobler, Martin Nöllenburg
Diagrammatic Representation and Inference (DIAGRAMS'22) (Valeria Giardino, Sven Linker, Richard Burns, Francesco Bellucci, Jean-Michel Boucheix, Petrucio Viana, eds.), volume 13462 of LNAI, pages 20–36, 2022, Springer.
[bibtex] [pdf] [doi]
[4]Multidimensional Manhattan Preferences
Jiehua Chen, Martin Nöllenburg, Sofia Simola, Anaïs Villedieu, Markus Wallinger
Theoretical Informatics (LATIN'22) (Armando Castañeda, Francisco Rodríguez-Henríquez, eds.), volume 13568 of LNCS, pages 273–289, 2022, Springer.
[bibtex] [doi]
[3]Compacting Squares: Input-Sensitive In-Place Reconfiguration of Sliding Squares
Hugo A. Akitaya, Erik D. Demaine, Matias Korman, Irina Kostitsyna, Irene Parada, Willem Sonke, Bettina Speckmann, Ryuhei Uehara, Jules Wulms
Scandinavian Symposium and Workshops on Algorithm Theory (SWAT'22) (Artur Czumaj, Qin Xin, eds.), volume 227 of LIPIcs, pages 4:1–4:19, 2022, Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
[bibtex] [doi]
2021
[2]On the Readability of Abstract Set Visualizations
Markus Wallinger, Ben Jacobsen, Stephen Kobourov, Martin Nöllenburg
IEEE Trans. Visualization and Computer Graphics, volume 27, number 6, pages 2821–2832, 2021.
[bibtex] [doi]
[1]MetroSets: Visualizing Sets as Metro Maps
Ben Jacobsen, Markus Wallinger, Stephen Kobourov, Martin Nöllenburg
IEEE Trans. Visualization and Computer Graphics, volume 27, number 2, pages 1257–1267, 2021.
[bibtex] [pdf] [doi]

News

  • Best Paper Award at SOFSEM 2025

    Best Paper Award at SOFSEM 2025

    2025-01-23
    Thomas Depian, Simon D. Fink, Alexander Firbas, Robert Ganian, and Martin Nöllenburg received the Best Paper Award for their paper …Read More »
  • Markus Wallinger receives Award of Excellence for his PhD Thesis

    Markus Wallinger receives Award of Excellence for his PhD Thesis

    2024-12-05
    Our former group member Markus Wallinger won the Award of Excellence by the Federal Ministry for Education, Science and Research. …Read More »
  • Thomas Depian receives State Prize for his Master’s Thesis

    Thomas Depian receives State Prize for his Master’s Thesis

    2024-11-21
    Our group member Thomas Depian won the Appreciation Award given by the Federal Ministry for Education, Science and Research. This …Read More »
  • Best Paper Award at GECCO 2024 for M. Bresich, G. Raidl, and S. Limmer

    Best Paper Award at GECCO 2024 for M. Bresich, G. Raidl, and S. Limmer

    2024-07-24
    Maria Bresich, Günther Raidl, and Steffen Limmer received the best paper award at the 2024 Genetic and Evolutionary Computation Conference …Read More »
  • Welcome to our Feodor Lynen Fellow Dr. Frank Sommer

    Welcome to our Feodor Lynen Fellow Dr. Frank Sommer

    2024-06-14
    On June 1, 2024, Dr. Frank Sommer has joined the Algorithms and Complexity group with a prestigious Feodor Lynen postdoc …Read More »

News archive

All news for 2015, 2016, 2017, 2018, 2019, 2020, 2021, 2022, 2023 and 2024.
TU Wien Informatics
Offenlegung (§25 MedienG) Inhaber der Website ist das Institut für Logic and Computation an der Technischen Universität Wien, 1040 Wien. Die TU Wien distanziert sich von den Inhalten aller extern gelinkten Seiten und übernimmt diesbezüglich keine Haftung. – Disclaimer – Datenschutzerklärung
Log in requires cookies.