Visualizing graphs: optimization and trade-offs
Loading...
Date
2014-08, 2014-09, 2014-09, 2016-07, 2016-08
Authors
Mondal, Debajyoti
Journal Title
Journal ISSN
Volume Title
Publisher
CCCG
Springer
Springer
Leibniz Center for Informatics
CCCG
Springer
Springer
Leibniz Center for Informatics
CCCG
Abstract
Effective visualization of graphs is a powerful tool to help understand the relationships among the graph's underlying objects and to interact with them. Several styles for drawing graphs have emerged over the last three decades. Polyline drawing is a widely used style for drawing graphs, where each node is mapped to a distinct point in the plane and each edge is mapped to a polygonal chain between their corresponding nodes. Some common optimization criteria for such a drawing are defined in terms of area requirement, number of bends per edge, angular resolution, number of distinct line segments, edge crossings, and number of planar layers. In this thesis we develop algorithms for drawing graphs that optimize different aesthetic qualities of the drawing. Our algorithms seek to simultaneously optimize multiple drawing aesthetics, reveal potential trade-offs among them, and improve many previous graph drawing algorithms. We start by exploring probable trade-offs in the context of planar graphs. We prove that every $n$-vertex planar triangulation $G$ with maximum degree $\Delta$ can be drawn with at most $2n+t-3$ segments and $O(8^t \cdot \Delta^{2t})$ area, where $t$ is the number of leaves in a Schnyder tree of $G$. We then show that one can improve the area by allowing the edges to have bends. Since compact drawings often suffer from bad angular resolution, we seek to compute polyline drawings with better angular resolution. We develop a polyline drawing algorithm that is simple and intuitive, yet implies significant improvement over known results. At this point we move our attention to drawing nonplanar graphs. We prove that every thickness-$t$ graph can be drawn on $t$ planar layers with $\min\{O(2^{t/2} \cdot n^{1-1/\beta}), 2.25n +O(1)\}$ bends per edge, where $\beta = 2^{\lceil (t-2)/2 \rceil }$. Previously, the bend complexity, i.e., the number of bends per edge, was not known to be sublinear for $t>2$. We then examine the case when the number of available layers is restricted. The layers may now contain edge crossings. We develop a technique to draw complete graphs on two layers, which improves previous upper bounds on the number of edge crossings in such drawings.
Description
Keywords
Graph Drawing, Algorithms, Planar Graph, Graph Thickness, Complete Graph, Polyline Drawing, Trade-offs
Citation
Twenty-Sixth Canadian Conference on Computational Geometry (CCCG), Halifax, Canada
Twenty-Second International Symposium on Graph Drawing (GD), Wuerzburg, Germany
Twenty-Second International Symposium on Graph Drawing (GD), Wuerzburg, Germany
Forty-Third International Colloquium on Automata, Languages and Programming (ICALP), Rome, Italy
Twenty-Eighth Canadian Conference on Computational Geometry (CCCG), Vancouver, Canada
Twenty-Second International Symposium on Graph Drawing (GD), Wuerzburg, Germany
Twenty-Second International Symposium on Graph Drawing (GD), Wuerzburg, Germany
Forty-Third International Colloquium on Automata, Languages and Programming (ICALP), Rome, Italy
Twenty-Eighth Canadian Conference on Computational Geometry (CCCG), Vancouver, Canada