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).

2024 [ nach oben ]

2023 [ nach oben ]

- Bläsius, Thomas; Friedrich, Tobias; Krejca, Martin S.; Molitor, Louise
**The Impact of Geometry on Monochrome Regions in the Flip Schelling Process**Computational Geometry (CGTA) 2023: 101902 - Bläsius, Thomas; Fischbeck, Philipp; Friedrich, Tobias; Katzmann, Maximilian
**Solving Vertex Cover in Polynomial Time on Hyperbolic Random Graphs**Theory of Computing Systems 2023: 28–51 - Bläsius, Thomas; Friedrich, Tobias; Katzmann, Maximilian; Ruff, Janosch; Zeif, Ziena
**On the Giant Component of Geometric Inhomogeneous Random Graphs**European Symposium on Algorithms (ESA) 2023: 20:1–20:13 - Bläsius, Thomas; Friedrich, Tobias; Katzmann, Maximilian; Stephan, Daniel
**Strongly Hyperbolic Unit Disk Graphs**Symposium Theoretical Aspects of Computer Science (STACS) 2023: 13:1–13:17

2022 [ nach oben ]

- Bläsius, Thomas; Freiberger, Cedric; Friedrich, Tobias; Katzmann, Maximilian; Montenegro-Retana, Felix; Thieffry, Marianne
**Efficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic Geometry**ACM Transactions on Algorithms 2022: 1–32 - Bläsius, Thomas; Friedrich, Tobias; Lischeid, Julius; Meeks, Kitty; Schirneck, Martin
**Efficiently Enumerating Hitting Sets of Hypergraphs Arising in Data Profiling**Journal of Computer and System Sciences 2022: 192–213 - Bläsius, Thomas; Friedrich, Tobias; Schirneck, Martin
**The Complexity of Dependency Detection and Discovery in Relational Databases**Theoretical Computer Science 2022: 79–96 - Bläsius, Thomas; Friedrich, Tobias; Stangl, David; Weyand, Christopher
**An Efficient Branch-and-Bound Solver for Hitting Set**Algorithm Engineering and Experiments (ALENEX) 2022 - Bläsius, Thomas; Fischbeck, Philipp
**On the External Validity of Average-Case Analyses of Graph Algorithms**European Symposium on Algorithms (ESA) 2022: 21:1–21:14 - Bläsius, Thomas; Fischbeck, Philipp; Gottesbüren, Lars; Hamann, Michael; Heuer, Tobias; Spinner, Jonas; Weyand, Christopher; Wilhelm, Marcus
**A Branch-and-Bound Algorithm for Cluster Editing**Symposium on Experimental Algorithms (SEA) 2022: 13:1–13:19

2021 [ nach oben ]

- Bläsius, Thomas; Friedrich, Tobias; Katzmann, Maximilian
**Efficiently Approximating Vertex Cover on Scale-Free Networks with Underlying Hyperbolic Geometry**European Symposium on Algorithms (ESA) 2021: 20:1–20:15 - Bläsius, Thomas; Friedrich, Tobias; Weyand, Christopher
**Efficiently Computing Maximum Flows in Scale-Free Networks**European Symposium on Algorithms (ESA) 2021: 21:1–21:14 - Bläsius, Thomas; Fischbeck, Philipp; Gottesbüren, Lars; Hamann, Michael; Heuer, Tobias; Spinner, Jonas; Weyand, Christopher; Wilhelm, Marcus
**PACE Solver Description: The KaPoCE Exact Cluster Editing Algorithm**International Symposium on Parameterized and Exact Computation (IPEC) 2021: 27:1–27:3 - Bläsius, Thomas; Fischbeck, Philipp; Gottesbüren, Lars; Hamann, Michael; Heuer, Tobias; Spinner, Jonas; Weyand, Christopher; Wilhelm, Marcus
**PACE Solver Description: KaPoCE: A Heuristic Cluster Editing Algorithm**International Symposium on Parameterized and Exact Computation (IPEC) 2021: 31:1–31:4 - Bläsius, Thomas; Friedrich, Tobias; Krejca, Martin S.; Molitor, Louise
**The Impact of Geometry on Monochrome Regions in the Flip Schelling Process**International Symposium on Algorithms and Computation, (ISAAC) 2021 2021: 29:1–29:17 - Bläsius, Thomas; Friedrich, Tobias; Katzmann, Maximilian
**Force-Directed Embedding of Scale-Free Networks in the Hyperbolic Plane**Symposium on Experimental Algorithms (SEA) 2021: 22:1–22:18 - Bläsius, Thomas; Friedrich, Tobias; Göbel, Andreas; Levy, Jordi; Rothenberger, Ralf
**The Impact of Heterogeneity and Geometry on the Proof Complexity of Random Satisfiability**Symposium on Discrete Algorithms (SODA) 2021: 42–53

