Information Technology Reference
In-Depth Information
Force-Directed 3D Arc Diagrams
Michael J. Bannister, Michael T. Goodrich, and Peter Sampson
University of California, Irvine, USA
Abstract.
We discuss a force-directed algorithm for constructing 3D arc dia-
grams. We introduce forces that allow curves in a 2D force directed graph to bow
out and away from each other in the third dimension in order to achieve better
angular resolution.
1
Introduction
In a 2D
arc diagram
1
,agraph is drawn by placing its vertices on a line and drawing
its edges as circular arcs. Goodrich and Pszona [4] extend this definition to 3D arc
diagrams, where vertices are placed in the
xy
-plane and edges are drawn as circular
arcs that may bow out of that plane in the third dimension, and they show how to use
graph coloring methods to determine tangent angles. Their approach works well for
some types of graphs, but not all. In this poster, we present a general force-directed
method for constructing a3Darcdiagram for any graph.
2
Our Algorithm
We start with a 2D force-directed layoutproduced with Fruchterman-Reingold [3]
forces, that is, where all vertices repel each other based on electromagnetic forces and
vertices connected by an edge are attracted to each other by a force that views the edge
as a spring. Vertex placements are refined iteratively, where each iteration brings the 2D
graph closer to a low energy state where nodes are experiencing the same forces in ev-
ery direction. Our implementation starts with the standard 2D forces, without any kind
of distortion, allowing vertices to move freely. Thus, in the
xy
-plane, all vertices ex-
ert a force inversely related to their distance, similar to an electromagnetic force, which
tends to push away vertices that are not related to each other. Vertices that share an edge
are pulled toward each other with a spring force, positively related to their distance, so
that nodes that are related can be closer spatially. These two forces are tempered by
a cooling function that gradually reduces the impact of the forces to avoid any case
where nodes are pulled forward and backward indefinitely. This phase of the algorithm
is similar to the first phase in the “dummy node” approach of Chemobelskiy
et al.
[2]
for force-directed Lombardi drawings.
After a small number of iterations, ouralgorithm enters its second phase, where
we allow intersecting edges to “pop” outofthe
xy
-plane. We also allow edges that
share common node to bow away from each other in the third dimension, based on their
1
