English Intern
Lehrstuhl für Informatik I - Algorithmen und Komplexität

Übersichtliches Zeichnen von Graphen

Graphen sind nicht nur ein häufiges Hilfsmittel beim Modellieren und Lösen von Problemen in der Informatik, sondern werden auch oft zur Visualisierung von Daten genutzt. Auch für Laien sind konkrete Zeichnungen von Graphen oft gut verständlich, da die Darstellung einer Verbindung oder eines Zusammenhangs durch Kanten intuitiv ist. Darüber hinaus lassen sich Methoden zum Zeichnen von Graphen auch oft für das Zeichnen realer Netzwerke, wie z.B. (U-)Bahnnetze, verwenden. Wir entwickeln und untersuchen Algorithmen für das übersichtliche Zeichnen von Graphen.

Es gibt auf dem Gebiet des Graphenzeichnens zwar schon viele beweisbar gute Algorithmen, die aber dennoch keine wirklich übersichtlichen Zeichnungen produzieren. Dies liegt daran, dass es meist schon schwer ist, nur ein gewünschtes Zielkriterium zu optimieren, wie z.B. die Anzahl der Knicke oder der Kreuzungen von Kanten. Dies führt dazu, dass andere Anforderungen an die Übersichtlichkeit einer Zeichnung nicht erfüllt werden, etwa weil die Kanten sehr lang sind oder einzelne Kanten sehr viele Knicke aufweisen. Es kann daher auch sinnvoll sein, Teilprobleme nicht optimal zu lösen, sondern gegeneinander abzuwägen. So kann eine Zeichnung besser lesbar werden, wenn es ein paar Kantenkreuzungen mehr gibt, dafür aber die Kreuzungswinkel sehr groß sind, wodurch die einzelne Kreuzung sehr viel übersichtlicher wird.

Die meisten existierenden Zeichenalgorithmen funktionieren außerdem nur auf planaren Graphen, d.h. Graphen, die sich ohne Überschneidungen zeichnen lassen. Gerade auf realen Daten basierende Graphen sind allerdings oft nicht planar. Haben solche Graphen eine gewisse Größe, was nicht ungewöhnlich ist, so sind in einer Zeichnung die einzelnen Knoten und Kanten ohnehin kaum unterscheidbar. Um die Graphen dennoch vernünftig darstellen zu können, existieren verschiedene Ansätze: man bündelt Gruppen von Kanten oder bildet Knotencluster. Es existiert jedoch noch kein Verfahren, das stets übersichtliche Zeichnungen liefert.

Projektmitarbeiter

Veröffentlichungen

  • 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, S. 50–68. 2019.
  • Drawing Graphs on Few Circles and Few Spheres. Kryven, Myroslav; Ravsky, Alexander; Wolff, Alexander. In Journal of Graph Algorithms & Applications, 23(2), S. 371–391. 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), Bd. 11904 von Lecture Notes in Computer Science, D. Archambault, C. D. T{ó}th (Hrsg.), S. 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), Bd. 11904 von Lecture Notes in Computer Science, D. Archambault, C. D. T{ó}th (Hrsg.), S. 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), Bd. 10692 von Lecture Notes in Computer Science, F. Frati, K.-L. Ma (Hrsg.), S. 365–378. 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), Bd. 11282 von Lecture Notes in Computer Science, T. Biedl, A. Kerren (Hrsg.), S. 137–151. 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), Bd. 10692 von Lecture Notes in Computer Science, F. Frati, K.-L. Ma (Hrsg.), S. 546–559. 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), Bd. 10692 von Lecture Notes in Computer Science, F. Frati, K.-L. Ma (Hrsg.), S. 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), Bd. 11282 von Lecture Notes in Computer Science, T. Biedl, A. Kerren (Hrsg.), S. 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), S. 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), Bd. 9801 von Lecture Notes in Computer Science, Y. Hu, M. N{ö}llenburg (Hrsg.), S. 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), Bd. 9801 von Lecture Notes in Computer Science, Y. Hu, M. N{ö}llenburg (Hrsg.), S. 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), Bd. 9801 von Lecture Notes in Computer Science, Y. Hu, M. N{ö}llenburg (Hrsg.), S. 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), Bd. 9411 von Lecture Notes in Computer Science, E. {Di Giacomo}, A. Lubiw (Hrsg.), S. 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), Bd. 9411 von Lecture Notes in Computer Science, E. {Di Giacomo}, A. Lubiw (Hrsg.), S. 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), Bd. 8871 von Lecture Notes in Computer Science, C. Duncan, A. Symvonis (Hrsg.), S. 76–88. 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), Bd. 8871 von Lecture Notes in Computer Science, C. Duncan, A. Symvonis (Hrsg.), S. 488–500. 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), Bd. 8871 von Lecture Notes in Computer Science, C. Duncan, A. Symvonis (Hrsg.), S. 367–379. 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), S. 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), Bd. 7157 von Lecture Notes in Computer Science, {Md. S. Rahman, {Shin- ichi} Nakano (Hrsg.), S. 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), S. 626–641. 2011.
  • Schematization in Cartography, Visualization, and Computational Geometry. Dykes, Jason; M{ü}ller-Hannemann, Matthias; Wolff, Alexander. In Bd. 10461 von 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), Bd. 5849 von Lecture Notes in Computer Science, D. Eppstein, E. R. Gansner (Hrsg.), S. 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), S. 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), S. 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), Bd. 4875 von Lecture Notes in Computer Science, S.-H. Hong, T. Nishizeki, W. Quan (Hrsg.), S. 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), S. 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), Bd. 4372 von Lecture Notes in Computer Science, M. Kaufmann, D. Wagner (Hrsg.), S. 270–281. Springer-Verlag, 2007.
  • Drawing Subway Maps: A Survey. Wolff, Alexander. In Informatik -- Forschung & Entwicklung, 22(1), S. 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), Bd. 4362 von Lecture Notes in Computer Science, J. van Leeuwen, G. F. Italiano, W. van der Hoek, C. Meinel, H. Sack, F. Plasil (Hrsg.), S. 177–186. Springer-Verlag, 2007.
  • Drawing Subway Maps: A Survey. Wolff, Alexander. In Informatik&nobsp;��� Forschung & Entwicklung, 22(1), S. 23–44. 2007.
  • {Geometrische Netzwerke und ihre Visualisierung}. Wolff, Alexander. 2005, Juni.