Information Technology Reference
In-Depth Information
proximity and the angle between them. This is implemented by viewing edges as Bezier
curves with 1 control point. The bowing force is exerted on the control points of two
edges sharing a common node and is constructed by the current distance between the
control points and the angle formed by the shared node and the location of each control
point. Specifically, we compute a force that 2 control points will exert on each other as
F
=
c/
(
r
a
d
b
)
,
where
r
is the angle of the control points and their shared node and
d
is the distance
between the two control points. In our case, we found that the values,
c
=
.
5 and
b
=2,
worked well, with
r
=1
.
5 initially.
This force is applied in the
x
-and
y
-directions, leading the two control points away
from each other and in the positive
z
-direction on both. It is then reduced so that the
xy
-
force is perpendicular to the original straight line edgebeforeanycurve bowing force
is applied. The control points are then pulled back to their original, unmoved location
laying on the
xy
-plane by a spring force with power proportional to how far away the
control point currently is from its origin. The spring force for a direction (
x
in this case)
is given by
·
−
Fx
=
kFx,
where
k
=
.
5.
When edges intersect, as detected by an orientation algorithm [1], we repel their
control points in the
z
-direction only. This lifts up the higher edge and lowers the other.
The magnitude of the force exerted on each control point is based on their distance in
the
xy
-plane.
In the initial state, where all edges are lying on the
xy
-plane and have a
z
-valueof0,
we exert a force to only one of the edges (at random), leaving the other edge still on the
xy
-plane.
3Con lu ion
We have observed that by adding another dimension to a graph drawing and allowing
control points to enter this new dimension with forces that cause edges to bow outof
the plane in a fashion dictated by intersections, angles, and proximity, we can improve
the angular resolution of the graph as a whole. For almost all cases, using additional
forces will provide better angular resolutionthanifwewereinthe
xy
-plane alone.
References
1. Battista, G.D., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing:Algorithms for the Visu-
alization of Graphs (1998)
2. Chernobelskiy, R., Cunningham, K.I., Goodrich, M.T., Kobourov, S.G., Trott, L.: Force-
directed lombardi-style graph drawing. In: Speckmann, B. (ed.) GD 2011. LNCS, vol. 7034,
pp. 320-331. Springer, Heidelberg (2011)
3. Fruchterman, T.M.J., Reingold, E.M.: Graph drawing by force-directed placement. Software:
Practice and Experience 21(11), 1129-1164 (1991), doi:10.1002/spe.4380211102
4. Goodrich, M.T., Pszona, P.: Achievinggood angular resolution in 3D arc diagrams. In: Wis-
math, S., Wolff, A. (eds.) GD 2013. LNCS, vol. 8242, pp. 161-172. Springer, Heidelberg
(2013)
