Thomas Bläsius | Hasso-Plattner-Institut

Prof. Dr. Thomas Bläsius

This is an archived page of a former group member.
Thomas Bläsius is now head of the Scalable Algorithms group at the Karlsruhe Insitute of Technology.

Research Interest

Most of my current and past research centers around graph algorithms. More specifically, I am interested in the following aspects.

Random scale-free networks (in particular hyperbolic random graphs and related models).
Average case analysis of algorithms based on realistic input instances (in particular hyperbolic random graphs).
Graph drawing (in particular planarity and extensions thereof, orthogonal drawings, and hypebrolic embeddings).

Publications

2024

Bläsius, Thomas; Fischbeck, PhilippOn the External Validity of Average-Case Analyses of Graph AlgorithmsACM Transactions on Algorithms 2024
[ ][ ][ URL ][ DOI ][ Download ]

2023

Bläsius, Thomas; Friedrich, Tobias; Krejca, Martin S.; Molitor, LouiseThe Impact of Geometry on Monochrome Regions in the Flip Schelling ProcessComputational Geometry (CGTA) 2023: 101902
[ ][ ][ URL ][ DOI ][ Download ]
Bläsius, Thomas; Fischbeck, Philipp; Friedrich, Tobias; Katzmann, MaximilianSolving Vertex Cover in Polynomial Time on Hyperbolic Random GraphsTheory of Computing Systems 2023: 28–51
[ ][ ][ URL ][ DOI ][ Download ]
Bläsius, Thomas; Friedrich, Tobias; Katzmann, Maximilian; Ruff, Janosch; Zeif, ZienaOn the Giant Component of Geometric Inhomogeneous Random GraphsEuropean Symposium on Algorithms (ESA) 2023: 20:1–20:13
[ ][ ][ URL ][ DOI ][ Download ]
Bläsius, Thomas; Friedrich, Tobias; Katzmann, Maximilian; Stephan, DanielStrongly Hyperbolic Unit Disk GraphsSymposium Theoretical Aspects of Computer Science (STACS) 2023: 13:1–13:17
[ ][ ][ URL ][ DOI ][ Download ]

2022

Bläsius, Thomas; Freiberger, Cedric; Friedrich, Tobias; Katzmann, Maximilian; Montenegro-Retana, Felix; Thieffry, MarianneEfficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic GeometryACM Transactions on Algorithms 2022: 1–32
[ ][ ][ URL ][ DOI ][ Download ]
Bläsius, Thomas; Friedrich, Tobias; Lischeid, Julius; Meeks, Kitty; Schirneck, MartinEfficiently Enumerating Hitting Sets of Hypergraphs Arising in Data ProfilingJournal of Computer and System Sciences 2022: 192–213
[ ][ ][ URL ][ DOI ][ Download ]
Bläsius, Thomas; Friedrich, Tobias; Schirneck, MartinThe Complexity of Dependency Detection and Discovery in Relational DatabasesTheoretical Computer Science 2022: 79–96
[ ][ ][ URL ][ DOI ][ Download ]
Bläsius, Thomas; Friedrich, Tobias; Stangl, David; Weyand, ChristopherAn Efficient Branch-and-Bound Solver for Hitting SetAlgorithm Engineering and Experiments (ALENEX) 2022
[ ][ ][ URL ][ DOI ][ Download ]
Bläsius, Thomas; Fischbeck, PhilippOn the External Validity of Average-Case Analyses of Graph AlgorithmsEuropean Symposium on Algorithms (ESA) 2022: 21:1–21:14
[ ][ ][ URL ][ DOI ][ Download ]
Bläsius, Thomas; Fischbeck, Philipp; Gottesbüren, Lars; Hamann, Michael; Heuer, Tobias; Spinner, Jonas; Weyand, Christopher; Wilhelm, MarcusA Branch-and-Bound Algorithm for Cluster EditingSymposium on Experimental Algorithms (SEA) 2022: 13:1–13:19
[ ][ ][ URL ][ DOI ][ Download ]

2021

