Wolff, Alexander - Chair of Computer Science I

Lehrstuhl für Informatik I
Universität Würzburg
Am Hubland
D-97074 Würzburg

Building M4, Room 01.001
Office hours: Wed, 2:00–3:00 pm
Tel.: +49 (0) 931-31-85055
Fax: +49 (0) 931-31-825200

firstname.lastname "at" uni-wuerzburg.de
orcid.org/0000-0001-5872-718X

Current Teaching

lecture Algorithmic Graph Theory (B.Sc. Inf, LA Inf.)
lecture Visualization of Graphs (M.Sc. Inf)
seminar Algorithms (M.Sc./B.Sc. Inf)

» more

Research

Graph Drawing
Computational Geometry
Algorithms for Geographic Information Systems (GIS)
Graph Algorithms

Work in Committees

since 2024 managing editor of the diamond open-access journal JoCG; 2017–2024 section editor
2017– member of the editorial board of the diamond open-access journal JGAA
program co-chair of the conferences SOFSEM 2026 (with Jakub Kozik) and GD 2013 (with Stephen Wismath) and of the workshop EuroCG 2020 (with Steve Chaplick and Philipp Kindermann)
program committees of the conferences WG (2026), ESA (2013), WAOA (2018), ISAAC (2022, 2014, 2011, 2006), GD (2020, 2017, 2015, 2013, 2012, 2006), PacificVis (2013, 2012, 2011), CIAC (2025), SoCG Video/MM track (2012), AGILE (2010, 2009), Gene&MR (2011, 2010), CALDAM (2018), EuroCG (2026, 2020, 2019), ICCG (2020), SchematicMapping (2019)
organizing committee chair of GD 2014 and EuroCG 2020 (with Steve Chaplick and Philipp Kindermann)
2011–15 steering committee of the European Symposia on Algorithms (ESA)
2012–17 and 2021–24 steering committee of the International Symposia on Graph Drawing and Network Visualization (GD)
2024–2027 steering committee of the International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM)
2011–17 and 2021–23 faculty council of the Faculty of Mathematics and Computer Science of the University of Würzburg

Short CV

2021–2023:
managing director of the Institute of Computer Science, University of Würzburg
2015–2017:
dean of the Faculty of Mathematics and Computer Science, University of Würzburg
2013–2015:
vice dean of the Faculty of Mathematics and Computer Science, University of Würzburg
2011–2013:
managing director of the Institute of Computer Science, University of Würzburg
since 2009:
chair of Algorithms, Complexity, and Knowledge Based Systems at the Institute of Computer Science, University of Würzburg

» more

Key Publications

