Incremental graph layout algorithm for interactive environments

Abstract

Most common and maybe the biggest limitation of graph layout algorithms today is their lack of incremental-layout ability. Whenever there is a change in the graph, these algorithms makes no references to current layout informations and whole layouting procedures is repeated again. This problem magnifies as informations to represent get large or the algorithm is used in interactive environment where frequent user-interactions occurs, where the changes in the graph caused by user interactions are relatively small to overall size of the graph representing relationship between informations. This thesis introduce an incremental graph layouting algorithm, variant of Sugiyama``s algorithm, that reduces layouting computations by generating fewer dummy vertices, having better vertex ordering functions, and most importantly the incremental layout ability which drastically reduces the layouting time.