Scalable Algorithms (ITI)

Thomas Bläsius

Head of the Scalable Algorithms Group

Karlsruhe Institute of Technology (KIT)
Institute of Theoretical Informatics

email thomas.blaesius@kit.edu
office room 309, Computer Science building 50.34
office hours by appointment

Research

My research is centered around the question of why algorithms often perform better in practice than the theoretical run time bounds predict. I attempt to shrink this theory-practice gap by taking properties regularly observed in real-world instances into account rather than analyzing the worst case. In this context, my research intersects with multiple other areas in the field of algorithmics, including the following:

  • graph algorithms
  • computational geometry
  • probabilistic methods (e.g., average case analysis)
  • propositional satisfiability
  • algorithm engineering
  • network science

Publications

2021

Thomas Bläsius, Tobias Friedrich, Andreas Göbel, Jordi Levy, Ralf Rothenberger
The Impact of Heterogeneity and Geometry on the Proof Complexity of Random Satisfiability.
ACM-SIAM Symposium on Discrete Algorithms (SODA) 2021
Thomas Bläsius, Tobias Friedrich, Maximilian Katzmann
Force-Directed Embedding of Scale-Free Networks in the Hyperbolic Plane.
Symposium on Experimental and Efficient Algorithms (SEA) 2021

2020

Thomas Bläsius, Tobias Friedrich, Maximilian Katzmann, Anton Krohmer
Hyperbolic Embeddings for Near-Optimal Greedy Routing.
ACM Journal of Experimental Algorithmics (JEA) 2020
Johann Birnick, Thomas Bläsius, Tobias Friedrich, Felix Naumann, Thorsten Papenbrock, Martin Schirneck
Hitting Set Enumeration with Partial Information for Unique Column Combination Discovery.
Proceedings of the VLDB Endowment 2020
Thomas Bläsius, Maximilian Böther, Philipp Fischbeck, Tobias Friedrich, Alina Gries, Falk Hüffner, Otto Kißig, Pascal Lenzner, Louise Molitor, Leon Schiller, Armin Wells, Simon Wietheger
A Strategic Routing Framework and Algorithms for Computing Alternative Paths.
Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS) 2020
Thomas Bläsius, Tobias Friedrich, Martin Schirneck
The Minimization of Random Hypergraphs.
European Symposium on Algorithms (ESA) 2020
Thomas Bläsius, Philipp Fischbeck, Tobias Friedrich, Maximilian Katzmann
Solving Vertex Cover in Polynomial Time on Hyperbolic Random Graphs.
Symposium on Theoretical Aspects of Computer Science (STACS) 2020

2019

Thomas Bläsius, Marcel Radermacher, Ignaz Rutter
How to Draw a Planarization.
Journal of Graph Algorithms and Applications 2019
Thomas Bläsius, Tobias Friedrich, Julius Lischeid, Kitty Meeks, Martin Schirneck
Efficiently Enumerating Hitting Sets of Hypergraphs Arising in Data Profiling.
Workshop on Algorithm Engineering and Experimentation (ALENEX) 2019
Thomas Bläsius, Tobias Friedrich, Maximilian Katzmann, Ulrich Meyer, Manuel Penschuck, Christopher Weyand
Efficiently Generating Geometric Inhomogeneous and Hyperbolic Random Graphs.
European Symposium on Algorithms (ESA) 2019
Thomas Bläsius, Tobias Friedrich, Andrew M. Sutton
On the Empirical Time Complexity of Scale-Free 3-SAT at the Phase Transition.
International Conference on Tools and Algorithms for Construction and Analysis of Systems (TACAS) 2019
Thomas Bläsius, Philipp Fischbeck, Tobias Friedrich, Martin Schirneck
Understanding the Effectiveness of Data Reduction in Public Transportation Networks.
Workshop on Algorithms and Models for the Web-Graph (WAW) 2019

2018

