Graph visualization and its applications.

摘要

Graphs are abstract structures for modeling relational information. The goal of automatic graph drawing is to develop algorithms that compute a good drawing conforming to aesthetic criteria. Many practical applications have labeled nodes, which may cause overlaps in graph layouts. Removal of such node overlaps is very important to improve the readability of graphs. In addition, it is important to preserve a user's mental map of a drawing with dynamic graph drawing.;This dissertation presents E-Spring algorithm for node overlap removal in clustered directed acyclic graphs (DAGs) with finite length node labels. It is based on the popular spring embedder model, and introduces a theoretical approach using physical forces for considering overlaps. A mechanism that identifies nodes as parents or children was devised, and a force function based on weights of parent nodes eliminates node overlaps.;Enhancements to E-Spring algorithm include the automatic detection of a condition that should stop the animated drawing of graphs; and a method for node interleaving to eliminate residual overlap present in some regions of individual DAG clusters. The stop condition was based on minimization of average edge lengths for individual clusters, and inter-DAG cluster distances. This significantly reduces the overall graph area. Furthermore, E-Spring algorithm was extended to visualize general graphs without node overlaps. Tree structures were extracted, and a post-processing step that implements edge routing eliminates residual edge-node intersections in graph layouts.;Applications for graph visualization include the online eBay marketplace, and bibliography DBLP data that utilized web services technology to extract relevant data. Categorization of a new class of web services called the Executable Web was performed. For this class, the calculations occur behind the scenes of web query forms, and search engine spiders cannot access them. The definition of Hidden Web services was extended to include the existing Deep Web and the new Executable Web.