Show simple item record

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) Wood, David (Mathematical Sciences) en_US
dc.degree.level Doctor of Philosophy (Ph.D.) en_US
dc.description.note October 2016 en_US


Files in this item

This item appears in the following Collection(s)

Show simple item record

View Statistics