Thomas Bläsius, Annette Karrer, Ignaz Rutter
Simultaneous Embedding: Edge Orderings, Relative Positions, Cutvertices.
Algorithmica 2018
Thomas Bläsius, Tobias Friedrich, Anton Krohmer
Cliques in Hyperbolic Random Graphs.
Algorithmica 2018
Thomas Bläsius, Peter Stumpf, Torsten Ueckerdt
Local and union boxicity.
Discrete Mathematics 2018
Moritz Baum, Thomas Bläsius, Andreas Gemsa, Ignaz Rutter, Franziska Wegner
Scalable exact visualization of isocontours in road networks via minimum-link paths.
Journal of Computational Geometry (JoCG) 2018
Thomas Bläsius, Tobias Friedrich, Anton Krohmer, Sören Laue
Efficient Embedding of Scale-Free Graphs in the Hyperbolic Plane.
IEEE/ACM Transactions on Networking (TON) 2018
Thomas Bläsius, Tobias Friedrich, Maximilian Katzmann, Anton Krohmer
Hyperbolic Embeddings for Near-Optimal Greedy Routing.
Workshop on Algorithm Engineering and Experimentation (ALENEX) 2018
Thomas Bläsius, Cedric Freiberger, Tobias Friedrich, Maximilian Katzmann, Felix Montenegro-Retana, Marianne Thieffry
Efficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic Geometry.
International Colloquium on Automata, Languages and Programming (ICALP) 2018
Thomas Bläsius, Jan Eube, Thomas Feldtkeller, Tobias Friedrich, Martin S. Krejca, J. A. Gregor Lagodzinski, Ralf Rothenberger, Julius Severin, Fabian Sommer, Justin Trautmann
Memory-Restricted Routing with Tiled Map Data.
IEEE International Conference on Systems, Man and Cybernetics (SMC) 2018
Thomas Bläsius, Tobias Friedrich, Maximilian Katzmann, Anton Krohmer, Jonathan Striebel
Towards a Systematic Evaluation of Generative Network Models.
Workshop on Algorithms and Models for the Web-Graph (WAW) 2018

2017

Robert Kovacs, Anna Seufert, Ludwig Wall, Hsiang-Ting Chen, Florian Meinel, Willi Müller, Sijing You, Maximilian Brehm, Jonathan Striebel, Yannis Kommana, Alexander Popiak, Thomas Bläsius, Patrick Baudisch
TrussFab: Fabricating Sturdy Large-Scale Structures on Desktop 3D Printers.
International Conference on Human Factors in Computing Systems (CHI) 2017
Thomas Bläsius, Marcel Radermacher, Ignaz Rutter
How to Draw a Planarization.
Conference on Current Trends in Theory and Practice of Informatics (SOFSEM) 2017
Robert Kovacs, Ludwig Wall, Anna Seufert, Hsiang-Ting Chen, Willi Müller, Florian Meinel, Yannis Kommana, Thomas Bläsius, Oliver S. Schneider, Thijs Roumen, Patrick Baudisch
Demonstrating TrussFab's Editor: Designing Sturdy Large-Scale Structures.
ACM Symposium on User Interface Software and Technology (UIST) 2017

2016

Thomas Bläsius, Sebastian Lehmann, Ignaz Rutter
Orthogonal graph drawing with inflexible edges.
Computational Geometry 2016
Thomas Bläsius, Ignaz Rutter
Simultaneous PQ-Ordering with Applications to Constrained Embedding Problems.
ACM Transactions on Algorithms (TALG) 2016
Thomas Bläsius, Ignaz Rutter, Dorothea Wagner
Optimal Orthogonal Graph Drawing with Convex Bend Costs.
ACM Transactions on Algorithms (TALG) 2016
Thomas Bläsius, Ignaz Rutter
A new perspective on clustered planarity as a combinatorial embedding problem.
Theoretical Computer Science 2016
Moritz Baum, Thomas Bläsius, Andreas Gemsa, Ignaz Rutter, Franziska Wegner
Scalable Exact Visualization of Isocontours in Road Networks via Minimum-Link Paths.
European Symposium on Algorithms (ESA) 2016
Thomas Bläsius, Tobias Friedrich, Anton Krohmer
Hyperbolic Random Graphs: Separators and Treewidth.
European Symposium on Algorithms (ESA) 2016
Thomas Bläsius, Tobias Friedrich, Anton Krohmer, Sören Laue
Efficient Embedding of Scale-Free Graphs in the Hyperbolic Plane.
European Symposium on Algorithms (ESA) 2016
Thomas Bläsius, Tobias Friedrich, Martin Schirneck
The Parameterized Complexity of Dependency Detection in Relational Databases.
International Symposium on Parameterized and Exact Computation (IPEC) 2016

