Graph Drawing

Compact Drawings of 1-Planar Graphs with Right-Angle Crossings and Few Bends. Chaplick, Steven; Lipp, Fabian; Wolff, Alexander; Zink, Johannes. In Computational Geometry: Theory and Applications, 84, pp. 50–68. 2019.

[ Abstract ]
[ BibTeX ]
[ slides ]
[ pdf ]

We study the following classes of beyond-planar graphs: 1-planar, IC-planar, and NIC-planar graphs. These are the graphs that admit a 1-planar, IC-planar, and NIC-planar drawing, respectively. A drawing of a graph is \emph{1-planar} if every edge is crossed at most once. A 1-planar drawing is \emph{IC-planar} if no two pairs of crossing edges share a vertex. A 1-planar drawing is \emph{NIC-planar} if no two pairs of crossing edges share two vertices. We study the relations of these beyond-planar graph classes (\emph{beyond-planar graphs} is a collective term for the primary attempts to generalize the planar graphs) to \emph{right-angle crossing} (\emph{RAC}) graphs that admit compact drawings on the grid with few bends. We present four drawing algorithms that preserve the given embeddings. First, we show that every \($n$\)-vertex NIC-planar graph admits a NIC-planar RAC drawing with at most one bend per edge on a grid of size \($O(n) times O(n)$\). Then, we show that every \($n$\)-vertex 1-planar graph admits a 1-planar RAC drawing with at most two bends per edge on a grid of size \($O(n^3) times O(n^3)$\). Finally, we make two known algorithms embedding-preserving; for drawing 1-planar RAC graphs with at most one bend per edge and for drawing IC-planar RAC graphs straight-line.

@article{clwz-cd1pg-CGTA19,
  abstract = {We study the following classes of beyond-planar graphs: 1-planar, IC-planar, and NIC-planar graphs. These are the graphs that admit a 1-planar, IC-planar, and NIC-planar drawing, respectively. A drawing of a graph is \emph{1-planar} if every edge is crossed at most once. A 1-planar drawing is \emph{IC-planar} if no two pairs of crossing edges share a vertex. A 1-planar drawing is \emph{NIC-planar} if no two pairs of crossing edges share two vertices. We study the relations of these beyond-planar graph classes (\emph{beyond-planar graphs} is a collective term for the primary attempts to generalize the planar graphs) to \emph{right-angle crossing} (\emph{RAC}) graphs that admit compact drawings on the grid with few bends. We present four drawing algorithms that preserve the given embeddings. First, we show that every $n$-vertex NIC-planar graph admits a NIC-planar RAC drawing with at most one bend per edge on a grid of size $O(n) \times O(n)$. Then, we show that every $n$-vertex 1-planar graph admits a 1-planar RAC drawing with at most two bends per edge on a grid of size $O(n^3) \times O(n^3)$. Finally, we make two known algorithms embedding-preserving; for drawing 1-planar RAC graphs with at most one bend per edge and for drawing IC-planar RAC graphs straight-line.},
  author = {Chaplick, Steven and Lipp, Fabian and Wolff, Alexander and Zink, Johannes},
  journal = {Computational Geometry: Theory and Applications},
  keywords = {gd-info1},
  note = {Special Issue on the 34th European Workshop on Computational Geometry},
  pages = {50–68},
  title = {Compact Drawings of 1-Planar Graphs with Right-Angle Crossings and Few Bends},
  volume = 84,
  year = 2019
}

Computing Optimal-Height Tangles Faster. Firman, Oksana; Kindermann, Philipp; Ravsky, Alexander; Wolff, Alexander; Zink, Johannes. In Proc. 27th Int. Symp. Graph Drawing & Network Vis. (GD’19), Vol. 11904 of Lecture Notes in Computer Science, D. Archambault, C. D. Tóth (eds.), pp. 203–215. Springer-Verlag, 2019.

[ BibTeX ]
[ slides ]

