# Dr. Thomas Bläsius

**Chair for Algorithm Engineering**

Hasso Plattner Institute

Office: A-1.4

Tel.: +49 331 5509-412

E-Mail: Thomas.Blaesius(at)hpi.de

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

2021 [ nach oben ]

- The Impact of Heterogeneity and Geometry on the Proof Complexity of Random Satisfiability. Symposium on Discrete Algorithms (SODA) 2021

2020 [ nach oben ]

- Hyperbolic Embeddings for Near-Optimal Greedy Routing. Journal of Experimental Algorithmics (JEA) 2020
- Hitting Set Enumeration with Partial Information for Unique Column Combination Discovery. Proceedings of the VLDB Endowment 2020: 2270 - 2283
- A Strategic Routing Framework and Algorithms for Computing Alternative Paths. Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS) 2020: 10:1--10:14
- The Minimization of Random Hypergraphs. European Symposium on Algorithms (ESA) 2020: 21:1-21:15
- 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 ]

- How to Draw a Planarization. Graph Algorithms and Applications 2019: 653-682
- Efficiently Enumerating Hitting Sets of Hypergraphs Arising in Data Profiling. Algorithm Engineering and Experiments (ALENEX) 2019: 130-143
- Efficiently Generating Geometric Inhomogeneous and Hyperbolic Random Graphs. European Symposium on Algorithms (ESA) 2019: 21:2-21:14EATCS Best Paper Award
- 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
- 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 ]

- Simultaneous Embedding: Edge Orderings, Relative Positions, Cutvertices. Algorithmica 2018: 1214-1277
- Cliques in Hyperbolic Random Graphs. Algorithmica 2018: 2324-2344
- Local and Union Boxicity. Discrete Mathematics 2018: 1307 - 1315
- Scalable Exact Visualization of Isocontours in Road Networks via Minimum-Link Paths. Journal of Computational Geometry 2018: 27-73
- Efficient Embedding of Scale-Free Graphs in the Hyperbolic Plane. Transactions on Networking 2018: 920-933
- Hyperbolic Embeddings for Near-Optimal Greedy Routing. Algorithm Engineering and Experiments (ALENEX) 2018: 199-208
- Efficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic Geometry. International Colloquium on Automata, Languages, and Programming (ICALP) 2018: 20:1-20:14
- Memory-restricted Routing With Tiled Map Data. Systems, Man, and Cybernetics (SMC) 2018: 3347-3354
- Towards a Systematic Evaluation of Generative Network Models. Workshop on Algorithms and Models for the Web Graph (WAW) 2018: 99-114

2017 [ nach oben ]

- TrussFab: Fabricating Sturdy Large-Scale Structures on Desktop 3D Printers. Human Factors in Computing Systems (CHI) 2017: 2606-2616
- How to Draw a Planarization. Current Trends in Theory and Practice of Computer Science (SOFSEM) 2017: 295-308

2016 [ nach oben ]

- Orthogonal Graph Drawing with Inflexible Edges. Computational Geometry 2016: 26-40
- A new perspective on clustered planarity as a combinatorial embedding problem. Theoretical Computer Science 2016: 306-315
- Simultaneous PQ-Ordering with Applications to Constrained Embedding Problems. Transactions on Algorithms 2016: 16
- Optimal Orthogonal Graph Drawing with Convex Bend Costs. Transactions on Algorithms 2016: 33
- Scalable Exact Visualization of Isocontours in Road Networks via Minimum-Link Paths. European Symposium on Algorithms (ESA) 2016: 7:1-7:18
- Hyperbolic Random Graphs: Separators and Treewidth. European Symposium on Algorithms (ESA) 2016: 15:1-15:16
- Efficient Embedding of Scale-Free Graphs in the Hyperbolic Plane. European Symposium on Algorithms (ESA) 2016: 16:1-16:18EATCS Best Paper Award
- 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 ]

- Disconnectivity and relative positions in simultaneous embeddings. Computational Geometry 2015: 459-478
- Orthogonal Graph Drawing with Inflexible Edges. International Conference on Algorithms and Complexity (CIAC) 2015: 61-73
- Pixel and Voxel Representations of Graphs. Graph Drawing (GD) 2015: 472-486
- New Approaches to Classic Graph-Embedding Problems - Orthogonal Drawings & Constrained Planarity. Doctoral Dissertation, Karlsruhe Institute of Technology 2015

2014 [ nach oben ]

- Orthogonal Graph Drawing with Flexibility Constraints. Algorithmica 2014: 859-885
- Testing Mutual duality of Planar graphs. Computational Geometry and Applications 2014: 325-346
- Complexity of Higher-Degree Orthogonal Graph Embedding in the Kandinsky Model. European Symposium on Algorithms (ESA) 2014: 161-172
- A New Perspective on Clustered Planarity as a Combinatorial Embedding Problem. Graph Drawing (GD) 2014: 440-451

2013 [ nach oben ]

- Simultaneous Embedding of Planar Graphs. Handbook of Graph Drawing and Visualization 2013: 349-381
- Simultaneous Embedding: Edge Orderings, Relative Positions, Cutvertices. Graph Drawing (GD) 2013: 220-231
- Using ILP/SAT to Determine Pathwidth, Visibility Representations, and other Grid-Based Graph Drawings. Graph Drawing (GD) 2013: 460-471
- Optimal Orthogonal Graph Drawing with Convex Bend Costs. International Colloquium on Automata, Languages, and Programming (ICALP) 2013: 184-195
- Testing Mutual Duality of Planar Graphs. International Symposium on Algorithms and Computation (ISAAC) 2013: 350-360
- Simultaneous PQ-Ordering with Applications to Constrained Embedding Problems. Symposium on Discrete Algorithms (SODA) 2013: 1030-1043

2012 [ nach oben ]

- Disconnectivity and Relative Positions in Simultaneous Embeddings. Graph Drawing (GD) 2012: 31-42

2010 [ nach oben ]

- Orthogonal Graph Drawing with Flexibility Constraints. Graph Drawing (GD) 2010: 92-104

# 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