Data in real-world graph drawing applications often change frequently but incrementally. Any drastic change in the graph layout could disrupt a user's "mental map." Furthermore, real-world applications like enterprise process or e-commerce graphing, where data change rapidly in both content and quantity, demand a comprehensive responsiveness when rendering the graph layout in a multi-user environment in real time. Most standard static graph drawing algorithms apply global changes and redraw the entire graph layout whenever the data change. The new layout may be very different from the previous layout and the time taken to redraw the entire graph degrades quickly as the amount of graph data grows. Dynamic behavior and the quantity of data generated by real-world applications pose challenges for existing graph drawing algorithms in terms of incremental stability and scalability.
A constrained hierarchical graph drawing framework and modified Sugiyama heuristic were developed in this research. The goal of this research was to improve the scalability of the constrained graph drawing framework while preserving layout stability. The framework's use of the relational data model shifts the graph application from the traditional desktop to a collaborative and distributed environment by reusing vertex and edge information stored in a relational database. This research was based on the work of North and Woodhull (2001) and the constrained crossing reduction problem proposed by Forster (2004). The result of the constrained hierarchical graph drawing framework and the new Sugiyama heuristic, especially the modified barycenter algorithms, were tested and evaluated against the Graphviz framework and North and Woodhull's (2001) online graph drawing framework.
The performance test results showed that the constrained graph drawing framework run time is comparable with the performance of the Graphviz framework in terms of generating static graph layouts, which is independent of database accesses. Decoupling graph visualization from the graph editing modules improved scalability, enabling the rendering of large graphs in real time. The visualization test also showed that the constrained framework satisfied the aesthetic criteria for constrained graph layouts. Future enhancements for this proposed framework include implementation of (1) the horizontal coordinate assignment algorithm, (2) drawing polylines for multilayer edges in the rendering module, and (3) displaying subgraphs for very large graph layouts.
|Advisor:||Laszlo, Michael J.|
|Commitee:||Li, Wei, Sun, Junping|
|School:||Nova Southeastern University|
|Department:||Computer Science (CISC, CISD)|
|School Location:||United States -- Florida|
|Source:||DAI-B 72/12, Dissertation Abstracts International|
|Keywords:||Crossing reduction, Graph layouts, Sugiyama heuristic|
Copyright in each Dissertation and Thesis is retained by the author. All Rights Reserved
The supplemental file or files you are about to download were provided to ProQuest by the author as part of a
dissertation or thesis. The supplemental files are provided "AS IS" without warranty. ProQuest is not responsible for the
content, format or impact on the supplemental file(s) on our system. in some cases, the file type may be unknown or
may be a .exe file. We recommend caution as you open such files.
Copyright of the original materials contained in the supplemental file is retained by the author and your access to the
supplemental files is subject to the ProQuest Terms and Conditions of use.
Depending on the size of the file(s) you are downloading, the system may take some time to download them. Please be