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

Markus Wallinger (Doctoral Student)
Martin Nöllenburg (Professor, Principal Investigator)

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

1 result
2021
[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

  • Martin Nöllenburg: promotion to Full Professor

    Martin Nöllenburg: promotion to Full Professor

    2020-12-17
    By December 1st, 2020, our colleague Martin Nöllenburg has been promoted to Full Professor for Graph and Geometric Algorithms.  Martin has …Read More »
  • Martin Kronegger wins the Best Teaching Award 2020

    Martin Kronegger wins the Best Teaching Award 2020

    2020-10-23
    Congratulations to Martin Kronegger who received a Best Teaching Award 2020 from TU Wien. The Algorithms and Complexity group is …Read More »
  • Welcome to our Feodor Lynen Fellow Dr. Manuel Sorge

    Welcome to our Feodor Lynen Fellow Dr. Manuel Sorge

    2020-10-12
    On October 1, 2020, Dr. Manuel Sorge has joined the Algorithms and Complexity group with a prestigious Feodor Lynen postdoc …Read More »
  • TU Wien students excel at the 2020 Graph Drawing Contest

    TU Wien students excel at the 2020 Graph Drawing Contest

    2020-10-01
    The 27th annual Graph Drawing Contest, held (virtually) in conjunction with the 28th International Symposium on Graph Drawing and Network …Read More »
  • Best Paper Award at CP’2020

    Best Paper Award at CP’2020

    2020-09-11
    Tomáš Peitl and Stefan Szeider won the Best Paper Award at the main track of CP'2020, the 26th International Conference on Principles …Read More »

News archive

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