@inproceedings{fkrwz-cohtf-GD19,
  author = {Firman, Oksana and Kindermann, Philipp and Ravsky, Alexander and Wolff, Alexander and Zink, Johannes},
  booktitle = {Proc. 27th Int. Symp. Graph Drawing \& Network Vis. (GD'19)},
  editor = {Archambault, Daniel and Tóth, Csaba D.},
  keywords = {gd-info1},
  pages = {203–215},
  publisher = {Springer-Verlag},
  series = {Lecture Notes in Computer Science},
  title = {Computing Optimal-Height Tangles Faster},
  volume = 11904,
  year = 2019
}

Drawing Graphs on Few Circles and Few Spheres. Kryven, Myroslav; Ravsky, Alexander; Wolff, Alexander. In Journal of Graph Algorithms & Applications, 23(2), pp. 371–391. 2019.

[ Abstract ]
[ BibTeX ]
[ slides ]

Given a drawing of a graph, its \emph{visual complexity} is defined as the number of geometrical entities in the drawing, for example, the number of segments in a straight-line drawing or the number of arcs in a circular-arc drawing (in 2D). Recently, Chaplick et al. [GD 2016] introduced a different measure for the visual complexity, the \emph{affine cover number}, which is the minimum number of lines (or planes) that together cover a crossing-free straight-line drawing of a graph G in 2D (3D). In this paper, we introduce the \emph{spherical cover number}, which is the minimum number of circles (or spheres) that together cover a crossing-free circular-arc drawing in 2D (or 3D). It turns out that spherical covers are sometimes significantly smaller than affine covers. For complete, complete bipartite, and platonic graphs, we analyze their spherical cover numbers and compare them to their affine cover numbers as well as their segment and arc numbers. We also link the spherical cover number to other graph parameters such as treewidth and linear arboricity.

@article{krw-dgfcf-JGAA19,
  abstract = {Given a drawing of a graph, its \emph{visual complexity} is defined as the number of geometrical entities in the drawing, for example, the number of segments in a straight-line drawing or the number of arcs in a circular-arc drawing (in 2D). Recently, Chaplick et al.\ [GD 2016] introduced a different measure for the visual complexity, the \emph{affine cover number}, which is the minimum number of lines (or planes) that together cover a crossing-free straight-line drawing of a graph G in 2D (3D). In this paper, we introduce the \emph{spherical cover number}, which is the minimum number of circles (or spheres) that together cover a crossing-free circular-arc drawing in 2D (or 3D). It turns out that spherical covers are sometimes significantly smaller than affine covers. For complete, complete bipartite, and platonic graphs, we analyze their spherical cover numbers and compare them to their affine cover numbers as well as their segment and arc numbers. We also link the spherical cover number to other graph parameters such as treewidth and linear arboricity.},
  author = {Kryven, Myroslav and Ravsky, Alexander and Wolff, Alexander},
  journal = {Journal of Graph Algorithms \& Applications},
  keywords = {gd-info1},
  number = 2,
  pages = {371–391},
  title = {Drawing Graphs on Few Circles and Few Spheres},
  volume = 23,
  year = 2019
}

Stick Graphs with Length Constraints. Chaplick, Steven; Kindermann, Philipp; Löffler, Andre; Thiele, Florian; Wolff, Alexander; Zaft, Alexander; Zink, Johannes. In Proc. 27th Int. Symp. Graph Drawing & Network Vis. (GD’19), Vol. 11904 of Lecture Notes in Computer Science, D. Archambault, C. D. Tóth (eds.), pp. 3–17. Springer-Verlag, 2019.

[ BibTeX ]
[ slides ]

@inproceedings{ckltwzz-sglc-GD19,
  author = {Chaplick, Steven and Kindermann, Philipp and Löffler, Andre and Thiele, Florian and Wolff, Alexander and Zaft, Alexander and Zink, Johannes},
  booktitle = {Proc. 27th Int. Symp. Graph Drawing \& Network Vis. (GD'19)},
  editor = {Archambault, Daniel and Tóth, Csaba D.},
  keywords = {gd-info1},
  pages = {3–17},
  publisher = {Springer-Verlag},
  series = {Lecture Notes in Computer Science},
  title = {Stick Graphs with Length Constraints},
  volume = 11904,
  year = 2019
}

Beyond Outerplanarity. Chaplick, Steven; Kryven, Myroslav; Liotta, Giuseppe; Löffler, Andre; Wolff, Alexander. In Proc. 25th Int. Symp. Graph Drawing & Network Vis. (GD’17), Vol. 10692 of Lecture Notes in Computer Science, F. Frati, K.-L. Ma (eds.), pp. 546–559. Springer-Verlag, 2018.

[ BibTeX ]
[ slides ]

@inproceedings{ckllw-bo-GD17,
  author = {Chaplick, Steven and Kryven, Myroslav and Liotta, Giuseppe and Löffler, Andre and Wolff, Alexander},
  booktitle = {Proc. 25th Int. Symp. Graph Drawing \& Network Vis. (GD'17)},
  editor = {Frati, Fabrizio and Ma, Kwan-Liu},
  keywords = {gd-info1},
  pages = {546–559},
  publisher = {Springer-Verlag},
  series = {Lecture Notes in Computer Science},
  title = {Beyond Outerplanarity},
  volume = 10692,
  year = 2018
}

Computing Storylines with Few Block Crossings. van Dijk, Thomas C.; Lipp, Fabian; Markfelder, Peter; Wolff, Alexander. In Proc. 25th Int. Symp. Graph Drawing & Network Vis. (GD’17), Vol. 10692 of Lecture Notes in Computer Science, F. Frati, K.-L. Ma (eds.), pp. 365–378. Springer-Verlag, 2018.

[ BibTeX ]
[ slides ]

@inproceedings{dlmw-csfbc-GD17,
  author = {van Dijk, Thomas C. and Lipp, Fabian and Markfelder, Peter and Wolff, Alexander},
  booktitle = {Proc. 25th Int. Symp. Graph Drawing \& Network Vis. (GD'17)},
  editor = {Frati, Fabrizio and Ma, Kwan-Liu},
  keywords = {gd-info1},
  pages = {365–378},
  publisher = {Springer-Verlag},
  series = {Lecture Notes in Computer Science},
  title = {Computing Storylines with Few Block Crossings},
  volume = 10692,
  year = 2018
}

Orthogonal and Smooth Orthogonal Layouts of 1-Planar Graphs with Low Edge Complexity. Argyriou, Evmorfia; Cornelsen, Sabine; Förster, Henry; Kaufmann, Michael; Nöllenburg, Martin; Okamoto, Yoshio; Raftopoulou, Chrysanthi; Wolff, Alexander. In Proc. 26th Int. Symp. Graph Drawing & Network Vis. (GD’18), Vol. 11282 of Lecture Notes in Computer Science, T. Biedl, A. Kerren (eds.), pp. 509–523. Springer-Verlag, 2018.

[ BibTeX ]

@inproceedings{acfknorw-osol1-GD18,
  author = {Argyriou, Evmorfia and Cornelsen, Sabine and Förster, Henry and Kaufmann, Michael and Nöllenburg, Martin and Okamoto, Yoshio and Raftopoulou, Chrysanthi and Wolff, Alexander},
  booktitle = {Proc. 26th Int. Symp. Graph Drawing \& Network Vis. (GD'18)},
  editor = {Biedl, Therese and Kerren, Andreas},
  keywords = {gd-info1},
  pages = {509–523},
  publisher = {Springer-Verlag},
  series = {Lecture Notes in Computer Science},
  title = {Orthogonal and Smooth Orthogonal Layouts of 1-Planar Graphs with Low Edge Complexity},
  volume = 11282,
  year = 2018
}

Planar {L}-Drawings of Directed Graphs. Chaplick, Steven; Chimani, Markus; Cornelsen, Sabine; {Da Lozzo}, Giordano; Nöllenburg, Martin; Patrignani, Maurizio; Tollis, Ioannis G.; Wolff, Alexander. In Proc. 25th Int. Symp. Graph Drawing & Network Vis. (GD’17), Vol. 10692 of Lecture Notes in Computer Science, F. Frati, K.-L. Ma (eds.), pp. 465–478. Springer-Verlag, 2018.

[ BibTeX ]
[ slides ]

@inproceedings{cccdnptw-plddg-GD17,
  author = {Chaplick, Steven and Chimani, Markus and Cornelsen, Sabine and {Da Lozzo}, Giordano and Nöllenburg, Martin and Patrignani, Maurizio and Tollis, Ioannis G. and Wolff, Alexander},
  booktitle = {Proc. 25th Int. Symp. Graph Drawing \& Network Vis. (GD'17)},
  editor = {Frati, Fabrizio and Ma, Kwan-Liu},
  keywords = {gd-info1},
  pages = {465–478},
  publisher = {Springer-Verlag},
  series = {Lecture Notes in Computer Science},
  title = {Planar {L}-Drawings of Directed Graphs},
  volume = 10692,
  year = 2018
}

On the Maximum Crossing Number. Chimani, Markus; Felsner, Stefan; Kobourov, Stephen; Ueckerdt, Torsten; Valtr, Pavel; Wolff, Alexander. In Journal of Graph Algorithms & Applications, 22(1), pp. 67–87. 2018.

[ Abstract ]
[ BibTeX ]

Research about crossings is typically about minimization. In this paper, we consider \emph{maximizing} the number of crossings over all possible ways to draw a given graph in the plane. Alpert et al. [Electron. J. Combin., 2009] conjectured that any graph has a \emph{convex} straight-line drawing, that is, a drawing with vertices in convex position, that maximizes the number of edge crossings. We disprove this conjecture by constructing a planar graph on twelve vertices that admits a non-convex drawing with more crossings than any convex drawing. Bald et al. [Proc. COCOON, 2016] showed that it is NP-hard to compute the maximum number of crossings of a geometric graph and that the weighted geometric case is NP-hard to approximate. We strengthen these results by showing hardness of approximation even for the unweighted geometric case. We also prove that the unweighted topological case is NP-hard.

@article{cfkuvw-mcn-JGAA18,
  abstract = {Research about crossings is typically about minimization. In this paper, we consider \emph{maximizing} the number of crossings over all possible ways to draw a given graph in the plane. Alpert et al. [Electron. J. Combin., 2009] conjectured that any graph has a \emph{convex} straight-line drawing, that is, a drawing with vertices in convex position, that maximizes the number of edge crossings. We disprove this conjecture by constructing a planar graph on twelve vertices that admits a non-convex drawing with more crossings than any convex drawing. Bald et al. [Proc. COCOON, 2016] showed that it is NP-hard to compute the maximum number of crossings of a geometric graph and that the weighted geometric case is NP-hard to approximate. We strengthen these results by showing hardness of approximation even for the unweighted geometric case. We also prove that the unweighted topological case is NP-hard.},
  author = {Chimani, Markus and Felsner, Stefan and Kobourov, Stephen and Ueckerdt, Torsten and Valtr, Pavel and Wolff, Alexander},
  journal = {Journal of Graph Algorithms \& Applications},
  keywords = {gd-info1},
  note = {Special issue on ``Graph Drawing Beyond Planarity''.},
  number = 1,
  pages = {67–87},
  title = {On the Maximum Crossing Number},
  volume = 22,
  year = 2018
}

Compact Drawings of 1-Planar Graphs with Right-Angle Crossings and Few Bends. Chaplick, Steven; Lipp, Fabian; Wolff, Alexander; Zink, Johannes. In Proc. 26th Int. Symp. Graph Drawing & Network Vis. (GD’18), Vol. 11282 of Lecture Notes in Computer Science, T. Biedl, A. Kerren (eds.), pp. 137–151. Springer-Verlag, 2018.

[ BibTeX ]
[ slides ]

@inproceedings{clwz-cd1pg-GD18,
  author = {Chaplick, Steven and Lipp, Fabian and Wolff, Alexander and Zink, Johannes},
  booktitle = {Proc. 26th Int. Symp. Graph Drawing \& Network Vis. (GD'18)},
  editor = {Biedl, Therese and Kerren, Andreas},
  keywords = {gd-info1},
  pages = {137–151},
  publisher = {Springer-Verlag},
  series = {Lecture Notes in Computer Science},
  title = {Compact Drawings of 1-Planar Graphs with Right-Angle Crossings and Few Bends},
  volume = 11282,
  year = 2018
}

Snapping Graph Drawings to the Grid Optimally. Löffler, Andre; van Dijk, Thomas C.; Wolff, Alexander. In Proc. 24th Int. Symp. Graph Drawing & Network Vis. (GD’16), Vol. 9801 of Lecture Notes in Computer Science, Y. Hu, M. Nöllenburg (eds.), pp. 144–151. Springer-Verlag, 2016.

[ BibTeX ]
[ slides ]

@inproceedings{ldw-sgdgo-GD16,
  author = {Löffler, Andre and van Dijk, Thomas C. and Wolff, Alexander},
  booktitle = {Proc. 24th Int. Symp. Graph Drawing \& Network Vis. (GD'16)},
  editor = {Hu, Yifan and Nöllenburg, Martin},
  keywords = {gd-info1},
  pages = {144–151},
  publisher = {Springer-Verlag},
  series = {Lecture Notes in Computer Science},
  title = {Snapping Graph Drawings to the Grid Optimally},
  volume = 9801,
  year = 2016
}

Obstructing Visibilities with One Obstacle. Chaplick, Steven; Lipp, Fabian; Park, {Ji-won}; Wolff, Alexander. In Proc. 24th Int. Symp. Graph Drawing & Network Vis. (GD’16), Vol. 9801 of Lecture Notes in Computer Science, Y. Hu, M. Nöllenburg (eds.), pp. 295–308. Springer-Verlag, 2016.

[ BibTeX ]
[ slides ]

@inproceedings{clpw-ov1o-GD16,
  author = {Chaplick, Steven and Lipp, Fabian and Park, {Ji-won} and Wolff, Alexander},
  booktitle = {Proc. 24th Int. Symp. Graph Drawing \& Network Vis. (GD'16)},
  editor = {Hu, Yifan and Nöllenburg, Martin},
  keywords = {gd-info1},
  pages = {295–308},
  publisher = {Springer-Verlag},
  series = {Lecture Notes in Computer Science},
  title = {Obstructing Visibilities with One Obstacle},
  volume = 9801,
  year = 2016
}

Block Crossings in Storyline Visualizations. van Dijk, Thomas C.; Fink, Martin; Fischer, Norbert; Lipp, Fabian; Markfelder, Peter; Ravsky, Alexander; Suri, Subhash; Wolff, Alexander. In Proc. 24th Int. Symp. Graph Drawing & Network Vis. (GD’16), Vol. 9801 of Lecture Notes in Computer Science, Y. Hu, M. Nöllenburg (eds.), pp. 382–398. Springer-Verlag, 2016.

[ BibTeX ]
[ slides ]

@inproceedings{dfflmrsw-bcsv-GD16,
  author = {van Dijk, Thomas C. and Fink, Martin and Fischer, Norbert and Lipp, Fabian and Markfelder, Peter and Ravsky, Alexander and Suri, Subhash and Wolff, Alexander},
  booktitle = {Proc. 24th Int. Symp. Graph Drawing \& Network Vis. (GD'16)},
  editor = {Hu, Yifan and Nöllenburg, Martin},
  keywords = {gd-info1},
  note = {Received best-paper award at GD 2016},
  pages = {382–398},
  publisher = {Springer-Verlag},
  series = {Lecture Notes in Computer Science},
  title = {Block Crossings in Storyline Visualizations},
  volume = 9801,
  year = 2016
}

Faster Force-Directed Graph Drawing with the Well-Separated Pair Decomposition. Lipp, Fabian; Wolff, ALexander; Zink, Johannes. In Proc. 23rd Int. Symp. Graph Drawing & Network Vis. (GD’15), Vol. 9411 of Lecture Notes in Computer Science, E. {Di Giacomo}, A. Lubiw (eds.), pp. 52–59. Springer-Verlag, 2015.

[ BibTeX ]
[ pdf ]

@inproceedings{lwz-ffggd-GD15,
  author = {Lipp, Fabian and Wolff, ALexander and Zink, Johannes},
  booktitle = {Proc. 23rd Int. Symp. Graph Drawing \& Network Vis. (GD'15)},
  editor = {{Di Giacomo}, Emilio and Lubiw, Anna},
  keywords = {gd-info1},
  pages = {52–59},
  publisher = {Springer-Verlag},
  series = {Lecture Notes in Computer Science},
  title = {Faster Force-Directed Graph Drawing with the Well-Separated Pair Decomposition},
  volume = 9411,
  year = 2015
}

Pixel and Voxel Representations of Graphs. Alam, Md. Jawaherul; Bläsius, Thomas; Rutter, Ignaz; Ueckerdt, Torsten; Wolff, Alexander. In Proc. 23rd Int. Symp. Graph Drawing & Network Vis. (GD’15), Vol. 9411 of Lecture Notes in Computer Science, E. {Di Giacomo}, A. Lubiw (eds.), pp. 472–486. Springer-Verlag, 2015.

[ BibTeX ]
[ slides ]
[ pdf ]

@inproceedings{abruw-pvrg-GD15,
  author = {Alam, Md. Jawaherul and Bläsius, Thomas and Rutter, Ignaz and Ueckerdt, Torsten and Wolff, Alexander},
  booktitle = {Proc. 23rd Int. Symp. Graph Drawing \& Network Vis. (GD'15)},
  editor = {{Di Giacomo}, Emilio and Lubiw, Anna},
  keywords = {gd-info1},
  pages = {472–486},
  publisher = {Springer-Verlag},
  series = {Lecture Notes in Computer Science},
  title = {Pixel and Voxel Representations of Graphs},
  volume = 9411,
  year = 2015
}

Drawing Graphs within Restricted Area. Aulbach, Maximilian; Fink, Martin; Schuhmann, Julian; Wolff, Alexander. In Proc. 22nd Int. Sympos. Graph Drawing (GD’14), Vol. 8871 of Lecture Notes in Computer Science, C. Duncan, A. Symvonis (eds.), pp. 367–379. Springer-Verlag, 2014.

[ BibTeX ]

@inproceedings{afsw-dgra-GD14,
  author = {Aulbach, Maximilian and Fink, Martin and Schuhmann, Julian and Wolff, Alexander},
  booktitle = {Proc. 22nd Int. Sympos. Graph Drawing (GD'14)},
  editor = {Duncan, Christian and Symvonis, Antonios},
  keywords = {gd-info1},
  pages = {367–379},
  publisher = {Springer-Verlag},
  series = {Lecture Notes in Computer Science},
  title = {Drawing Graphs within Restricted Area},
  volume = 8871,
  year = 2014
}

Luatodonotes: Boundary Labeling for Annotations in Texts. Kindermann, Philipp; Lipp, Fabian; Wolff, Alexander. In Proc. 22nd Int. Sympos. Graph Drawing (GD’14), Vol. 8871 of Lecture Notes in Computer Science, C. Duncan, A. Symvonis (eds.), pp. 76–88. Springer-Verlag, 2014.

[ BibTeX ]
[ pdf ]

@inproceedings{klw-lblat-GD14,
  author = {Kindermann, Philipp and Lipp, Fabian and Wolff, Alexander},
  booktitle = {Proc. 22nd Int. Sympos. Graph Drawing (GD'14)},
  editor = {Duncan, Christian and Symvonis, Antonios},
  keywords = {gd-info1},
  pages = {76–88},
  publisher = {Springer-Verlag},
  series = {Lecture Notes in Computer Science},
  title = {Luatodonotes: Boundary Labeling for Annotations in Texts},
  volume = 8871,
  year = 2014
}

On Monotone Drawings of Trees. Kindermann, Philipp; Schulz, André; Spoerhase, Joachim; Wolff, Alexander. In Proc. 22nd Int. Sympos. Graph Drawing (GD’14), Vol. 8871 of Lecture Notes in Computer Science, C. Duncan, A. Symvonis (eds.), pp. 488–500. Springer-Verlag, 2014.

[ BibTeX ]
[ pdf ]

@inproceedings{kssw-mdt-GD14,
  author = {Kindermann, Philipp and Schulz, André and Spoerhase, Joachim and Wolff, Alexander},
  booktitle = {Proc. 22nd Int. Sympos. Graph Drawing (GD'14)},
  editor = {Duncan, Christian and Symvonis, Antonios},
  keywords = {gd-info1},
  pages = {488–500},
  publisher = {Springer-Verlag},
  series = {Lecture Notes in Computer Science},
  title = {On Monotone Drawings of Trees},
  volume = 8871,
  year = 2014
}

Drawing (Complete) Binary Tanglegrams: Hardness, Approximation, Fixed-Parameter Tractability. Buchin, Kevin; Buchin, Maike; Byrka, Jaroslaw; Nöllenburg, Martin; Okamoto, Yoshio; Silveira, Rodrigo I.; Wolff, Alexander. In Algorithmica, 62(1--2), pp. 309–332. 2012.

[ Abstract ]
[ BibTeX ]
[ slides ]
[ pdf ]

A \emph{binary tanglegram} is a drawing of a pair \ttree{S,T} of rooted binary trees whose leaf sets are in one-to-one correspondence; matching leaves are connected by inter-tree edges. For applications, for example, in phylogenetics, it is essential that both trees are drawn without edge crossings and that the inter-tree edges have as few crossings as possible. It is known that finding a tanglegram with the minimum number of crossings is NP-hard and that the problem is fixed-parameter tractable with respect to that number. par We prove that under the Unique Games Conjecture there is no constant-factor approximation for binary trees. We show that the problem is NP-hard even if both trees are complete binary trees. For this case we give an \($O(n^3)$\)-time 2-approximation and a new, simple fixed-parameter algorithm. We show that the maximization version of the dual problem for binary trees can be reduced to a version of \textsc{MaxCut} for which the algorithm of Goemans and Williamson yields a \($0.878$\)-approximation.

@article{bbbnosw-dcbth-12,
  abstract = {A \emph{binary tanglegram} is a drawing of a pair \ttree{S,T} of rooted binary trees whose leaf sets are in one-to-one correspondence; matching leaves are connected by inter-tree edges. For applications, for example, in phylogenetics, it is essential that both trees are drawn without edge crossings and that the inter-tree edges have as few crossings as possible. It is known that finding a tanglegram with the minimum number of crossings is NP-hard and that the problem is fixed-parameter tractable with respect to that number. \par We prove that under the Unique Games Conjecture there is no constant-factor approximation for binary trees. We show that the problem is NP-hard even if both trees are complete binary trees. For this case we give an $O(n^3)$-time 2-approximation and a new, simple fixed-parameter algorithm. We show that the maximization version of the dual problem for binary trees can be reduced to a version of \textsc{MaxCut} for which the algorithm of Goemans and Williamson yields a $0.878$-approximation.},
  author = {Buchin, Kevin and Buchin, Maike and Byrka, Jaroslaw and Nöllenburg, Martin and Okamoto, Yoshio and Silveira, Rodrigo I. and Wolff, Alexander},
  journal = {Algorithmica},
  keywords = {gd-info1},
  number = {1–2},
  pages = {309–332},
  title = {Drawing (Complete) Binary Tanglegrams: Hardness, Approximation, Fixed-Parameter Tractability},
  volume = 62,
  year = 2012
}

Drawing Graphs with Vertices at Specified Positions and Crossings at Large Angles. Fink, Martin; Haunert, Jan-Henrik; Mchedlidze, Tamara; Spoerhase, Joachim; Wolff, Alexander. In Proc. Workshop Algorithms Comput. (WALCOM’12), Vol. 7157 of Lecture Notes in Computer Science, {Md. S. Rahman, {Shin- ichi} Nakano (eds.), pp. 186–197. Springer-Verlag, 2012.

[ BibTeX ]
[ pdf ]

@inproceedings{fhmsw-dgvsp-WALCOM12,
  author = {Fink, Martin and Haunert, Jan-Henrik and Mchedlidze, Tamara and Spoerhase, Joachim and Wolff, Alexander},
  booktitle = {Proc. Workshop Algorithms Comput. (WALCOM'12)},
  editor = {Rahman, {Md. Saidur} and Nakano, {Shin-ichi}},
  keywords = {gd-info1},
  pages = {186–197},
  publisher = {Springer-Verlag},
  series = {Lecture Notes in Computer Science},
  title = {Drawing Graphs with Vertices at Specified Positions and Crossings at Large Angles},
  volume = 7157,
  year = 2012
}

Drawing and Labeling High-Quality Metro Maps by Mixed-Integer Programming. Nöllenburg, Martin; Wolff, Alexander. In IEEE Transactions on Visualization and Computer Graphics, 17(5), pp. 626–641. 2011.

[ Abstract ]
[ BibTeX ]
[ 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
}

Schematization in Cartography, Visualization, and Computational Geometry. Dykes, Jason; Müller-Hannemann, Matthias; Wolff, Alexander. In Vol. 10461 of Dagstuhl Seminar Proceedings. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2011.

[ BibTeX ]
[ URL ]

@proceedings{dmw-scvcg-11,
  editor = {Dykes, Jason and Müller-Hannemann, Matthias and Wolff, Alexander},
  keywords = {gd-info1},
  publisher = {Schloss Dagstuhl – Leibniz-Zentrum für Informatik},
  series = {Dagstuhl Seminar Proceedings},
  title = {Schematization in Cartography, Visualization, and Computational Geometry},
  volume = 10461,
  year = 2011
}

Manhattan-Geodesic Embedding of Planar Graphs. Katz, Bastian; Krug, Marcus; Rutter, Ignaz; Wolff, Alexander. In Proc. 17th Int. Sympos. Graph Drawing (GD’09), Vol. 5849 of Lecture Notes in Computer Science, D. Eppstein, E. R. Gansner (eds.), pp. 207–218. Springer-Verlag, 2010.

[ BibTeX ]
[ pdf ]

@inproceedings{kkrw-mgepg-10,
  author = {Katz, Bastian and Krug, Marcus and Rutter, Ignaz and Wolff, Alexander},
  booktitle = {Proc. 17th Int. Sympos. Graph Drawing (GD'09)},
  editor = {Eppstein, David and Gansner, Emden R.},
  keywords = {gd-info1},
  pages = {207–218},
  publisher = {Springer-Verlag},
  series = {Lecture Notes in Computer Science},
  title = {Manhattan-Geodesic Embedding of Planar Graphs},
  volume = 5849,
  year = 2010
}

Untangling a Planar Graph. Goaoc, Xavier; Kratochvíl, Jan; Okamoto, Yoshio; Shin, Chan-Su; Spillner, Andreas; Wolff, Alexander. In Discrete & Computational Geometry, 42(4), pp. 542–569. 2009.

[ Abstract ]
[ BibTeX ]
[ 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íl, Jan and Okamoto, Yoshio and Shin, Chan-Su and Spillner, Andreas and Wolff, Alexander},
  journal = {Discrete \& Computational Geometry},
  keywords = {gd-info1},
  number = 4,
  pages = {542–569},
  title = {Untangling a Planar Graph},
  volume = 42,
  year = 2009
}

Drawing Binary Tanglegrams: An Experimental Evaluation. Nöllenburg, Martin; Völker, Markus; Wolff, Alexander; Holten, Danny. In Proc. 11th Workshop Algorithm Engineering and Experiments (ALENEX’09), pp. 106–119. 2009.

[ BibTeX ]
[ slides ]
[ pdf ]

@inproceedings{nvwh-dbtee-09,
  author = {Nöllenburg, Martin and Völker, Markus and Wolff, Alexander and Holten, Danny},
  booktitle = {Proc. 11th Workshop Algorithm Engineering and Experiments (ALENEX'09)},
  keywords = {gd-info1},
  pages = {106–119},
  title = {Drawing Binary Tanglegrams: An Experimental Evaluation},
  year = 2009
}

Cover Contact Graphs. Atienza, Nieves; de Castro, Natalia; Cortés, Carmen; Garrido, M. Ángeles; Grima, Clara I.; Hernández, Gregorio; Márquez, Alberto; Moreno, Auxiliadora; Nöllenburg, Martin; Portillo, José Ramon; Reyes, Pedro; Valenzuela, Jesús; Villar, Maria Trinidad; Wolff, Alexander. In Proc. 15th Int. Sympos. Graph Drawing (GD’07), Vol. 4875 of Lecture Notes in Computer Science, S.-H. Hong, T. Nishizeki, W. Quan (eds.), pp. 171–182. Springer-Verlag, 2008.

[ BibTeX ]
[ pdf ]

@inproceedings{accgghmmnprvvw-ccg-08,
  author = {Atienza, Nieves and de Castro, Natalia and Cortés, Carmen and Garrido, M. Ángeles and Grima, Clara I. and Hernández, Gregorio and Márquez, Alberto and Moreno, Auxiliadora and Nöllenburg, Martin and Portillo, José Ramon and Reyes, Pedro and Valenzuela, Jesús and Villar, Maria Trinidad and Wolff, Alexander},
  booktitle = {Proc. 15th Int. Sympos. Graph Drawing (GD'07)},
  editor = {Hong, Seok-Hee and Nishizeki, Takao and Quan, Wu},
  keywords = {gd-info1},
  pages = {171–182},
  publisher = {Springer-Verlag},
  series = {Lecture Notes in Computer Science},
  title = {Cover Contact Graphs},
  volume = 4875,
  year = 2008
}

Straightening Drawings of Clustered Hierarchical Graphs. Bereg, Sergey; Völker, Markus; Wolff, Alexander; Zhang, Yuanyi. In Proc. 33rd Int. Conf. Current Trends Theory & Practice Comput. Sci. (SOFSEM’07), Vol. 4362 of Lecture Notes in Computer Science, J. van Leeuwen, G. F. Italiano, W. van der Hoek, C. Meinel, H. Sack, F. Plášil (eds.), pp. 177–186. Springer-Verlag, 2007.

[ BibTeX ]
[ pdf ]

@inproceedings{bvwz-sdchg-07,
  author = {Bereg, Sergey and Völker, Markus and Wolff, Alexander and Zhang, Yuanyi},
  booktitle = {Proc. 33rd Int. Conf. Current Trends Theory \& Practice Comput. Sci. (SOFSEM'07)},
  editor = {van Leeuwen, Jan and Italiano, Giuseppe F. and van der Hoek, Wiebe and Meinel, Christoph and Sack, Harald and Plášil, František},
  keywords = {gd-info1},
  pages = {177–186},
  publisher = {Springer-Verlag},
  series = {Lecture Notes in Computer Science},
  title = {Straightening Drawings of Clustered Hierarchical Graphs},
  volume = 4362,
  year = 2007
}

Drawing Subway Maps: A Survey. Wolff, Alexander. In Informatik – Forschung & Entwicklung, 22(1), pp. 23–44. 2007.

[ Abstract ]
[ BibTeX ]
[ pdf ]

This paper deals with automating the drawing of subway maps. There are two features of schematic subway maps that make them different from drawings of other networks such as flow charts or organigrams. First, most schematic subway maps use not only horizontal and vertical lines, but also diagonals. This gives more flexibility in the layout process, but it also makes the problem provably hard. Second, a subway map represents a network whose components have geographic locations that are roughly known to the users of such a map. This knowledge must be respected during the search for a clear layout of the network. For the sake of visual clarity the underlying geography may be distorted, but it must not be given up, otherwise map users will be hopelessly confused. In this paper we first give a rather generally accepted list of rules that should be adhered to by a good subway map. Next we survey three recent methods for drawing subway maps, analyze their performance with respect to the above rules, and compare the resulting maps among each other and to official subway maps drawn by graphic designers. We then focus on one of the methods, which is based on mixed-integer linear programming, a widely-used global optimization technique. This method guarantees to find a drawing that fulfills a subset of the above-mentioned rules (if such a drawing exists) and optimizes a weighted sum of costs that correspond to the remaining rules. The method can draw even large subway networks such as the London Underground in an aesthetically pleasing manner, similar to maps made by professional graphic designers. If station labels are included in the optimization process, so far only medium-size networks can be drawn. Finally we give evidence why drawing good subway maps is difficult (even without labels).

@article{w-dsms-07,
  abstract = {This paper deals with automating the drawing of subway maps. There are two features of schematic subway maps that make them different from drawings of other networks such as flow charts or organigrams. First, most schematic subway maps use not only horizontal and vertical lines, but also diagonals. This gives more flexibility in the layout process, but it also makes the problem provably hard. Second, a subway map represents a network whose components have geographic locations that are roughly known to the users of such a map. This knowledge must be respected during the search for a clear layout of the network. For the sake of visual clarity the underlying geography may be distorted, but it must not be given up, otherwise map users will be hopelessly confused. In this paper we first give a rather generally accepted list of rules that should be adhered to by a good subway map. Next we survey three recent methods for drawing subway maps, analyze their performance with respect to the above rules, and compare the resulting maps among each other and to official subway maps drawn by graphic designers. We then focus on one of the methods, which is based on mixed-integer linear programming, a widely-used global optimization technique. This method guarantees to find a drawing that fulfills a subset of the above-mentioned rules (if such a drawing exists) and optimizes a weighted sum of costs that correspond to the remaining rules. The method can draw even large subway networks such as the London Underground in an aesthetically pleasing manner, similar to maps made by professional graphic designers. If station labels are included in the optimization process, so far only medium-size networks can be drawn. Finally we give evidence why drawing good subway maps is difficult (even without labels).},
  author = {Wolff, Alexander},
  journal = {Informatik – Forschung \& Entwicklung},
  keywords = {gd-info1},
  number = 1,
  pages = {23–44},
  title = {Drawing Subway Maps: A Survey},
  volume = 22,
  year = 2007
}

Boundary Labeling: Models and Efficient Algorithms for Rectangular Maps. Bekos, Michael A.; Kaufmann, Michael; Symvonis, Antonios; Wolff, Alexander. In Computational Geometry: Theory and Applications, 36(3), pp. 215–236. 2007.

[ Abstract ]
[ BibTeX ]
[ pdf ]

In this paper, we present \emph{boundary labeling}, a new approach for labeling point sets with large labels. We first place disjoint labels around an axis-parallel rectangle that contains the point sites. Then, we connect each label to its site such that no two connections, so-called \emph{leaders}, intersect. Such an approach is common e.g. in technical drawings and medical atlases, but so far the problem has not been studied in the literature. The new problem is interesting in that it is a mixture of a label-placement and a graph-drawing problem. par We consider attaching labels to one, two or all four sides of the rectangle. We investigate rectilinear and straight-line leaders. We present simple and efficient algorithms that minimize the total length of the leaders or, in the case of rectilinear leaders, the total number of bends.

@article{bksw-blmea-07,
  abstract = {In this paper, we present \emph{boundary labeling}, a new approach for labeling point sets with large labels. We first place disjoint labels around an axis-parallel rectangle that contains the point sites. Then, we connect each label to its site such that no two connections, so-called \emph{leaders}, intersect. Such an approach is common e.g.\ in technical drawings and medical atlases, but so far the problem has not been studied in the literature. The new problem is interesting in that it is a mixture of a label-placement and a graph-drawing problem. \par We consider attaching labels to one, two or all four sides of the rectangle. We investigate rectilinear and straight-line leaders. We present simple and efficient algorithms that minimize the total length of the leaders or, in the case of rectilinear leaders, the total number of bends.},
  author = {Bekos, Michael A. and Kaufmann, Michael and Symvonis, Antonios and Wolff, Alexander},
  journal = {Computational Geometry: Theory and Applications},
  keywords = {gd-info1},
  number = 3,
  pages = {215–236},
  title = {Boundary Labeling: Models and Efficient Algorithms for Rectangular Maps},
  volume = 36,
  year = 2007
}

Minimizing Intra-Edge Crossings in Wiring Diagrams and Public Transport Maps. Benkert, Marc; Nöllenburg, Martin; Uno, Takeaki; Wolff, Alexander. In Proc. 14th Int. Sympos. Graph Drawing (GD’06), Vol. 4372 of Lecture Notes in Computer Science, M. Kaufmann, D. Wagner (eds.), pp. 270–281. Springer-Verlag, 2007.

[ BibTeX ]
[ pdf ]

@inproceedings{bnuw-miecw-07,
  author = {Benkert, Marc and Nöllenburg, Martin and Uno, Takeaki and Wolff, Alexander},
  booktitle = {Proc. 14th Int. Sympos. Graph Drawing (GD'06)},
  editor = {Kaufmann, Michael and Wagner, Dorothea},
  keywords = {gd-info1},
  pages = {270–281},
  publisher = {Springer-Verlag},
  series = {Lecture Notes in Computer Science},
  title = {Minimizing Intra-Edge Crossings in Wiring Diagrams and Public Transport Maps},
  volume = 4372,
  year = 2007
}

{Geometrische Netzwerke und ihre Visualisierung}. Wolff, Alexander. 2005, June.

[ BibTeX ]
[ pdf ]

@misc{w-gniv-05,
  author = {Wolff, Alexander},
  howpublished = {Habilitationsschrift (kumulativ), Fakultät für Informatik, Universität Karlsruhe},
  keywords = {gd-info1},
  month = {06},
  school = {Fakultät für Informatik, Universität Karlsruhe},
  title = {{Geometrische Netzwerke und ihre Visualisierung}},
  year = 2005
}

Readable Graph Drawing

Researchers

Publications

Data privacy protection

Data privacy protection

Picture credits