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, 1:30–2:30 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 Algorithms and Data Structures (B.Sc. Inf, LuRI, GamesEng, InNa; LA Inf.)
lecture Approximation Algorithms (M.Sc. Inf)
seminar Visualization of Graphs (M.Sc./B.Sc. Inf)

» more

Research

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

Work in Committees

2017– member of the editorial boards of the open-access journals JoCG and JGAA
program co-chair of the conference GD 2013 (with Stephen Wismath) and the workshop EuroCG 2020 (with Steve Chaplick and Philipp Kindermann)
program committees of the conferences ESA (2013), WAOA (2018), ISAAC (2022, 2014, 2011, 2006), GD (2020, 2017, 2015, 2013, 2012, 2006), PacificVis (2013, 2012, 2011), SoCG Video/MM track (2012), AGILE (2010, 2009), Gene&MR (2011, 2010), CALDAM (2018), EuroCG (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 (GD)
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

Adjacency Graphs of Polyhedral Surfaces Arseneva, Elena; Kleist, Linda; Klemz, Boris; Löffler, Maarten; Schulz, André; Vogtenhuber, Birgit; Wolff, Alexander in Proc. 37th Annu. Sympos. Comput. Geom. (SoCG’21), LIPIcs, K. Buchin, Éric Colin de Verdière (eds.) (2021). (Vol. 189) 11:1–17.
- [ BibTeX ]
- [ DOI ]
- [ slides ]
- [ arxiv ]
- [ video ]
@inproceedings{akklsvw-dgps-SoCG21, author = {Arseneva, Elena and Kleist, Linda and Klemz, Boris and L{\"o}ffler, Maarten and Schulz, Andr{\'e} and Vogtenhuber, Birgit and Wolff, Alexander}, booktitle = {Proc. 37th Annu. Sympos. Comput. Geom. (SoCG'21)}, editor = {Buchin, Kevin and \'{E}ric {Colin de Verdi{\`e}re}}, keywords = {realizability}, pages = {11:1–17}, publisher = {Schloss Dagstuhl – Leibniz-Zentrum f{\"u}r Informatik}, series = {LIPIcs}, title = {Adjacency Graphs of Polyhedral Surfaces}, volume = 189, year = 2021 }
Drawing and Labeling High-Quality Metro Maps by Mixed-Integer Programming Nöllenburg, Martin; Wolff, Alexander in IEEE Transactions on Visualization and Computer Graphics (2011). 17(5) 626–641.
- [ 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{\"o}llenburg, Martin and Wolff, Alexander}, journal = {IEEE Transactions on Visualization and Computer Graphics}, keywords = {octilinear_layout}, number = 5, pages = {626–641}, title = {Drawing and Labeling High-Quality Metro Maps by Mixed-Integer Programming}, volume = 17, year = 2011 }
Trimming of Graphs, with Application to Point Labeling Erlebach, Thomas; Hagerup, Torben; Jansen, Klaus; Minzlaff, Moritz; Wolff, Alexander in Theory of Computing Systems (2010). 47(3) 613–636.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
For $$t>0$$ and $$g\ge 0$$, a vertex-weighted graph of total weight $$W$$ is \emph{$$(t,g)$$-trimmable if it contains a vertex-induced subgraph of total weight at least $$(1-1/t)W$$ and with no simple path of more than $$g$$ edges. A family of graphs is \emph{trimmable if for every constant $$t>0$$, there is a constant $$g\ge 0$$ such that every vertex-weighted graph in the family is $$(t,g)$$-trimmable. We show that every family of graphs of bounded domino treewidth is trimmable. This implies that every family of graphs of bounded degree is trimmable if the graphs in the family have bounded treewidth or are planar. We also show that every family of directed graphs of bounded layer bandwidth (a less restrictive condition than bounded directed bandwidth) is trimmable. As an application of these results, we derive polynomial-time approximation schemes for various forms of the problem of labeling a subset of given weighted point features with nonoverlapping sliding axes-parallel rectangular labels so as to maximize the total weight of the labeled features, provided that the ratios of label heights or the ratios of label lengths are bounded by a constant. This settles one of the last major open questions in the theory of map labeling.

@article{ehjmw-tgapl-10, abstract = {For $t>0$ and $g\ge 0$, a vertex-weighted graph of total weight $W$ is \emph{$(t,g)$-trimmable} if it contains a vertex-induced subgraph of total weight at least $(1-1/t)W$ and with no simple path of more than $g$ edges. A family of graphs is \emph{trimmable} if for every constant $t>0$, there is a constant $g\ge 0$ such that every vertex-weighted graph in the family is $(t,g)$-trimmable. We show that every family of graphs of bounded domino treewidth is trimmable. This implies that every family of graphs of bounded degree is trimmable if the graphs in the family have bounded treewidth or are planar. We also show that every family of directed graphs of bounded layer bandwidth (a less restrictive condition than bounded directed bandwidth) is trimmable. As an application of these results, we derive polynomial-time approximation schemes for various forms of the problem of labeling a subset of given weighted point features with nonoverlapping sliding axes-parallel rectangular labels so as to maximize the total weight of the labeled features, provided that the ratios of label heights or the ratios of label lengths are bounded by a constant. This settles one of the last major open questions in the theory of map labeling.}, author = {Erlebach, Thomas and Hagerup, Torben and Jansen, Klaus and Minzlaff, Moritz and Wolff, Alexander}, journal = {Theory of Computing Systems}, keywords = {trimming_weighted_graphs}, number = 3, pages = {613–636}, title = {Trimming of Graphs, with Application to Point Labeling}, volume = 47, year = 2010 }
Computing Large Matchings Fast Rutter, Ignaz; Wolff, Alexander in ACM Transactions on Algorithms (2010). 7(1) article 1, 21 pages.
- [ Abstract ]
- [ BibTeX ]
- [ URL ]
- [ DOI ]
- [ pdf ]
- [ slides ]
In this paper we present algorithms for computing large matchings in 3-regular graphs, graphs with maximum degree 3, and 3-connected planar graphs. The algorithms give a guarantee on the size of the computed matching and take linear or slightly superlinear time. Thus they are faster than the best-known algorithm for computing maximum matchings in general graphs, which runs in $$O(\sqrt{n}m)$$ time, where $$n$$ denotes the number of vertices and $$m$$ the number of edges of the given graph. For the classes of 3-regular graphs and graphs with maximum degree 3, the bounds we achieve are known to be best possible. par We also investigate graphs with block trees of bounded degree, where the $$d$$-block tree is the adjacency graph of the $$d$$-connected components of the given graph. In 3-regular graphs and 3-connected planar graphs with bounded-degree 2- and 4-block trees, respectively, we show how to compute \emph{maximum matchings in slightly superlinear time.

@article{rw-clmf-TALG10, abstract = {In this paper we present algorithms for computing large matchings in 3-regular graphs, graphs with maximum degree 3, and 3-connected planar graphs. The algorithms give a guarantee on the size of the computed matching and take linear or slightly superlinear time. Thus they are faster than the best-known algorithm for computing maximum matchings in general graphs, which runs in $O(\sqrt{n}m)$ time, where $n$ denotes the number of vertices and $m$ the number of edges of the given graph. For the classes of 3-regular graphs and graphs with maximum degree 3, the bounds we achieve are known to be best possible. \par We also investigate graphs with block trees of bounded degree, where the $d$-block tree is the adjacency graph of the $d$-connected components of the given graph. In 3-regular graphs and 3-connected planar graphs with bounded-degree 2- and 4-block trees, respectively, we show how to compute \emph{maximum} matchings in slightly superlinear time.}, author = {Rutter, Ignaz and Wolff, Alexander}, journal = {ACM Transactions on Algorithms}, keywords = {myown}, number = 1, pages = {article 1, 21 pages}, title = {Computing Large Matchings Fast}, volume = 7, year = 2010 }
Untangling a Planar Graph Goaoc, Xavier; Kratochvíl, Jan; Okamoto, Yoshio; Shin, Chan-Su; Spillner, Andreas; Wolff, Alexander in Discrete & Computational Geometry (2009). 42(4) 542–569.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
- [ pdf ]
A straight-line drawing $$\delta$$ of a planar graph $$G$$ need not be plane, but can be made so by \emph{untangling it, that is, by moving some of the vertices of $$G$$. Let shift$$(G,\delta)$$ denote the minimum number of vertices that need to be moved to untangle $$\delta$$. We show that shift$$(G,\delta)$$ is NP-hard to compute and to approximate. Our hardness results extend to a version of \textsc{1BendPointSetEmbeddability, a well-known graph-drawing problem. par Further we define fix$$(G,\delta)=n-shift(G,\delta)$$ to be the maximum number of vertices of a planar $$n$$-vertex graph $$G$$ that can be fixed when untangling $$\delta$$. We give an algorithm that fixes at least $$\sqrt{((\log n)-1)/\log \log n}$$ vertices when untangling a drawing of an $$n$$-vertex graph $$G$$. If $$G$$ is outerplanar, the same algorithm fixes at least $$\sqrt{n/2}$$ vertices. On the other hand we construct, for arbitrarily large $$n$$, an $$n$$-vertex planar graph $$G$$ and a drawing $$\delta_G$$ of $$G$$ with fix$$(G,\delta_G) \le \sqrt{n-2}+1$$ and an $$n$$-vertex outerplanar graph $$H$$ and a drawing $$\delta_H$$ of $$H$$ with fix$$(H,\delta_H) \le 2 \sqrt{n-1}+1$$. Thus our algorithm is asymptotically worst-case optimal for outerplanar graphs.

@article{gkossw-upg-DCG09, abstract = {A straight-line drawing $\delta$ of a planar graph $G$ need not be plane, but can be made so by \emph{untangling} it, that is, by moving some of the vertices of $G$. Let shift$(G,\delta)$ denote the minimum number of vertices that need to be moved to untangle $\delta$. We show that shift$(G,\delta)$ is NP-hard to compute and to approximate. Our hardness results extend to a version of \textsc{1BendPointSetEmbeddability}, a well-known graph-drawing problem. \par Further we define fix$(G,\delta)=n-shift(G,\delta)$ to be the maximum number of vertices of a planar $n$-vertex graph $G$ that can be fixed when untangling $\delta$. We give an algorithm that fixes at least $\sqrt{((\log n)-1)/\log \log n}$ vertices when untangling a drawing of an $n$-vertex graph $G$. If $G$ is outerplanar, the same algorithm fixes at least $\sqrt{n/2}$ vertices. On the other hand we construct, for arbitrarily large $n$, an $n$-vertex planar graph $G$ and a drawing $\delta_G$ of $G$ with fix$(G,\delta_G) \le \sqrt{n-2}+1$ and an $n$-vertex outerplanar graph $H$ and a drawing $\delta_H$ of $H$ with fix$(H,\delta_H) \le 2 \sqrt{n-1}+1$. Thus our algorithm is asymptotically worst-case optimal for outerplanar graphs.}, author = {Goaoc, Xavier and Kratochv{\'i}l, Jan and Okamoto, Yoshio and Shin, Chan-Su and Spillner, Andreas and Wolff, Alexander}, journal = {Discrete \& Computational Geometry}, keywords = {untangling}, number = 4, pages = {542–569}, title = {Untangling a Planar Graph}, volume = 42, year = 2009 }

Complete Publication List

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

Prof. Dr. Alexander Wolff