Bläsius, Thomas; Friedrich, Tobias; Katzmann, MaximilianEfficiently Approximating Vertex Cover on Scale-Free Networks with Underlying Hyperbolic GeometryEuropean Symposium on Algorithms (ESA) 2021: 20:1–20:15
[ ][ ][ URL ][ DOI ][ Download ]
Bläsius, Thomas; Friedrich, Tobias; Weyand, ChristopherEfficiently Computing Maximum Flows in Scale-Free NetworksEuropean Symposium on Algorithms (ESA) 2021: 21:1–21:14
[ ][ ][ URL ][ DOI ][ Download ]
Bläsius, Thomas; Fischbeck, Philipp; Gottesbüren, Lars; Hamann, Michael; Heuer, Tobias; Spinner, Jonas; Weyand, Christopher; Wilhelm, MarcusPACE Solver Description: The KaPoCE Exact Cluster Editing AlgorithmInternational Symposium on Parameterized and Exact Computation (IPEC) 2021: 27:1–27:3
[ ][ ][ URL ][ DOI ][ Download ]
Bläsius, Thomas; Fischbeck, Philipp; Gottesbüren, Lars; Hamann, Michael; Heuer, Tobias; Spinner, Jonas; Weyand, Christopher; Wilhelm, MarcusPACE Solver Description: KaPoCE: A Heuristic Cluster Editing AlgorithmInternational Symposium on Parameterized and Exact Computation (IPEC) 2021: 31:1–31:4
[ ][ ][ URL ][ DOI ][ Download ]
Bläsius, Thomas; Friedrich, Tobias; Krejca, Martin S.; Molitor, LouiseThe Impact of Geometry on Monochrome Regions in the Flip Schelling ProcessInternational Symposium on Algorithms and Computation, (ISAAC) 2021 2021: 29:1–29:17
[ ][ ][ URL ][ DOI ][ Download ]
Bläsius, Thomas; Friedrich, Tobias; Katzmann, MaximilianForce-Directed Embedding of Scale-Free Networks in the Hyperbolic PlaneSymposium on Experimental Algorithms (SEA) 2021: 22:1–22:18
[ ][ ][ URL ][ DOI ][ Download ]
Bläsius, Thomas; Friedrich, Tobias; Göbel, Andreas; Levy, Jordi; Rothenberger, RalfThe Impact of Heterogeneity and Geometry on the Proof Complexity of Random SatisfiabilitySymposium on Discrete Algorithms (SODA) 2021: 42–53
[ ][ ][ URL ][ DOI ][ Download ]

2020

Bläsius, Thomas; Friedrich, Tobias; Katzmann, Maximilian; Krohmer, AntonHyperbolic Embeddings for Near-Optimal Greedy RoutingJournal of Experimental Algorithmics (JEA) 2020: 1–18
[ ][ ][ URL ][ DOI ][ Download ]
Birnick, Johann; Bläsius, Thomas; Friedrich, Tobias; Naumann, Felix; Papenbrock, Thorsten; Schirneck, MartinHitting Set Enumeration with Partial Information for Unique Column Combination DiscoveryProceedings of the VLDB Endowment 2020: 2270–2283
[ ][ ][ URL ][ DOI ][ Download ]
Bläsius, Thomas; Böther, Maximilian; Fischbeck, Philipp; Friedrich, Tobias; Gries, Alina; Hüffner, Falk; Kißig, Otto; Lenzner, Pascal; Molitor, Louise; Schiller, Leon; Wells, Armin; Wietheger, SimonA Strategic Routing Framework and Algorithms for Computing Alternative PathsAlgorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS) 2020: 10:1–10:14
[ ][ ][ URL ][ DOI ][ Download ]
Bläsius, Thomas; Friedrich, Tobias; Schirneck, MartinThe Minimization of Random HypergraphsEuropean Symposium on Algorithms (ESA) 2020: 21:1–21:15
[ ][ ][ URL ][ DOI ][ Download ]
Bläsius, Thomas; Fischbeck, Philipp; Friedrich, Tobias; Katzmann, MaximilianSolving Vertex Cover in Polynomial Time on Hyperbolic Random GraphsSymposium on the Theoretical Aspects of Computer Science (STACS) 2020: 25:1–25:14
[ ][ ][ URL ][ DOI ][ Download ]

2019

