Readable Graph Drawing
Readable Graph Drawings
Graphs are not only a common tool for modelling ans solving problems in computer science, but are also often used for visualizing data. Concrete drawings of graphs are understood also by nonexperts; the representation of a link or a connection is intuitive. Moreover, methods for graph drawing can be used for visualizing real networks such as metro networks. We develop and investigate algorithms for creating readable drawings of graphs.
The literature describes many provably good algorithms for drawing graphs. Rarely, however, do these algorithms produce wellreadable drawings. That is beacause it is often already hard to optimize only one desired criterion such as the number of bends or the number of edge crossings. This leads to other readability requirements not being fulfilled, perhaps because some edges are very long or some have many bends. It can, therefore, also make sense to do without solving partial problems optimally and rather balance several criteria against each other. A drawing can, for example, become better readable if there are slightly more crossings that have, in contrast, very high crossing angles, which improves the readability of a single crossing a lot.
Most existing algorithms for graph drawing work, furthermore, only on planar graphs, that is, graphs that can be drawn without crossings. Especially graphs based on realworld data are, however, often not planar. If such graphs are big, which is not unusual, then single nodes or edges are hardly distinguishable in a drawing. There exist several approaches to draw such graphs: groups of edges are bundled or clusters of nodes are formed. So far, however, there is no method that always produces readable drawings.
Researchers
 Alexander Wolff
 Philipp Kindermann
 Jonathan Klawitter
 Oksana Firman
 Myroslav Kryven
 André Löffler
 Steven Chaplick (until 2020)
 Fabian Lipp (until 2018)
 Martin Fink (until 2014)
Publications

Computing OptimalHeight Tangles Faster. Firman, Oksana; Kindermann, Philipp; Ravsky, Alexander; Wolff, Alexander; Zink, Johannes in Lecture Notes in Computer Science, D. Archambault, C. D. Tóth (eds.) (2019). (Vol. 11904) 203–215.

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.

Stick Graphs with Length Constraints. Chaplick, Steven; Kindermann, Philipp; Löffler, Andre; Thiele, Florian; Wolff, Alexander; Zaft, Alexander; Zink, Johannes in Lecture Notes in Computer Science, D. Archambault, C. D. Tóth (eds.) (2019). (Vol. 11904) 3–17.

Compact Drawings of 1Planar Graphs with RightAngle Crossings and Few Bends. Chaplick, Steven; Lipp, Fabian; Wolff, Alexander; Zink, Johannes in Computational Geometry: Theory and Applications (2019). 84 50–68.

Beyond Outerplanarity. Chaplick, Steven; Kryven, Myroslav; Liotta, Giuseppe; Löffler, Andre; Wolff, Alexander in Lecture Notes in Computer Science, F. Frati, K.L. Ma (eds.) (2018). (Vol. 10692) 546–559.

Computing Storylines with Few Block Crossings. van Dijk, Thomas C.; Lipp, Fabian; Markfelder, Peter; Wolff, Alexander in Lecture Notes in Computer Science, F. Frati, K.L. Ma (eds.) (2018). (Vol. 10692) 365–378.

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.

Orthogonal and Smooth Orthogonal Layouts of 1Planar Graphs with Low Edge Complexity. Argyriou, Evmorfia; Cornelsen, Sabine; Förster, Henry; Kaufmann, Michael; Nöllenburg, Martin; Okamoto, Yoshio; Raftopoulou, Chrysanthi; Wolff, Alexander in Lecture Notes in Computer Science, T. Biedl, A. Kerren (eds.) (2018). (Vol. 11282) 509–523.[ BibTeX ]

Compact Drawings of 1Planar Graphs with RightAngle Crossings and Few Bends. Chaplick, Steven; Lipp, Fabian; Wolff, Alexander; Zink, Johannes in Lecture Notes in Computer Science, T. Biedl, A. Kerren (eds.) (2018). (Vol. 11282) 137–151.

Planar LDrawings of Directed Graphs. Chaplick, Steven; Chimani, Markus; Cornelsen, Sabine; Da Lozzo, Giordano; Nöllenburg, Martin; Patrignani, Maurizio; Tollis, Ioannis G.; Wolff, Alexander in Lecture Notes in Computer Science, F. Frati, K.L. Ma (eds.) (2018). (Vol. 10692) 465–478.

Obstructing Visibilities with One Obstacle. Chaplick, Steven; Lipp, Fabian; Park, Jiwon; Wolff, Alexander in Lecture Notes in Computer Science, Y. Hu, M. Nöllenburg (eds.) (2016). (Vol. 9801) 295–308.

Snapping Graph Drawings to the Grid Optimally. Löffler, Andre; van Dijk, Thomas C.; Wolff, Alexander in Lecture Notes in Computer Science, Y. Hu, M. Nöllenburg (eds.) (2016). (Vol. 9801) 144–151.

Drawing Graphs on Few Lines and Few Planes. Chaplick, Steven; Fleszar, Krzysztof; Lipp, Fabian; Ravsky, Alexander; Verbitsky, Oleg; Wolff, Alexander in Lecture Notes in Computer Science, Y. Hu, M. Nöllenburg (eds.) (2016). (Vol. 9801) 166–180.