2020 [ nach oben ]

- Bläsius, Thomas; Friedrich, Tobias; Katzmann, Maximilian; Krohmer, Anton
**Hyperbolic Embeddings for Near-Optimal Greedy Routing**Journal of Experimental Algorithmics (JEA) 2020: 1–18 - Birnick, Johann; Bläsius, Thomas; Friedrich, Tobias; Naumann, Felix; Papenbrock, Thorsten; Schirneck, Martin
**Hitting Set Enumeration with Partial Information for Unique Column Combination Discovery**Proceedings of the VLDB Endowment 2020: 2270–2283 - 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, Simon
**A Strategic Routing Framework and Algorithms for Computing Alternative Paths**Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS) 2020: 10:1–10:14 - Bläsius, Thomas; Friedrich, Tobias; Schirneck, Martin
**The Minimization of Random Hypergraphs**European Symposium on Algorithms (ESA) 2020: 21:1–21:15 - Bläsius, Thomas; Fischbeck, Philipp; Friedrich, Tobias; Katzmann, Maximilian
**Solving Vertex Cover in Polynomial Time on Hyperbolic Random Graphs**Symposium on the Theoretical Aspects of Computer Science (STACS) 2020: 25:1–25:14

2019 [ nach oben ]

- Bläsius, Thomas; Rademacher, Marcel; Rutter, Ignaz
**How to Draw a Planarization**Graph Algorithms and Applications 2019: 653–682 - Bläsius, Thomas; Friedrich, Tobias; Lischeid, Julius; Meeks, Kitty; Schirneck, Martin
**Efficiently Enumerating Hitting Sets of Hypergraphs Arising in Data Profiling**Algorithm Engineering and Experiments (ALENEX) 2019: 130–143 - Bläsius, Thomas; Friedrich, Tobias; Katzmann, Maximilian; Meyer, Ulrich; Penschuck, Manuel; Weyand, Christopher
**Efficiently Generating Geometric Inhomogeneous and Hyperbolic Random Graphs**European Symposium on Algorithms (ESA) 2019: 21:2–21:14EATCS Best Paper Award - Bläsius, Thomas; Friedrich, Tobias; Sutton, Andrew M.
**On the Empirical Time Complexity of Scale-Free 3-SAT at the Phase Transition**Tools and Algorithms for the Construction and Analysis of Systems (TACAS) 2019: 117–134 - Bläsius, Thomas; Fischbeck, Philipp; Friedrich, Tobias; Schirneck, Martin
**Understanding the Effectiveness of Data Reduction in Public Transportation Networks**Workshop on Algorithms and Models for the Web Graph (WAW) 2019: 87–101

2018 [ nach oben ]

- Bläsius, Thomas; Karrer, Annette; Rutter, Ignaz
**Simultaneous Embedding: Edge Orderings, Relative Positions, Cutvertices**Algorithmica 2018: 1214–1277 - Bläsius, Thomas; Friedrich, Tobias; Krohmer, Anton
**Cliques in Hyperbolic Random Graphs**Algorithmica 2018: 2324–2344 - Bläsius, Thomas; Stumpf, Peter; Ueckerdt, Torsten
**Local and Union Boxicity**Discrete Mathematics 2018: 1307–1315 - Bläsius, Thomas; Friedrich, Tobias; Krohmer, Anton; Laue, Sören
**Efficient Embedding of Scale-Free Graphs in the Hyperbolic Plane**IEEE/ACM Transactions on Networking 2018: 920–933 - Baum, Moritz; Bläsius, Thomas; Gemsa, Andreas; Rutter, Ignaz; Wegner, Franziska
**Scalable Exact Visualization of Isocontours in Road Networks via Minimum-Link Paths**Journal of Computational Geometry 2018: 27–73 - Bläsius, Thomas; Friedrich, Tobias; Katzmann, Maximilian; Krohmer, Anton
**Hyperbolic Embeddings for Near-Optimal Greedy Routing**Algorithm Engineering and Experiments (ALENEX) 2018: 199–208 - Bläsius, Thomas; Freiberger, Cedric; Friedrich, Tobias; Katzmann, Maximilian; Montenegro-Retana, Felix; Thieffry, Marianne
**Efficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic Geometry**International Colloquium on Automata, Languages, and Programming (ICALP) 2018: 20:1–20:14 - Bläsius, Thomas; Eube, Jan; Feldtkeller, Thomas; Friedrich, Tobias; Krejca, Martin S.; Lagodzinski, J. A. Gregor; Rothenberger, Ralf; Severin, Julius; Sommer, Fabian; Trautmann, Justin
**Memory-restricted Routing With Tiled Map Data**Systems, Man, and Cybernetics (SMC) 2018: 3347–3354 - Bläsius, Thomas; Friedrich, Tobias; Katzmann, Maximilian; Krohmer, Anton; Striebel, Jonathan
**Towards a Systematic Evaluation of Generative Network Models**Workshop on Algorithms and Models for the Web Graph (WAW) 2018: 99–114