Bläsius, Thomas; Rademacher, Marcel; Rutter, IgnazHow to Draw a PlanarizationGraph Algorithms and Applications 2019: 653–682
[ ][ ][ URL ][ DOI ][ Download ]
Bläsius, Thomas; Friedrich, Tobias; Lischeid, Julius; Meeks, Kitty; Schirneck, MartinEfficiently Enumerating Hitting Sets of Hypergraphs Arising in Data ProfilingAlgorithm Engineering and Experiments (ALENEX) 2019: 130–143
[ ][ ][ URL ][ DOI ][ Download ]
Bläsius, Thomas; Friedrich, Tobias; Katzmann, Maximilian; Meyer, Ulrich; Penschuck, Manuel; Weyand, ChristopherEfficiently Generating Geometric Inhomogeneous and Hyperbolic Random GraphsEuropean Symposium on Algorithms (ESA) 2019: 21:2–21:14
EATCS Best Paper Award
[ ][ ][ URL ][ DOI ][ Download ]
Bläsius, Thomas; Friedrich, Tobias; Sutton, Andrew M.On the Empirical Time Complexity of Scale-Free 3-SAT at the Phase TransitionTools and Algorithms for the Construction and Analysis of Systems (TACAS) 2019: 117–134
[ ][ ][ URL ][ DOI ][ Download ]
Bläsius, Thomas; Fischbeck, Philipp; Friedrich, Tobias; Schirneck, MartinUnderstanding the Effectiveness of Data Reduction in Public Transportation NetworksWorkshop on Algorithms and Models for the Web Graph (WAW) 2019: 87–101
[ ][ ][ URL ][ DOI ][ Download ]

2018

Bläsius, Thomas; Karrer, Annette; Rutter, IgnazSimultaneous Embedding: Edge Orderings, Relative Positions, CutverticesAlgorithmica 2018: 1214–1277
[ ][ ][ URL ][ DOI ][ Download ]
Bläsius, Thomas; Friedrich, Tobias; Krohmer, AntonCliques in Hyperbolic Random GraphsAlgorithmica 2018: 2324–2344
[ ][ ][ DOI ][ Download ]
Bläsius, Thomas; Stumpf, Peter; Ueckerdt, TorstenLocal and Union BoxicityDiscrete Mathematics 2018: 1307–1315
[ ][ ][ URL ][ DOI ][ Download ]
Bläsius, Thomas; Friedrich, Tobias; Krohmer, Anton; Laue, SörenEfficient Embedding of Scale-Free Graphs in the Hyperbolic PlaneIEEE/ACM Transactions on Networking 2018: 920–933
[ ][ ][ URL ][ DOI ][ Download ]
Baum, Moritz; Bläsius, Thomas; Gemsa, Andreas; Rutter, Ignaz; Wegner, FranziskaScalable Exact Visualization of Isocontours in Road Networks via Minimum-Link PathsJournal of Computational Geometry 2018: 27–73
[ ][ ][ URL ][ DOI ][ Download ]
Bläsius, Thomas; Friedrich, Tobias; Katzmann, Maximilian; Krohmer, AntonHyperbolic Embeddings for Near-Optimal Greedy RoutingAlgorithm Engineering and Experiments (ALENEX) 2018: 199–208
[ ][ ][ URL ][ DOI ][ Download ]
Bläsius, Thomas; Freiberger, Cedric; Friedrich, Tobias; Katzmann, Maximilian; Montenegro-Retana, Felix; Thieffry, MarianneEfficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic GeometryInternational Colloquium on Automata, Languages, and Programming (ICALP) 2018: 20:1–20:14
[ ][ ][ URL ][ DOI ][ Download ]
Bläsius, Thomas; Eube, Jan; Feldtkeller, Thomas; Friedrich, Tobias; Krejca, Martin S.; Lagodzinski, J. A. Gregor; Rothenberger, Ralf; Severin, Julius; Sommer, Fabian; Trautmann, JustinMemory-restricted Routing With Tiled Map DataSystems, Man, and Cybernetics (SMC) 2018: 3347–3354
[ ][ ][ DOI ][ Download ]
Bläsius, Thomas; Friedrich, Tobias; Katzmann, Maximilian; Krohmer, Anton; Striebel, JonathanTowards a Systematic Evaluation of Generative Network ModelsWorkshop on Algorithms and Models for the Web Graph (WAW) 2018: 99–114
[ ][ ][ URL ][ DOI ][ Download ]

2017

