Visualizing graphs: optimization and trade-offs
| dc.contributor.author | Mondal, Debajyoti | |
| dc.contributor.examiningcommittee | Bose, Prosenjit (Computer Science) Praymak, Andriy (Mathematics) Wood, David (Mathematical Sciences) | en_US |
| dc.contributor.supervisor | Durocher, Stephane (Computer Science) | en_US |
| 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.degree.discipline | Computer Science | en_US |
| dc.degree.level | Doctor of Philosophy (Ph.D.) | en_US |
| 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.description.note | October 2016 | 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.language.iso | eng | 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.rights | open access | 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.type | doctoral thesis | en_US |