2015

Thomas Bläsius
New Approaches to Classic Graph-Embedding Problems - Orthogonal Drawings & Constrained Planarity.
Karlsruhe Institute of Technology 2015
Thomas Bläsius, Ignaz Rutter
Disconnectivity and relative positions in simultaneous embeddings.
Computational Geometry 2015
Thomas Bläsius, Sebastian Lehmann, Ignaz Rutter
Orthogonal Graph Drawing with Inflexible Edges.
International/Italian Conference on Algorithms and Complexity (CIAC) 2015
Md. Jawaherul Alam, Thomas Bläsius, Ignaz Rutter, Torsten Ueckerdt, Alexander Wolff
Pixel and Voxel Representations of Graphs.
International Symposium Graph Drawing and Network Visualization (GD) 2015
Thomas Bläsius
Neue Methoden für klassische Grapheinbettungsprobleme - Orthogonale Zeichnungen & bedingte Planarität.
GI Ausgezeichnete Informatikdissertationen 2015

2014

Thomas Bläsius, Marcus Krug, Ignaz Rutter, Dorothea Wagner
Orthogonal Graph Drawing with Flexibility Constraints.
Algorithmica 2014
Patrizio Angelini, Thomas Bläsius, Ignaz Rutter
Testing Mutual duality of Planar graphs.
International Journal of Computational Geometry and Applications 2014
Thomas Bläsius, Guido Brückner, Ignaz Rutter
Complexity of Higher-Degree Orthogonal Graph Embedding in the Kandinsky Model.
European Symposium on Algorithms (ESA) 2014
Thomas Bläsius, Ignaz Rutter
A New Perspective on Clustered Planarity as a Combinatorial Embedding Problem.
International Symposium Graph Drawing and Network Visualization (GD) 2014

2013

Thomas Bläsius, Annette Karrer, Ignaz Rutter
Simultaneous Embedding: Edge Orderings, Relative Positions, Cutvertices.
International Symposium Graph Drawing and Network Visualization (GD) 2013
Therese C. Biedl, Thomas Bläsius, Benjamin Niedermann, Martin Nöllenburg, Roman Prutkin, Ignaz Rutter
Using ILP/SAT to Determine Pathwidth, Visibility Representations, and other Grid-Based Graph Drawings.
International Symposium Graph Drawing and Network Visualization (GD) 2013
Thomas Bläsius, Ignaz Rutter, Dorothea Wagner
Optimal Orthogonal Graph Drawing with Convex Bend Costs.
International Colloquium on Automata, Languages and Programming (ICALP) 2013
Patrizio Angelini, Thomas Bläsius, Ignaz Rutter
Testing Mutual Duality of Planar Graphs.
International Symposium on Algorithms and Computation (ISAAC) 2013
Thomas Bläsius, Ignaz Rutter
Simultaneous PQ-Ordering with Applications to Constrained Embedding Problems.
ACM-SIAM Symposium on Discrete Algorithms (SODA) 2013
Thomas Bläsius, Stephen G. Kobourov, Ignaz Rutter
Simultaneous Embedding of Planar Graphs.
Handbook of Graph Drawing and Visualization 2013

2012

Thomas Bläsius, Ignaz Rutter
Disconnectivity and Relative Positions in Simultaneous Embeddings.
International Symposium Graph Drawing and Network Visualization (GD) 2012

2010

Thomas Bläsius, Marcus Krug, Ignaz Rutter, Dorothea Wagner
Orthogonal Graph Drawing with Flexibility Constraints.
International Symposium Graph Drawing and Network Visualization (GD) 2010