Home |
Articles | Chuong Trinh Xe Lan | | My Dad Dissertation | Contact 


Dynamic Graph Layout

Abstract

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 increases rapidly, 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 changes. 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 of 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 are proposed in this research. The goal of this research is to improve the performance and scalability of the constrained graph drawing framework while preserving layout stability. The primary innovation of the proposed constrained hierarchical graph drawing framework is to use a relational data model to improve the performance of the algorithm by reusing vertex and edge information stored in a relational database . This research is based on the work of North and Woodhull (2001) and the constrained crossing reduction problem proposed by Forster (2004). The result of the proposed constrained hierarchical graph drawing framework and the new Sugiyama heuristic, especially the modified barycenter algorithms, will be tested and evaluated against North and Woodhull’s (2001) Online Graph Drawing Framework.

Research

Approved iea paper
Formal proposal - latest version 9.3
The proposal is being written. This page is updated frequently

Advisors

  1. Dr. Laszlo, Michael (Main advisor)
  2. Dr. Sun, Junping
  3. Dr. Li, Wei

Sugiyama Pseudocode

Demo, Snapshots, and Source Code

  • Source code
    A html version of source code (being updated frequently)
  • GraphViewer
    A basic graph viewer (applet) - for visualization testing purposes (still underdevelopment). [Tested under linux/firefox 3.0]
  • Graph Snapshots
    These snapshots were taken from graph viewer showing the result of the graph after layer assignment algorithm is completed including adding dummy vertices to ensure the graph is propered before executing the one-side two-layered crossing heuristics.
  • DDL script of the graph database
    This data contains vertices, edges and series of snapshots of graph layout.

Extended Dot Grammar

Extended dot grammar includes following functions
  • Add vertices
  • Add edges
  • Remove vertices
  • Remove edges
  • Set vertice constraints
  • Set order constraints

Applications

Applications of this research include but not limited to enterprise process modeling tool, online family tree (redenring large tree) etc.

References

Resources


Linux CPU:AMD Opteron(tm) Processor 250 Memory:8007700 kB

Copyright (c) 2005