Visualization of clustered directed acyclic graphs with node interleaving

Graph drawing and visualization represent structural information as diagrams of abstract graphs and networks. An important subset of graphs is directed acyclic graphs (DAGs). E-Spring algorithm, extended from the popular spring embedder model, eliminates node overlaps in clustered DAGs by modeling nodes as charged particles whose repulsion is controlled by edges modeled as springs. The drawing process needs to reach a stable state when the average distances of separation between nodes are near optimal. This paper presents an enhancement to E-Spring to introduce a stopping condition, which reduces equilibrium distances between nodes and therefore results in a significantly reduced area for DAG visualization. It imposes an upper bound on the repulsive forces between nodes based on graph geometry. The algorithm employs node interleaving to eliminate any residual node overlaps. These new techniques have been validated by visualizing eBay buyer-seller relationships and resulted in overall area reductions in the range of 45% to 79%.