Kovacs, Robert; Seufert, Anna; Wall, Ludwig; Chen, Hsiang-Ting; Meinel, Florian; Müller, Willi; You, Sijing; Brehm, Maximilian; Striebel, Jonathan; Kommana, Yannis; Popiak, Alexander; Bläsius, Thomas; Baudisch, PatrickTrussFab: Fabricating Sturdy Large-Scale Structures on Desktop 3D PrintersHuman Factors in Computing Systems (CHI) 2017: 2606–2616
[ ][ ][ URL ][ DOI ][ Download ]
Bläsius, Thomas; Radermacher, Marcel; Rutter, IgnazHow to Draw a PlanarizationCurrent Trends in Theory and Practice of Computer Science (SOFSEM) 2017: 295–308
[ ][ ][ URL ][ DOI ][ Download ]

2016

Bläsius, Thomas; Rutter, Ignaz; Wagner, DorotheaOptimal Orthogonal Graph Drawing with Convex Bend CostsACM Transactions on Algorithms 2016: 33
[ ][ ][ URL ][ DOI ][ Download ]
Bläsius, Thomas; Lehmann, Sebastian; Rutter, IgnazOrthogonal Graph Drawing with Inflexible EdgesComputational Geometry 2016: 26–40
[ ][ ][ URL ][ DOI ][ Download ]
Bläsius, Thomas; Rutter, IgnazA new perspective on clustered planarity as a combinatorial embedding problemTheoretical Computer Science 2016: 306–315
[ ][ ][ URL ][ DOI ][ Download ]
Bläsius, Thomas; Rutter, IgnazSimultaneous PQ-Ordering with Applications to Constrained Embedding ProblemsTransactions on Algorithms 2016: 16
[ ][ ][ DOI ][ Download ]
Baum, Moritz; Bläsius, Thomas; Gemsa, Andreas; Rutter, Ignaz; Wegner, FranziskaScalable Exact Visualization of Isocontours in Road Networks via Minimum-Link PathsEuropean Symposium on Algorithms (ESA) 2016: 7:1–7:18
[ ][ ][ DOI ][ Download ]
Bläsius, Thomas; Friedrich, Tobias; Krohmer, AntonHyperbolic Random Graphs: Separators and TreewidthEuropean Symposium on Algorithms (ESA) 2016: 15:1–15:16
[ ][ ][ DOI ][ Download ]
Bläsius, Thomas; Friedrich, Tobias; Krohmer, Anton; Laue, SörenEfficient Embedding of Scale-Free Graphs in the Hyperbolic PlaneEuropean Symposium on Algorithms (ESA) 2016: 16:1–16:18
EATCS Best Paper Award
[ ][ ][ URL ][ DOI ][ Download ]
Bläsius, Thomas; Friedrich, Tobias; Schirneck, MartinThe Parameterized Complexity of Dependency Detection in Relational DatabasesInternational Symposium on Parameterized and Exact Computation (IPEC) 2016: 6:1–6:13
[ ][ ][ URL ][ DOI ][ Download ]

2015

Bläsius, Thomas; Rutter, IgnazDisconnectivity and relative positions in simultaneous embeddingsComputational Geometry 2015: 459–478
[ ][ ][ DOI ][ Download ]
Bläsius, Thomas; Lehmann, Sebastian; Rutter, IgnazOrthogonal Graph Drawing with Inflexible EdgesInternational Conference on Algorithms and Complexity (CIAC) 2015: 61–73
[ ][ ][ DOI ][ Download ]
Alam, Md. Jawaherul; Bläsius, Thomas; Rutter, Ignaz; Ueckerdt, Torsten; Wolff, AlexanderPixel and Voxel Representations of GraphsGraph Drawing (GD) 2015: 472–486
[ ][ ][ DOI ][ Download ]
Bläsius, ThomasNew Approaches to Classic Graph-Embedding Problems - Orthogonal Drawings & Constrained PlanarityDoctoral Dissertation, Karlsruhe Institute of Technology 2015
[ ][ ][ URL ][ DOI ][ Download ]

2014

Bläsius, Thomas; Krug, Marcus; Rutter, Ignaz; Wagner, DorotheaOrthogonal Graph Drawing with Flexibility ConstraintsAlgorithmica 2014: 859–885
[ ][ ][ DOI ][ Download ]
Angelini, Patrizio; Bläsius, Thomas; Rutter, IgnazTesting Mutual duality of Planar graphsComputational Geometry and Applications 2014: 325–346
[ ][ ][ URL ][ DOI ][ Download ]
Bläsius, Thomas; Brückner, Guido; Rutter, IgnazComplexity of Higher-Degree Orthogonal Graph Embedding in the Kandinsky ModelEuropean Symposium on Algorithms (ESA) 2014: 161–172
[ ][ ][ DOI ][ Download ]
Bläsius, Thomas; Rutter, IgnazA New Perspective on Clustered Planarity as a Combinatorial Embedding ProblemGraph Drawing (GD) 2014: 440–451
[ ][ ][ DOI ][ Download ]