Recognizing 2-Layer and Outer k-Planar Graphs. Yasuaki Kobayashi, Yuto Okada and Alexander Wolff. In Proc. 41st Annu. Sympos. Comput. Geom. (SoCG), Vol. 332 of LIPIcs, O. Aichholzer, H. Wang (eds.), pp. 65:1–65:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025.
- [ BibTeX ]
- [ DOI ]
- [ arxiv ]
@inproceedings{kow-r2lok-SoCG25, author = {Kobayashi, Yasuaki and Okada, Yuto and Wolff, Alexander}, booktitle = {Proc. 41st Annu. Sympos. Comput. Geom. (SoCG)}, editor = {Aichholzer, Oswin and Wang, Haitao}, keywords = {2-layer_$k$-planar_graphs}, pages = {65:1–65:16}, publisher = {Schloss Dagstuhl – Leibniz-Zentrum für Informatik}, series = {LIPIcs}, title = {Recognizing 2-Layer and Outer k-Planar Graphs}, volume = 332, year = 2025 }
Constrained and Ordered Level Planarity Parameterized by the Number of Levels. Vacláv Blažej, Boris Klemz, Felix Klesen, Marie Diana Sieper, Alexander Wolff and Johannes Zink. Journal of Computational Geometry, 16(2), pp. 26–90. 2025.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
- [ slides ]
The problem \textsc{Level Planarity asks for a crossing-free drawing of a graph in the plane such that vertices are placed at prescribed y-coordinates (called \emph{levels}) and such that every edge is realized as a y-monotone curve. In the variant \textsc{Constrained Level Planarity (CLP), each level $$y$$ is equipped with a partial order $$\prec_y$$ on its vertices and in the desired drawing the left-to-right order of vertices on level~$$y$$ has to be a linear extension of~$$\prec_y$$. \textsc{Ordered Level PLanarity (OLP) corresponds to the special case of CLP where the given partial orders $$\prec_y$$ are total orders. Previous results by Brückner and Rutter [SODA 2017] and Klemz and Rote [ACM Trans. Alg. 2019] state that both CLP and OLP are NP-hard even in severely restricted cases. In particular, they remain NP-hard even when restricted to instances whose \emph{width (the maximum number of vertices that may share a common level) is at most two. In this paper, we focus on the other dimension: we study the parameterized complexity of CLP and OLP with respect to the \emph{height (the number of levels). par We show that OLP parameterized by the height is complete with respect to the complexity class XNLP, which was first studied by Elberfeld, Stockhusen, and Tantau [Algorithmica 2015] (under a different name) and recently made more prominent by Bodlaender, Groenland, Nederlof, and Swennenhuis [FOCS 2021]. It contains all parameterized problems that can be solved nondeterministically in time $$f(k)cdot n^mathcal O(1)}$$ and space $$f(k)\cdot \log n$$ (where~$$f$$ is a computable function, $$n$$ is the input size, and $$k$$ is the parameter). If a problem is XNLP-complete, it lies in XP, but is W[$$t$$]-hard for every $$t$$. par In contrast to the fact that OLP parameterized by the height lies in XP, it turns out that CLP is NP-hard even when restricted to instances of height 4. We complement this result by showing that CLP can be solved in polynomial time for instances of height at most~3.

@article{bkkswz-colpp-JoCG25, abstract = {The problem \textsc{Level Planarity} asks for a crossing-free drawing of a graph in the plane such that vertices are placed at prescribed y-coordinates (called \emph{levels}) and such that every edge is realized as a y-monotone curve. In the variant \textsc{Constrained Level Planarity} (CLP), each level $y$ is equipped with a partial order $\prec_y$ on its vertices and in the desired drawing the left-to-right order of vertices on level $y$ has to be a linear extension of $\prec_y$. \textsc{Ordered Level PLanarity} (OLP) corresponds to the special case of CLP where the given partial orders $\prec_y$ are total orders. Previous results by Br\"uckner and Rutter [SODA 2017] and Klemz and Rote [ACM Trans.\ Alg.\ 2019] state that both CLP and OLP are NP-hard even in severely restricted cases. In particular, they remain NP-hard even when restricted to instances whose \emph{width} (the maximum number of vertices that may share a common level) is at most two. In this paper, we focus on the other dimension: we study the parameterized complexity of CLP and OLP with respect to the \emph{height} (the number of levels). \par We show that OLP parameterized by the height is complete with respect to the complexity class XNLP, which was first studied by Elberfeld, Stockhusen, and Tantau [Algorithmica 2015] (under a different name) and recently made more prominent by Bodlaender, Groenland, Nederlof, and Swennenhuis [FOCS 2021]. It contains all parameterized problems that can be solved nondeterministically in time $f(k)\cdot n^{\mathcal O(1)}$ and space $f(k)\cdot \log n$ (where $f$ is a computable function, $n$ is the input size, and $k$ is the parameter). If a problem is XNLP-complete, it lies in XP, but is W[$t$]-hard for every $t$. \par In contrast to the fact that OLP parameterized by the height lies in XP, it turns out that CLP is NP-hard even when restricted to instances of height 4. We complement this result by showing that CLP can be solved in polynomial time for instances of height at most 3.}, author = {Blažej, Vacláv and Klemz, Boris and Klesen, Felix and Sieper, Marie Diana and Wolff, Alexander and Zink, Johannes}, journal = {Journal of Computational Geometry}, keywords = {level_planarity}, note = {Special issue on SoCG 2024.}, number = 2, pages = {26–90}, title = {Constrained and Ordered Level Planarity Parameterized by the Number of Levels}, volume = 16, year = 2025 }
Adjacency Graphs of Polyhedral Surfaces. Elena Arseneva, Linda Kleist, Boris Klemz, Maarten Löffler, André Schulz, Birgit Vogtenhuber and Alexander Wolff. Discrete & Computational Geometry, 71, pp. 1429–1455. 2024.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
- [ slides ]
- [ arxiv ]
- [ video ]
We study whether a given graph can be realized as an adjacency graph of the polygonal cells of a polyhedral surface in~$$\mathbb{R}^3$$. We show that every graph is realizable as a polyhedral surface with arbitrary polygonal cells, and that this is not true if we require the cells to be convex. In particular, if the given graph contains $$K_5$$, $$K_{5,81}$$, or any nonplanar $$3$$-tree as a subgraph, no such realization exists. On the other hand, all planar graphs, $$K_{4,4}$$, and $$K_{3,5}$$ can be realized with convex cells. The same holds for any subdivision of any graph where each edge is subdivided at least once, and, by a result from McMullen et al.~(1983), for any hypercube. par Our results have implications on the maximum density of graphs describing polyhedral surfaces with convex cells: The realizability of hypercubes shows that the maximum number of edges over all realizable $$n$$-vertex graphs is in $$\Omega(n \log n)$$. From the non-realizability of $$K_{5,81}$$, we obtain that any realizable $$n$$-vertex graph has $$\bigO(n^{9/5})$$ edges. As such, these graphs can be considerably denser than planar graphs, but not arbitrarily dense.

@article{akklsvw-dgps-DCG24, abstract = {We study whether a given graph can be realized as an adjacency graph of the polygonal cells of a polyhedral surface in $\mathbb{R}^3$. We show that every graph is realizable as a polyhedral surface with arbitrary polygonal cells, and that this is not true if we require the cells to be convex. In particular, if the given graph contains $K_5$, $K_{5,81}$, or any nonplanar $3$-tree as a subgraph, no such realization exists. On the other hand, all planar graphs, $K_{4,4}$, and $K_{3,5}$ can be realized with convex cells. The same holds for any subdivision of any graph where each edge is subdivided at least once, and, by a result from McMullen et al. (1983), for any hypercube. \par Our results have implications on the maximum density of graphs describing polyhedral surfaces with convex cells: The realizability of hypercubes shows that the maximum number of edges over all realizable $n$-vertex graphs is in $\Omega(n \log n)$. From the non-realizability of $K_{5,81}$, we obtain that any realizable $n$-vertex graph has $\bigO(n^{9/5})$ edges. As such, these graphs can be considerably denser than planar graphs, but not arbitrarily dense.}, author = {Arseneva, Elena and Kleist, Linda and Klemz, Boris and Löffler, Maarten and Schulz, André and Vogtenhuber, Birgit and Wolff, Alexander}, journal = {Discrete \& Computational Geometry}, keywords = {realizability}, pages = {1429–1455}, title = {Adjacency Graphs of Polyhedral Surfaces}, volume = 71, year = 2024 }
Bounding and Computing Obstacle Numbers of Graphs. Martin Balko, Steven Chaplick, Robert Ganian, Siddharth Gupta, Michael Hoffmann, Pavel Valtr and Alexander Wolff. SIAM Journal of Discrete Mathematics, 38(2), pp. 1537–1565. 2024.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
- [ slides ]
- [ arxiv ]
An obstacle representation of a graph G consists of a set of pairwise disjoint simply-connected closed regions and a one-to-one mapping of the vertices of G to points such that two vertices are adjacent in G if and only if the line segment connecting the two corresponding points does not intersect any obstacle. The obstacle number of a graph is the smallest number of obstacles in an obstacle representation of the graph in the plane such that all obstacles are simple polygons. par It is known that the obstacle number of each n-vertex graph is O(n log n) [Balko, Cibulka, and Valtr, 2018] and that there are n-vertex graphs whose obstacle number is Ω(n/(log log n)^2) [Dujmović and Morin, 2015]. We improve this lower bound to Ω(n/log log n) for simple polygons and to Ω(n) for convex polygons. To obtain these stronger bounds, we improve known estimates on the number of n-vertex graphs with bounded obstacle number, solving a conjecture by Dujmović and Morin. We also show that if the drawing of some n-vertex graph is given as part of the input, then for some drawings Ω(n2) obstacles are required to turn them into an obstacle representation of the graph. Our bounds are asymptotically tight in several instances. par We complement these combinatorial bounds by two complexity results. First, we show that computing the obstacle number of a graph G is fixed-parameter tractable in the vertex cover number of G. Second, we show that, given a graph G and a simple polygon P, it is NP-hard to decide whether G admits an obstacle representation using P as the only obstacle.

@article{bcghvw-bcong-SIDMA24, abstract = {An obstacle representation of a graph G consists of a set of pairwise disjoint simply-connected closed regions and a one-to-one mapping of the vertices of G to points such that two vertices are adjacent in G if and only if the line segment connecting the two corresponding points does not intersect any obstacle. The obstacle number of a graph is the smallest number of obstacles in an obstacle representation of the graph in the plane such that all obstacles are simple polygons. \par It is known that the obstacle number of each n-vertex graph is O(n log n) [Balko, Cibulka, and Valtr, 2018] and that there are n-vertex graphs whose obstacle number is Ω(n/(log log n)^2) [Dujmović and Morin, 2015]. We improve this lower bound to Ω(n/log log n) for simple polygons and to Ω(n) for convex polygons. To obtain these stronger bounds, we improve known estimates on the number of n-vertex graphs with bounded obstacle number, solving a conjecture by Dujmović and Morin. We also show that if the drawing of some n-vertex graph is given as part of the input, then for some drawings Ω(n2) obstacles are required to turn them into an obstacle representation of the graph. Our bounds are asymptotically tight in several instances. \par We complement these combinatorial bounds by two complexity results. First, we show that computing the obstacle number of a graph G is fixed-parameter tractable in the vertex cover number of G. Second, we show that, given a graph G and a simple polygon P, it is NP-hard to decide whether G admits an obstacle representation using P as the only obstacle.}, author = {Balko, Martin and Chaplick, Steven and Ganian, Robert and Gupta, Siddharth and Hoffmann, Michael and Valtr, Pavel and Wolff, Alexander}, journal = {SIAM Journal of Discrete Mathematics}, keywords = {convex_obstacle_number}, number = 2, pages = {1537–1565}, title = {Bounding and Computing Obstacle Numbers of Graphs}, volume = 38, year = 2024 }
Drawing Graphs on Few Lines and Few Planes. Steven Chaplick, Krzysztof Fleszar, Fabian Lipp, Alexander Ravsky, Oleg Verbitsky and Alexander Wolff. Journal of Computational Geometry, 11(1), pp. 433–475. 2020.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
- [ slides ]
We investigate the problem of drawing graphs in 2D and 3D such that their edges (or only their vertices) can be covered by few lines or planes. We insist on straight-line edges and crossing-free drawings. This problem has many relations to other challenging graph-drawing problems such as small-area or small-volume drawings, layered or track drawings, and drawing graphs with low visual complexity. While some facts about our problem are implicit in previous work, this is the first treatment of the problem in its full generality. Our contribution is as follows. par We show lower and upper bounds for the numbers of lines and planes needed for covering drawings of graphs in certain graph classes. In some cases our bounds are asymptotically tight; in some cases we are able to determine exact values. par We relate our parameters to standard combinatorial characteristics of graphs (such as the chromatic number, treewidth, or arboricity) and to parameters that have been studied in graph drawing (such as the track number or the number of segments appearing in a drawing). par We pay special attention to planar graphs. For example, we show that there are qplanar graphs that can be drawn in 3-space on asymptotically fewer lines than in the plane.

@article{cflrvw-dgflf-JoCG20, abstract = {We investigate the problem of drawing graphs in 2D and 3D such that their edges (or only their vertices) can be covered by few lines or planes. We insist on straight-line edges and crossing-free drawings. This problem has many relations to other challenging graph-drawing problems such as small-area or small-volume drawings, layered or track drawings, and drawing graphs with low visual complexity. While some facts about our problem are implicit in previous work, this is the first treatment of the problem in its full generality. Our contribution is as follows. \par We show lower and upper bounds for the numbers of lines and planes needed for covering drawings of graphs in certain graph classes. In some cases our bounds are asymptotically tight; in some cases we are able to determine exact values. \par We relate our parameters to standard combinatorial characteristics of graphs (such as the chromatic number, treewidth, or arboricity) and to parameters that have been studied in graph drawing (such as the track number or the number of segments appearing in a drawing). \par We pay special attention to planar graphs. For example, we show that there are qplanar graphs that can be drawn in 3-space on asymptotically fewer lines than in the plane.}, author = {Chaplick, Steven and Fleszar, Krzysztof and Lipp, Fabian and Ravsky, Alexander and Verbitsky, Oleg and Wolff, Alexander}, journal = {Journal of Computational Geometry}, keywords = {affine_cover_number}, number = 1, pages = {433–475}, title = {Drawing Graphs on Few Lines and Few Planes}, volume = 11, year = 2020 }
Drawing and Labeling High-Quality Metro Maps by Mixed-Integer Programming. Martin Nöllenburg and Alexander Wolff. IEEE Transactions on Visualization and Computer Graphics, 17(5), pp. 626–641. 2011.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
Metro maps are schematic diagrams of public transport networks that serve as visual aids for route planning and navigation tasks. It is a challenging problem in network visualization to automatically draw appealing metro maps. There are two aspects to this problem that depend on each other: the layout problem of finding station and link coordinates and the labeling problem of placing non-overlapping station labels. par In this paper we present a new integral approach that solves the combined layout and labeling problem (each of which, independently, is known to be NP-hard) using mixed-integer programming (MIP). We identify seven design rules used in most real-world metro maps. We split these rules into hard and soft constraints and translate them into a MIP model. Our MIP formulation finds a metro map that satisfies all hard constraints (if such a drawing exists) and minimizes a weighted sum of costs that correspond to the soft constraints. We have implemented the MIP model and present a case study and the results of an expert assessment to evaluate the performance of our approach in comparison to both manually designed official maps and results of previous layout methods.

@article{nw-dlhqm-TVCG11, abstract = {Metro maps are schematic diagrams of public transport networks that serve as visual aids for route planning and navigation tasks. It is a challenging problem in network visualization to automatically draw appealing metro maps. There are two aspects to this problem that depend on each other: the layout problem of finding station and link coordinates and the labeling problem of placing non-overlapping station labels. \par In this paper we present a new integral approach that solves the combined layout and labeling problem (each of which, independently, is known to be NP-hard) using mixed-integer programming (MIP). We identify seven design rules used in most real-world metro maps. We split these rules into hard and soft constraints and translate them into a MIP model. Our MIP formulation finds a metro map that satisfies all hard constraints (if such a drawing exists) and minimizes a weighted sum of costs that correspond to the soft constraints. We have implemented the MIP model and present a case study and the results of an expert assessment to evaluate the performance of our approach in comparison to both manually designed official maps and results of previous layout methods.}, author = {Nöllenburg, Martin and Wolff, Alexander}, journal = {IEEE Transactions on Visualization and Computer Graphics}, keywords = {network_visualization}, number = 5, pages = {626–641}, title = {Drawing and Labeling High-Quality Metro Maps by Mixed-Integer Programming}, volume = 17, year = 2011 }

Complete Publication List

by citations (Google Scholar)
chronologically (DBLP)
chronologically (ORCID)
chronologically (local list)
by type (local list)

Prof. Dr. Alexander Wolff

Current Teaching

Research

Work in Committees

Short CV

Key Publications

Complete Publication List

Picture credits