2017 [ nach oben ]

- 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, Patrick
**TrussFab: Fabricating Sturdy Large-Scale Structures on Desktop 3D Printers**Human Factors in Computing Systems (CHI) 2017: 2606–2616 - Bläsius, Thomas; Radermacher, Marcel; Rutter, Ignaz
**How to Draw a Planarization**Current Trends in Theory and Practice of Computer Science (SOFSEM) 2017: 295–308

2016 [ nach oben ]

- Bläsius, Thomas; Rutter, Ignaz; Wagner, Dorothea
**Optimal Orthogonal Graph Drawing with Convex Bend Costs**ACM Transactions on Algorithms 2016: 33 - Bläsius, Thomas; Lehmann, Sebastian; Rutter, Ignaz
**Orthogonal Graph Drawing with Inflexible Edges**Computational Geometry 2016: 26–40 - Bläsius, Thomas; Rutter, Ignaz
**A new perspective on clustered planarity as a combinatorial embedding problem**Theoretical Computer Science 2016: 306–315 - Bläsius, Thomas; Rutter, Ignaz
**Simultaneous PQ-Ordering with Applications to Constrained Embedding Problems**Transactions on Algorithms 2016: 16 - Baum, Moritz; Bläsius, Thomas; Gemsa, Andreas; Rutter, Ignaz; Wegner, Franziska
**Scalable Exact Visualization of Isocontours in Road Networks via Minimum-Link Paths**European Symposium on Algorithms (ESA) 2016: 7:1–7:18 - Bläsius, Thomas; Friedrich, Tobias; Krohmer, Anton
**Hyperbolic Random Graphs: Separators and Treewidth**European Symposium on Algorithms (ESA) 2016: 15:1–15:16 - Bläsius, Thomas; Friedrich, Tobias; Krohmer, Anton; Laue, Sören
**Efficient Embedding of Scale-Free Graphs in the Hyperbolic Plane**European Symposium on Algorithms (ESA) 2016: 16:1–16:18EATCS Best Paper Award - Bläsius, Thomas; Friedrich, Tobias; Schirneck, Martin
**The Parameterized Complexity of Dependency Detection in Relational Databases**International Symposium on Parameterized and Exact Computation (IPEC) 2016: 6:1–6:13

2015 [ nach oben ]

- Bläsius, Thomas; Rutter, Ignaz
**Disconnectivity and relative positions in simultaneous embeddings**Computational Geometry 2015: 459–478 - Bläsius, Thomas; Lehmann, Sebastian; Rutter, Ignaz
**Orthogonal Graph Drawing with Inflexible Edges**International Conference on Algorithms and Complexity (CIAC) 2015: 61–73 - Alam, Md. Jawaherul; Bläsius, Thomas; Rutter, Ignaz; Ueckerdt, Torsten; Wolff, Alexander
**Pixel and Voxel Representations of Graphs**Graph Drawing (GD) 2015: 472–486 - Bläsius, Thomas
**New Approaches to Classic Graph-Embedding Problems - Orthogonal Drawings & Constrained Planarity**Doctoral Dissertation, Karlsruhe Institute of Technology 2015

2014 [ nach oben ]

- Bläsius, Thomas; Krug, Marcus; Rutter, Ignaz; Wagner, Dorothea
**Orthogonal Graph Drawing with Flexibility Constraints**Algorithmica 2014: 859–885 - Angelini, Patrizio; Bläsius, Thomas; Rutter, Ignaz
**Testing Mutual duality of Planar graphs**Computational Geometry and Applications 2014: 325–346 - Bläsius, Thomas; Brückner, Guido; Rutter, Ignaz
**Complexity of Higher-Degree Orthogonal Graph Embedding in the Kandinsky Model**European Symposium on Algorithms (ESA) 2014: 161–172 - Bläsius, Thomas; Rutter, Ignaz
**A New Perspective on Clustered Planarity as a Combinatorial Embedding Problem**Graph Drawing (GD) 2014: 440–451

2013 [ nach oben ]

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

2012 [ nach oben ]

2010 [ nach oben ]

# 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

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