Block Crossings in Storyline Visualizations. van Dijk, Thomas C.; Fink, Martin; Fischer, Norbert; Lipp, Fabian; Markfelder, Peter; Ravsky, Alexander; Suri, Subhash; Wolff, Alexander in Lecture Notes in Computer Science, Y. Hu, M. Nöllenburg (eds.) (2016). (Vol. 9801) 382–398.

Faster ForceDirected Graph Drawing with the WellSeparated Pair Decomposition. Lipp, Fabian; Wolff, ALexander; Zink, Johannes in Lecture Notes in Computer Science, E. Di Giacomo, A. Lubiw (eds.) (2015). (Vol. 9411) 52–59.

Pixel and Voxel Representations of Graphs. Alam, Md. Jawaherul; Bläsius, Thomas; Rutter, Ignaz; Ueckerdt, Torsten; Wolff, Alexander in Lecture Notes in Computer Science, E. Di Giacomo, A. Lubiw (eds.) (2015). (Vol. 9411) 472–486.

Drawing Graphs within Restricted Area. Aulbach, Maximilian; Fink, Martin; Schuhmann, Julian; Wolff, Alexander in Lecture Notes in Computer Science, C. Duncan, A. Symvonis (eds.) (2014). (Vol. 8871) 367–379.[ BibTeX ]

On Monotone Drawings of Trees. Kindermann, Philipp; Schulz, André; Spoerhase, Joachim; Wolff, Alexander in Lecture Notes in Computer Science, C. Duncan, A. Symvonis (eds.) (2014). (Vol. 8871) 488–500.

Simultaneous Drawing of Planar Graphs with RightAngle Crossings and Few Bends. Bekos, Michael A.; van Dijk, Thomas C.; Kindermann, Philipp; Wolff, Alexander in Lecture Notes in Computer Science, C. Duncan, A. Symvonis (eds.) (2014). (Vol. 8871) 515–516.

Luatodonotes: Boundary Labeling for Annotations in Texts. Kindermann, Philipp; Lipp, Fabian; Wolff, Alexander in Lecture Notes in Computer Science, C. Duncan, A. Symvonis (eds.) (2014). (Vol. 8871) 76–88.[ BibTeX ]

Drawing Graphs with Vertices at Specified Positions and Crossings at Large Angles. Fink, Martin; Haunert, JanHenrik; Mchedlidze, Tamara; Spoerhase, Joachim; Wolff, Alexander in Lecture Notes in Computer Science, M. S. Rahman, S. ichi Nakano (eds.) (2012). (Vol. 7157) 186–197.

Drawing (Complete) Binary Tanglegrams: Hardness, Approximation, FixedParameter Tractability. Buchin, Kevin; Buchin, Maike; Byrka, Jaroslaw; Nöllenburg, Martin; Okamoto, Yoshio; Silveira, Rodrigo I.; Wolff, Alexander in Algorithmica (2012). 62(12) 309–332.

Drawing Graphs with Vertices at Specified Positions and Crossings at Large Angles. Fink, Martin; Haunert, JanHenrik; Mchedlidze, Tamara; Spoerhase, Joachim; Wolff, Alexander in Lecture Notes in Computer Science, M. van Kreveld, B. Speckmann (eds.) (2012). (Vol. 7034) 441–442.

Schematization in Cartography, Visualization, and Computational Geometry Dykes, Jason; MüllerHannemann, Matthias; Wolff, Alexander in Dagstuhl Seminar Proceedings (2011). (Vol. 10461) Schloss Dagstuhl~ LeibnizZentrum für Informatik.

Drawing and Labeling HighQuality Metro Maps by MixedInteger Programming. Nöllenburg, Martin; Wolff, Alexander in IEEE Transactions on Visualization and Computer Graphics (2011). 17(5) 626–641.

ManhattanGeodesic Embedding of Planar Graphs. Katz, Bastian; Krug, Marcus; Rutter, Ignaz; Wolff, Alexander in Lecture Notes in Computer Science, D. Eppstein, E. R. Gansner (eds.) (2010). (Vol. 5849) 207–218.

Drawing Binary Tanglegrams: An Experimental Evaluation. Nöllenburg, Martin; Völker, Markus; Wolff, Alexander; Holten, Danny (2009). 106–119.

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

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 Lecture Notes in Computer Science, S.H. Hong, T. Nishizeki, W. Quan (eds.) (2008). (Vol. 4875) 171–182.

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

Minimizing IntraEdge Crossings in Wiring Diagrams and Public Transport Maps. Benkert, Marc; Nöllenburg, Martin; Uno, Takeaki; Wolff, Alexander in Lecture Notes in Computer Science, M. Kaufmann, D. Wagner (eds.) (2007). (Vol. 4372) 270–281.

Straightening Drawings of Clustered Hierarchical Graphs. Bereg, Sergey; Völker, Markus; Wolff, Alexander; Zhang, Yuanyi in 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.

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.

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

A Simple Proof for the NPHardness of Edge Labeling. Technical Report (11/2000), Wolff, Alexander (2000).