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

8 results
2023
[8]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]
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]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, 2022, Springer.
[bibtex] [pdf] [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]On the Complexity of the Storyplan Problem
Carla Binucci, Emilio Di Giacomo, William J. Lenhart, Giuseppe Liotta, Fabrizio Montecchiani, Martin Nöllenburg, Antonios Symvonis
Graph Drawing and Network Visualization (GD'22) (Patrizio Angelini, Reinhard von Hanxleden, eds.), 2022, Springer.
[bibtex] [pdf]
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

  • New FWF ESPRIT Postdocs

    New FWF ESPRIT Postdocs

    2022-11-09
    Leroy Chew and Alexis de Colnet just joined the Algorithms and Complexity group as PIs of their own FWF ESPRIT …Read More »
  • Best student paper award at DIAGRAMS 2022

    Best student paper award at DIAGRAMS 2022

    2022-10-01
    Alexander Dobler received the Best Student Paper Award at the 13th International Conference on the Theory and Application of Diagrams …Read More »
  • Robert Ganian promoted to Associate Professor

    Robert Ganian promoted to Associate Professor

    2022-07-01
    Effective as of today, Robert Ganian is promoted to a tenured Associate Professor at the Algorithms and Complexity group. Congratulations, …Read More »
  • Best paper award at EvoCOP 2022

    Best paper award at EvoCOP 2022

    2022-05-24
    Jonas Mayerhofer, Markus Kirchweger, Marc Huber, and Günther Raidl received the best paper award for their work A Beam Search …Read More »
  • New PhD: Guangping Li

    New PhD: Guangping Li

    2022-05-13
    Guangping Li successfully defended her PhD thesis “An Algorithmic Study of Practical Map Labeling” on May 13, 2022. Congratulations, Dr. …Read More »

News archive

All news for 2015, 2016, 2017, 2018, 2019, 2020, 2021 and 2022.
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.