| Abstract |
In information technology, big data is a term used to describe data sets so large
and complex that they become awkward to work and analyze. Difficulties include
capture, storage, search, sharing, analysis, and visualization. In this work we focus
in the latter part, specifically we study the visualization of graphs. The need for
simple and intuitive visualization techniques is more imminent than ever.
In this thesis we propose a new framework for visualizing graphs. We extend
the so-called Dominance Drawing method, by relaxing some constraints in order
to include the much broader family of directed acyclic graphs. We introduce a new
computational problem called Weak Dominance Placement, which we prove NPcomplete
using notions from the field of Order Theory. We offer simple bounds and
properties as well as three heuristic algorithms in order to obtain locally optimal
solutions.
Using a weak dominance placement of the vertices, we propose a new graph
drawing model for visualizing directed acyclic graphs called Overloaded Orthogo-
nal. In order to simplify our drawings we use an overloading technique for edge
routing. All algorithms are simple and easy to implement and can be applied to
directed acyclic graphs of arbitrary degree, planar, and non-planar graphs. We also
present bounds on the number of bends and the layout area of a graph. Overloaded
Orthogonal drawings present several interesting properties such as efficient visual
edge confirmation as well as simplicity and clarity of the drawing.
Furthermore, we propose the DAGView framework which handles not only
directed acyclic graphs, but also graphs with cycles and undirected graphs. Our
approach combines the readability and scalability of a matrix based approach, with
the intuitiveness of a node-link approach in spotting a node within the layout and
in following an edge to find its destination. We have implemented the DAGView
framework in Java and the results are very encouraging. Finally, we believe that
DAGView visualizations will be well accepted in user studies, since several criteria
that users identified as important in a layout are met: underlying grid, crossings
that appear perpendicular, easy check for the existence of an edge and/or path,
preservation of the mental-map.
|
Dominance Drawing of Non-Planar Graphs
