Graph Drawing

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), Lecture Notes in Computer Science, D. Archambault, C. D. T{’o}th (eds.) (2019). (Vol. 11904) 203–215.

[ 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{\'o}th, Csaba D.},
  keywords = {myown},
  pages = {203–215},
  publisher = {Springer-Verlag},
  series = {Lecture Notes in Computer Science},
  title = {Computing Optimal-Height Tangles Faster},
  volume = 11904,
  year = 2019
}

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 (2019). 84 50–68.

[ 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 = {myown},
  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
}

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

[ BibTeX ]
[ slides ]

@inproceedings{ckltwzz-sglc-GD19,
  author = {Chaplick, Steven and Kindermann, Philipp and L{\"o}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{\'o}th, Csaba D.},
  keywords = {myown},
  pages = {3–17},
  publisher = {Springer-Verlag},
  series = {Lecture Notes in Computer Science},
  title = {Stick Graphs with Length Constraints},
  volume = 11904,
  year = 2019
}

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

[ 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 = {myown},
  number = 2,
  pages = {371–391},
  title = {Drawing Graphs on Few Circles and Few Spheres},
  volume = 23,
  year = 2019
}

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

[ BibTeX ]

@inproceedings{acfknorw-osol1-GD18,
  author = {Argyriou, Evmorfia and Cornelsen, Sabine and F{\"o}rster, Henry and Kaufmann, Michael and N{\"o}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 = {myown},
  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
}

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), Lecture Notes in Computer Science, F. Frati, K.-L. Ma (eds.) (2018). (Vol. 10692) 365–378.

[ 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 = {myown},
  pages = {365–378},
  publisher = {Springer-Verlag},
  series = {Lecture Notes in Computer Science},
  title = {Computing Storylines with Few Block Crossings},
  volume = 10692,
  year = 2018
}

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

[ BibTeX ]
[ slides ]

@inproceedings{cccdnptw-plddg-GD17,
  author = {Chaplick, Steven and Chimani, Markus and Cornelsen, Sabine and {Da Lozzo}, Giordano and N{\"o}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 = {myown},
  pages = {465–478},
  publisher = {Springer-Verlag},
  series = {Lecture Notes in Computer Science},
  title = {Planar L-Drawings of Directed Graphs},
  volume = 10692,
  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), Lecture Notes in Computer Science, T. Biedl, A. Kerren (eds.) (2018). (Vol. 11282) 137–151.

[ 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 = {myown},
  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
}

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

[ BibTeX ]
[ slides ]

@inproceedings{ckllw-bo-GD17,
  author = {Chaplick, Steven and Kryven, Myroslav and Liotta, Giuseppe and L{\"o}ffler, Andre and Wolff, Alexander},
  booktitle = {Proc. 25th Int. Symp. Graph Drawing \& Network Vis. (GD'17)},
  editor = {Frati, Fabrizio and Ma, Kwan-Liu},
  keywords = {myown},
  pages = {546–559},
  publisher = {Springer-Verlag},
  series = {Lecture Notes in Computer Science},
  title = {Beyond Outerplanarity},
  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 (2018). 22(1) 67–87.

[ 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 = {myown},
  note = {Special issue on ``Graph Drawing Beyond Planarity''.},
  number = 1,
  pages = {67–87},
  title = {On the Maximum Crossing Number},
  volume = 22,
  year = 2018
}

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), Lecture Notes in Computer Science, Y. Hu, M. N{"o}llenburg (eds.) (2016). (Vol. 9801) 295–308.

[ 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{\"o}llenburg, Martin},
  keywords = {myown},
  pages = {295–308},
  publisher = {Springer-Verlag},
  series = {Lecture Notes in Computer Science},
  title = {Obstructing Visibilities with One Obstacle},
  volume = 9801,
  year = 2016
}

Drawing Graphs on Few Lines and Few Planes Chaplick, Steven; Fleszar, Krzysztof; Lipp, Fabian; Ravsky, Alexander; Verbitsky, Oleg; Wolff, Alexander in Proc. 24th Int. Symp. Graph Drawing & Network Vis. (GD’16), Lecture Notes in Computer Science, Y. Hu, M. N{"o}llenburg (eds.) (2016). (Vol. 9801) 166–180.

[ BibTeX ]
[ slides ]

@inproceedings{cflrvw-dgflf-GD16,
  author = {Chaplick, Steven and Fleszar, Krzysztof and Lipp, Fabian and Ravsky, Alexander and Verbitsky, Oleg and Wolff, Alexander},
  booktitle = {Proc. 24th Int. Symp. Graph Drawing \& Network Vis. (GD'16)},
  editor = {Hu, Yifan and N{\"o}llenburg, Martin},
  keywords = {myown},
  pages = {166–180},
  publisher = {Springer-Verlag},
  series = {Lecture Notes in Computer Science},
  title = {Drawing Graphs on Few Lines and Few Planes},
  volume = 9801,
  year = 2016
}

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

[ BibTeX ]
[ slides ]

@inproceedings{ldw-sgdgo-GD16,
  author = {L{\"o}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{\"o}llenburg, Martin},
  keywords = {myown},
  pages = {144–151},
  publisher = {Springer-Verlag},
  series = {Lecture Notes in Computer Science},
  title = {Snapping Graph Drawings to the Grid Optimally},
  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), Lecture Notes in Computer Science, Y. Hu, M. N{"o}llenburg (eds.) (2016). (Vol. 9801) 382–398.

[ 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{\"o}llenburg, Martin},
  keywords = {myown},
  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), Lecture Notes in Computer Science, E. {Di Giacomo}, A. Lubiw (eds.) (2015). (Vol. 9411) 52–59.

[ 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 = {myown},
  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{"a}sius, Thomas; Rutter, Ignaz; Ueckerdt, Torsten; Wolff, Alexander in Proc. 23rd Int. Symp. Graph Drawing & Network Vis. (GD’15), Lecture Notes in Computer Science, E. {Di Giacomo}, A. Lubiw (eds.) (2015). (Vol. 9411) 472–486.

[ BibTeX ]
[ slides ]
[ pdf ]

@inproceedings{abruw-pvrg-GD15,
  author = {Alam, Md. Jawaherul and Bl{\"a}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 = {myown},
  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), Lecture Notes in Computer Science, C. Duncan, A. Symvonis (eds.) (2014). (Vol. 8871) 367–379.

[ 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 = {myown},
  pages = {367–379},
  publisher = {Springer-Verlag},
  series = {Lecture Notes in Computer Science},
  title = {Drawing Graphs within Restricted Area},
  volume = 8871,
  year = 2014
}

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

[ BibTeX ]
[ pdf ]

@inproceedings{kssw-mdt-GD14,
  author = {Kindermann, Philipp and Schulz, Andr{\'e} and Spoerhase, Joachim and Wolff, Alexander},
  booktitle = {Proc. 22nd Int. Sympos. Graph Drawing (GD'14)},
  editor = {Duncan, Christian and Symvonis, Antonios},
  keywords = {myown},
  pages = {488–500},
  publisher = {Springer-Verlag},
  series = {Lecture Notes in Computer Science},
  title = {On Monotone Drawings of Trees},
  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), Lecture Notes in Computer Science, C. Duncan, A. Symvonis (eds.) (2014). (Vol. 8871) 76–88.

[ 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 = {myown},
  pages = {76–88},
  publisher = {Springer-Verlag},
  series = {Lecture Notes in Computer Science},
  title = {Luatodonotes: Boundary Labeling for Annotations in Texts},
  volume = 8871,
  year = 2014
}

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

[ 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\"ollenburg, Martin and Okamoto, Yoshio and Silveira, Rodrigo I. and Wolff, Alexander},
  journal = {Algorithmica},
  keywords = {myown},
  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), Lecture Notes in Computer Science, {Md. S. Rahman, {Shin- ichi} Nakano (eds.) (2012). (Vol. 7157) 186–197.

[ 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 = {myown},
  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
}

Schematization in Cartography, Visualization, and Computational Geometry Dykes, Jason; M{"u}ller-Hannemann, Matthias; Wolff, Alexander in Dagstuhl Seminar Proceedings (2011). (Vol. 10461) Schloss Dagstuhl~-- Leibniz-Zentrum f{"u}r Informatik.

[ BibTeX ]
[ URL ]

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

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

[ 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{\"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
}

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

[ 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 = {myown},
  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{’i}l, Jan; Okamoto, Yoshio; Shin, Chan-Su; Spillner, Andreas; Wolff, Alexander in Discrete & Computational Geometry (2009). 42(4) 542–569.

[ 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{\'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
}

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

[ BibTeX ]
[ slides ]
[ pdf ]

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

Cover Contact Graphs Atienza, Nieves; de Castro, Natalia; Cort\’{e}s, Carmen; Garrido, M. {’A}ngeles; Grima, Clara I.; Hern\’{a}ndez, Gregorio; M\’{a}rquez, Alberto; Moreno, Auxiliadora; N\"{o}llenburg, Martin; Portillo, Jos{’e} Ramon; Reyes, Pedro; Valenzuela, Jes\’{u}s; Villar, Maria Trinidad; Wolff, Alexander in Proc. 15th Int. Sympos. Graph Drawing (GD’07), Lecture Notes in Computer Science, S.-H. Hong, T. Nishizeki, W. Quan (eds.) (2008). (Vol. 4875) 171–182.

[ BibTeX ]
[ pdf ]

@inproceedings{accgghmmnprvvw-ccg-08,
  author = {Atienza, Nieves and de Castro, Natalia and Cort\'{e}s, Carmen and Garrido, M. {\'A}ngeles and Grima, Clara I. and Hern\'{a}ndez, Gregorio and M\'{a}rquez, Alberto and Moreno, Auxiliadora and N\"{o}llenburg, Martin and Portillo, Jos{\'e} Ramon and Reyes, Pedro and Valenzuela, Jes\'{u}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 = {myown},
  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{"o}lker, Markus; Wolff, Alexander; Zhang, Yuanyi in Proc. 33rd Int. Conf. Current Trends Theory & Practice Comput. Sci. (SOFSEM’07), Lecture Notes in Computer Science, J. van Leeuwen, G. F. Italiano, W. van der Hoek, C. Meinel, H. Sack, F. Plasil (eds.) (2007). (Vol. 4362) 177–186.

[ BibTeX ]
[ pdf ]

@inproceedings{bvwz-sdchg-07,
  author = {Bereg, Sergey and V{\"o}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 Plasil, Frantisek},
  keywords = {myown},
  pages = {177–186},
  publisher = {Springer-Verlag},
  series = {Lecture Notes in Computer Science},
  title = {Straightening Drawings of Clustered Hierarchical Graphs},
  volume = 4362,
  year = 2007
}

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

[ BibTeX ]
[ pdf ]

@inproceedings{bnuw-miecw-07,
  author = {Benkert, Marc and N{\"o}llenburg, Martin and Uno, Takeaki and Wolff, Alexander},
  booktitle = {Proc. 14th Int. Sympos. Graph Drawing (GD'06)},
  editor = {Kaufmann, Michael and Wagner, Dorothea},
  keywords = {myown},
  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
}

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

[ 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 = {subway_map},
  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 (2007). 36(3) 215–236.

[ 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 = {straight-line_leaders},
  number = 3,
  pages = {215–236},
  title = {Boundary Labeling: Models and Efficient Algorithms for Rectangular Maps},
  volume = 36,
  year = 2007
}

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

[ BibTeX ]
[ pdf ]

@misc{w-gniv-05,
  author = {Wolff, Alexander},
  howpublished = {Habilitationsschrift (kumulativ), Fakult{\"a}t f{\"u}r Informatik, Universit{\"a}t Karlsruhe},
  keywords = {myown},
  month = {jun},
  school = {Fakult{\"a}t f{\"u}r Informatik, Universit{\"a}t Karlsruhe},
  title = {{Geometrische Netzwerke und ihre Visualisierung}},
  year = 2005
}

Readable Graph Drawing

Researchers

Publications

Data privacy protection

Data privacy protection

Picture credits