
388 CHAPTER 12. FORCE-DIRECTED DRAWING ALGORITHMS
Barycenter-Draw
Input: G = (V, E); a partition V = V
0
∪ V
1
of V into a set V
0
of at least three
fixed vertices and a set V
1
of free vertices; a strictly convex polygon P with |V
0
|
vertices
Output: a posit ion p
v
for each vertex of V , such that the fixed vertices form a
convex polygon P .
1. Place each fixed vertex u ∈ V
0
at a vertex of P , and each free vertex at the
origin.
2. repeat
foreach free vertex v ∈ V
1
do
x
v
=
1
deg(v)
X
(u,v)∈E
x
u
y
v
=
1
deg(v)
X
(u,v)∈E
y
u
until x
v
and y
v
converge for all free vertices v.
Figure 12.3 Tutte’s barycentric method [Tut63]. Pseudo-code from [DETT99].
12.4 Graph Theoretic Dist anc es Approach ...