# Graph Drawing with Low Visual Complexity

Algorithms for drawing graphs try to optimize (or give a guarantee) on certain formal quality measures. Typical measures include avoiding edge crossings, avoiding small angles between adjacent or crossing edges and minimizing the ratio between the largest and the smallest distance between any pair of points. Ideally, edges are represented by straight-line segments, but often also polygonal chains or circular arcs are used. When using polygonal chains, one usually tries to minimize the number of bends.

In this project, we want to examine a new conceptual design. The task is to draw a graph with a minimum number of geometric primitive. For example, we can draw a path in a graph as a single straight-line segment. The vertices are then only represented by crossings (or touching points) with other geometric elements. We call the number of used primitives the visual complexity of a drawing. We want to investigate how to create drawings with low visual complexity and find bounds for the required number. We want to answer this question for several classes of planar graphs, for example trees, series-parallel graphs, planar 3-trees and trangulations. As geometric primitive, we want to use mainly segments and circular arcs.

### Publications

- Experimental analysis of the accessibility of drawings with few segments. Philipp Kindermann, Wouter Meulemans and André Schulz. In Proceedings of the 25th International Symposium on Graph Drawing and Network Visualization (GD'17). To appear.
- On Gallai's conjecture for series-parallel graphs and planar 3-trees. Philipp Kindermann, Lena Schlipf and André Schulz. Arxiv report.
- Drawing Trees and Triangulations with Few Geometric Primitives. Gregor Hültenschmidt, Philipp Kindermann, Wouter Meulemans and André Schulz. In Proceedings of the 43rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG'17), To appear.
- Drawing Planar Cubic 3-Connected Graphs with Few Segments: Algorithms & Experiments. Alexander Igamberdiev, Wouter Meulemans and André Schulz. In Journal of Graph Algorithms and Applications, Vol. 21, Nr. 4, 2017, pp. 561-588
- Drawing Trees and Triangulations with Few Geometric Primitives. Gregor Hültenschmidt, Philipp Kindermann, Wouter Meulemans and André Schulz. In Proceedings of the 32nd European Workshop on Computational Geometry (EuroCG'16), pp. 55-58, Abstract
- Drawing Planar Cubic 3-Connected Graphs with Few Segments: Algorithms and Experiments. Alexander Igamberdiev, Wouter Meulemans and André Schulz. In Proceedings of the 23rd International Symposium on Graph Drawing and Network Visualization (GD'15), pp. 113-124
- Drawing Graphs with Few Arcs. André Schulz. In Journal of Graph Algorithms and Applications, Vol. 19, no. 1, 2015, pp. 393-412