Wolff, Alexander - Lehrstuhl für Informatik I - Algorithmen und Komplexität

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

Gebäude M4, Raum 01.001
Sprechstunde: Mi, 13:30–14:30 Uhr
Tel.: +49 (0) 931-31-85055
Fax: +49 (0) 931-31-825200

vorname.nachname "at" uni-wuerzburg.de

orcid.org/0000-0001-5872-718X

Aktuelle Lehre

Vorlesung Algorithmen und Datenstrukturen (B.Sc. Inf, LuRI, GamesEng, InNa; LA Inf.)
Vorlesung Approximationsalgorithmen (M.Sc. Inf)
Seminar Visualisierung von Graphen (M.Sc./B.Sc. Inf)

» mehr

Forschung

Graphenzeichnen
Algorithmische Geometrie
Algorithmen für Geografische Informationssysteme (GIS)
Graphalgorithmen

Arbeit in Ausschüssen

2017– Mitherausgeber der Open-Access-Zeitschriften JoCG und JGAA
Programmausschuss-Kovorsitz bei der Konferenz GD 2013 (mit Stephen Wismath) und dem Workshop EuroCG 2020 (mit Steve Chaplick und Philipp Kindermann)
Programmausschüsse der Konferenzen 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)
Organisationsausschuss-Vorsitzender bei GD 2014 und EuroCG 2020 (mit Steve Chaplick und Philipp Kindermann)
2011–15 Lenkungsausschuss der European Symposia on Algorithms (ESA)
2012–17 and 2021–24 Lenkungsausschuss der International Symposia on Graph Drawing (GD)
2011–17 und 2021–23 Fakultätsrat der Fakultät für Mathematik und Informatik, Universität Würzburg

Kurzer Werdegang

2021–2023
Geschäftsführender Vorstand des Instituts für Informatik, Universität Würzburg
2015–2017:
Dekan der Fakultät für Mathematik und Informatik, Universität Würzburg
2013–2015:
Vizedekan der Fakultät für Mathematik und Informatik, Universität Würzburg
2011–2013:
Geschäftsführender Vorstand des Instituts für Informatik, Universität Würzburg
seit 2009:
Professur am Lehrstuhl für Algorithmen, Komplexität und wissensbasierte Systeme, Institut für Informatik, Universität Würzburg

» mehr

Wichtige Veröffentlichungen

Adjacency Graphs of Polyhedral Surfaces. Elena Arseneva, Linda Kleist, Boris Klemz, Maarten Löffler, André Schulz, Birgit Vogtenhuber und Alexander Wolff. Discrete & Computational Geometry. 2024.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
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{\"o}ffler, Maarten and Schulz, Andr{\'e} and Vogtenhuber, Birgit and Wolff, Alexander}, journal = {Discrete \& Computational Geometry}, keywords = {realizability}, title = {Adjacency Graphs of Polyhedral Surfaces}, year = 2024 }
Drawing Graphs on Few Lines and Few Planes. Steven Chaplick, Krzysztof Fleszar, Fabian Lipp, Alexander Ravsky, Oleg Verbitsky und Alexander Wolff. Journal of Computational Geometry, 11(1), S. 433–475. 2020.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
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 und Alexander Wolff. IEEE Transactions on Visualization and Computer Graphics, 17(5), S. 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{\"o}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 }
Computing Large Matchings Fast. Ignaz Rutter und Alexander Wolff. ACM Transactions on Algorithms, 7(1), S. article 1, 21 pages. 2010.
- [ 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 = {maximum_matchings}, number = 1, pages = {article 1, 21 pages}, title = {Computing Large Matchings Fast}, volume = 7, year = 2010 }
Trimming of Graphs, with Application to Point Labeling. Thomas Erlebach, Torben Hagerup, Klaus Jansen, Moritz Minzlaff und Alexander Wolff. Theory of Computing Systems, 47(3), S. 613–636. 2010.
- [ 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 = {domino_treewidth}, number = 3, pages = {613–636}, title = {Trimming of Graphs, with Application to Point Labeling}, volume = 47, year = 2010 }

Vollständige Publikationsliste

nach Referenzen (Google Scholar)
chronologisch (DBLP)
chronologisch (ORCID)
chronologisch (lokale Liste)
nach Typ (lokale Liste)

Prof. Dr. Alexander Wolff