2013

Bläsius, Thomas; Kobourov, Stephen G.; Rutter, IgnazSimultaneous Embedding of Planar GraphsHandbook of Graph Drawing and Visualization 2013: 349–381
[ ][ ][ Download ]
Bläsius, Thomas; Karrer, Annette; Rutter, IgnazSimultaneous Embedding: Edge Orderings, Relative Positions, CutverticesGraph Drawing (GD) 2013: 220–231
[ ][ ][ DOI ][ Download ]
Biedl, Therese C.; Bläsius, Thomas; Niedermann, Benjamin; Nöllenburg, Martin; Prutkin, Roman; Rutter, IgnazUsing ILP/SAT to Determine Pathwidth, Visibility Representations, and other Grid-Based Graph DrawingsGraph Drawing (GD) 2013: 460–471
[ ][ ][ DOI ][ Download ]
Bläsius, Thomas; Rutter, Ignaz; Wagner, DorotheaOptimal Orthogonal Graph Drawing with Convex Bend CostsInternational Colloquium on Automata, Languages, and Programming (ICALP) 2013: 184–195
[ ][ ][ DOI ][ Download ]
Angelini, Patrizio; Bläsius, Thomas; Rutter, IgnazTesting Mutual Duality of Planar GraphsInternational Symposium on Algorithms and Computation (ISAAC) 2013: 350–360
[ ][ ][ DOI ][ Download ]
Bläsius, Thomas; Rutter, IgnazSimultaneous PQ-Ordering with Applications to Constrained Embedding ProblemsSymposium on Discrete Algorithms (SODA) 2013: 1030–1043
[ ][ ][ URL ][ DOI ][ Download ]

2012

Bläsius, Thomas; Rutter, IgnazDisconnectivity and Relative Positions in Simultaneous EmbeddingsGraph Drawing (GD) 2012: 31–42
[ ][ ][ URL ][ DOI ][ Download ]

2010

Bläsius, Thomas; Krug, Marcus; Rutter, Ignaz; Wagner, DorotheaOrthogonal Graph Drawing with Flexibility ConstraintsGraph Drawing (GD) 2010: 92–104
[ ][ URL ][ DOI ][ Download ]

Teaching

Teaching at HPI (as Postdoc)

Lectures

Graph Algorithms, Summer 2019
Computational Geometry, Winter 2018/19
Graph Algorithms, Summer 2018
Parameterized Algorithms, Winter 2017/18
Graph Algorithms, Summer 2017
Parameterized Algorithms, Winter 2016/17
Graph Algorithms, Summer 2016

Projects and Seminars

Seminar: Geometric Folding Algorithms, Summer 2019
Project Seminar: Modularity Maximization, Winter 2018/19
Seminar: Network Science, Summer 2018
Master Project: Visualizing Networks in Hyperbolic Space, Summer 2018
Master Project: Bidirectional Search in a Realistic Graph Model, Summer 2017
Project Seminar: Analysis of Complex Networks, Winter 2016/17

Teaching at KIT (as PhD student)

Algorithms in Planar Graphs, Summer 2015, teaching assistant
Seminar: The P vs. NP Conjecture, Summer 2015
Algorithmic Graph Theory, Winter 2014/15, teaching assistant
Seminar: Algorithmics, Winter 2014/15
Practical Course: Software Engineering, Summer 2014
Advanced Algorithms, Winter 2013/14, teaching assistant
Seminar: Algorithmics, Winter 2013/14
Practical Course: Software Engineering, Summer 2013
Advanced Algorithms, Winter 2012/13, teaching assistant
Practical Course: Software Engineering, Summer 2012
Seminar: The P vs. NP Conjecture, Summer 2012
Algorithms for Drawing Graphs, Winter 2011/12, teaching assistant

Projects

DFG Research Grant: The Hyperbolic Geometry of Networks, co-applicant, 2018
DFG Research Grant: Scale-Free Satisfiability, co-applicant, 2018
Feasibility Studies of Young Scientists (FYS): Heuristische Verfahren zur Visualisierung dynamischer Netzwerke, 2012