Home

# Visualizing graphs: optimization and trade-offs

 dc.contributor.supervisor Durocher, Stephane (Computer Science) en_US dc.contributor.author Mondal, Debajyoti dc.date.accessioned 2016-09-12T15:43:33Z dc.date.available 2016-09-12T15:43:33Z dc.date.issued 2014-08 en_US dc.date.issued 2014-09 en_US dc.date.issued 2014-09 en_US dc.date.issued 2016-07 en_US dc.date.issued 2016-08 en_US dc.identifier.citation Twenty-Sixth Canadian Conference on Computational Geometry (CCCG), Halifax, Canada en_US dc.identifier.citation Twenty-Second International Symposium on Graph Drawing (GD), Wuerzburg, Germany en_US dc.identifier.citation Twenty-Second International Symposium on Graph Drawing (GD), Wuerzburg, Germany en_US dc.identifier.citation Forty-Third International Colloquium on Automata, Languages and Programming (ICALP), Rome, Italy en_US dc.identifier.citation Twenty-Eighth Canadian Conference on Computational Geometry (CCCG), Vancouver, Canada en_US dc.identifier.uri http://hdl.handle.net/1993/31673 dc.description.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. en_US dc.publisher CCCG en_US dc.publisher Springer en_US dc.publisher Springer en_US dc.publisher Leibniz Center for Informatics en_US dc.publisher CCCG en_US dc.subject Graph Drawing en_US dc.subject Algorithms en_US dc.subject Planar Graph en_US dc.subject Graph Thickness en_US dc.subject Complete Graph en_US dc.subject Polyline Drawing en_US dc.subject Trade-offs en_US dc.title Visualizing graphs: optimization and trade-offs en_US dc.degree.discipline Computer Science en_US dc.contributor.examiningcommittee Bose, Prosenjit (Computer Science) Praymak, Andriy (Mathematics) en_US Wood, David (Mathematical Sciences) dc.degree.level Doctor of Philosophy (Ph.D.) en_US dc.description.note October 2016 en_US
﻿