Deutsch Intern
Chair of Computer Science I - Algorithms and Complexity

Readable Graph Drawing

Graphs are not only a common tool for modelling and solving problems in computer science, but are also often used for visualizing data. Concrete drawings of graphs are understood also by non-experts; 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 well-readable drawings. That is because 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 but all with large crossing angles.

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 real-world data are, however, usually not planar. If such graphs are large, 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

Publications

  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • Drawing Subway Maps: A Survey. Wolff, Alexander. In Informatik -- Forschung & Entwicklung, 22(1), pp. 23–44. 2007.
  • 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. Plasil (eds.), pp. 177–186. Springer-Verlag, 2007.
  • Drawing Subway Maps: A Survey. Wolff, Alexander. In Informatik&nobsp;��� Forschung & Entwicklung, 22(1), pp. 23–44. 2007.
  • {Geometrische Netzwerke und ihre Visualisierung}. Wolff, Alexander. 2005, June.

To top