## 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 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 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 real-world 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
- Steven Chaplick
- Fabian Lipp
- Myroslav Kryven
- André Löffler
- Martin Fink (until 2014)
- Philipp Kindermann (until 2015)

## Publications

- Computing Storylines with Few Block Crossings. in Lecture Notes in Computer Science, F. Frati, Ma, K. -L. (eds.) (2018). (Vol. 10692) 365--378.
- Planar L-Drawings of Directed Graphs. in Lecture Notes in Computer Science, F. Frati, Ma, K. -L. (eds.) (2018). (Vol. 10692) 465--478.
- On the Maximum Crossing Number. in Journal of Graph Algorithms & Applications (2018). 22(1) 67--87.
- Beyond Outerplanarity. in Lecture Notes in Computer Science, F. Frati, Ma, K. -L. (eds.) (2018). (Vol. 10692) 546--559.
- Snapping Graph Drawings to the Grid Optimally. in Lecture Notes in Computer Science, Y. Hu, Nöllenburg, M. (eds.) (2016). (Vol. 9801) 144--151.
- Block Crossings in Storyline Visualizations. in Lecture Notes in Computer Science, Y. Hu, Nöllenburg, M. (eds.) (2016). (Vol. 9801) 382--398.
- Drawing Graphs on Few Lines and Few Planes. in Lecture Notes in Computer Science, Y. Hu, Nöllenburg, M. (eds.) (2016). (Vol. 9801) 166--180.
- Obstructing Visibilities with One Obstacle. in Lecture Notes in Computer Science, Y. Hu, Nöllenburg, M. (eds.) (2016). (Vol. 9801) 295--308.
- Faster Force-Directed Graph Drawing with the Well-Separated Pair Decomposition. in Lecture Notes in Computer Science, E. Di Giacomo, Lubiw, A. (eds.) (2015). (Vol. 9411) 52--59.
- Pixel and Voxel Representations of Graphs. in Lecture Notes in Computer Science, E. Di Giacomo, Lubiw, A. (eds.) (2015). (Vol. 9411) 472--486.
- Luatodonotes: Boundary Labeling for Annotations in Texts. in Lecture Notes in Computer Science, C. Duncan, Symvonis, A. (eds.) (2014). (Vol. 8871) 76--88.
- Drawing Graphs within Restricted Area. in Lecture Notes in Computer Science, C. Duncan, Symvonis, A. (eds.) (2014). (Vol. 8871) 367--379.
- Simultaneous Drawing of Planar Graphs with Right-Angle Crossings and Few Bends. in Lecture Notes in Computer Science, C. Duncan, Symvonis, A. (eds.) (2014). (Vol. 8871) 515--516.
- On Monotone Drawings of Trees. in Lecture Notes in Computer Science, C. Duncan, Symvonis, A. (eds.) (2014). (Vol. 8871) 488--500.
- Drawing (Complete) Binary Tanglegrams: Hardness, Approximation, Fixed-Parameter Tractability. in Algorithmica (2012). 62(1--2) 309--332.
- Drawing Graphs with Vertices at Specified Positions and Crossings at Large Angles. in Lecture Notes in Computer Science, M. van Kreveld, Speckmann, B. (eds.) (2012). (Vol. 7034) 441--442.
- Drawing Graphs with Vertices at Specified Positions and Crossings at Large Angles. in Lecture Notes in Computer Science, M. S. Rahman, Nakano, S. -ichi (eds.) (2012). (Vol. 7157) 186--197.
- Schematization in Cartography, Visualization, and Computational Geometry in Dagstuhl Seminar Proceedings (2011). (Vol. 10461) Schloss Dagstuhl.
- Drawing and Labeling High-Quality Metro Maps by Mixed-Integer Programming. in IEEE Transactions on Visualization and Computer Graphics (2011). 17(5) 626--641.
- Manhattan-Geodesic Embedding of Planar Graphs. in Lecture Notes in Computer Science, D. Eppstein, Gansner, E. R. (eds.) (2010). (Vol. 5849) 207--218.
- Drawing Binary Tanglegrams: An Experimental Evaluation. (2009). 106--119.
- Untangling a Planar Graph. in Discrete & Computational Geometry (2009). 42(4) 542--569.
- Cover Contact Graphs. in Lecture Notes in Computer Science, S. -H. Hong, Nishizeki, T., Quan, W. (eds.) (2008). (Vol. 4875) 171--182.
- Straightening Drawings of Clustered Hierarchical Graphs. in Lecture Notes in Computer Science, J. van Leeuwen, Italiano, G. F., van der Hoek, W., Meinel, C., Sack, H., Plasil, F. (eds.) (2007). (Vol. 4362) 177--186.
- Minimizing Intra-Edge Crossings in Wiring Diagrams and Public Transport Maps. in Lecture Notes in Computer Science, M. Kaufmann, Wagner, D. (eds.) (2007). (Vol. 4372) 270--281.
- Drawing Subway Maps: A Survey. in Informatik~-- Forschung & Entwicklung (2007). 22(1) 23--44.
- Boundary Labeling: Models and Efficient Algorithms for Rectangular Maps. in Computational Geometry: Theory and Applications (2007). 36(3) 215--236.
- Geometrische Netzwerke und ihre Visualisierung. (2005).
- A Simple Proof for the NP-Hardness of Edge Labeling. Technical Report (11/2000), (2000).