Information Technology Reference
In-Depth Information
Root Computation Trees. Consider the cycle C n with n vertices. When drawn with
force directed algorithms, either Fruchterman and Reingold or Kamada and Kawai, the
embedding typically places all vertices equally spaced on a circle, such that neighbors
are placed next to each other, as shown in Figure 2. As an easy warm-uptoourmain
results, we observe that this is not always possible using aquadratic computation tree.
Theorem 1. There exist agraphwith sevenvertices such thatitisnot possible ina
quadratic computation tree to compute the coordinates of every possible Fruchterman
andReingold equilibrium or every possible KamadaandKawaiequilibrium.
Proof. Let G be the cycle C 7 on seven vertices. Both algorithms have the embedding
shown in Figure 2 (suitably scaled) as an equilibrium. In this embedding let a and b be
two neighboring vertices and ʱ and ʲ their corresponding complex coordinates. Then
ʱ/ʲ is equal to
±
ʶ 7 the seventh root of unity. By Lemma 6
[ Q ( ʶ 7 ): Q ]= ˆ (7) = 6 .
Since 6 is not a power of two, Lemma 5 implies that ʶ 7 cannot be constructed by a
quadratic computation tree. Therefore, neither can this embedding.
Theorem 2. Fo r arbitrarily large values of n ,there are graphson n vertices such
thatconstructing the coordinates of all Fruchterman andReingold equilibria ona
root computation tree requires degree ʩ ( n 0 . 677 ) .Ifthere exists infinitely many Sophie
Germain primes, then there are graphsforwhich computing the coordinates of any
Fruchterman andReingold equilibria requires degree ʩ ( n ) .Thesameresults with the
same graphs hold for KamadaandKawaiequilibria.
Proof. As in the previous theorem we consider embedding cycles with their canonical
embedding, which is an equilibrium for both algorithms. The same argument used in
the previous theorem shows we can construct ʶ n from the coordinates of the canonical
embedding of the cycle on n vertices.
We consider cycles with p vertices where p is a prime number for which ˆ ( p )= p
1
has a large prime factor q . If arbitrarily large Sophie Germain primes exist we let q be
such a prime and let p =2 q +1. Otherwise, by Lemma 4 we choose p in such a way
that its largest prime factor q is at least p 0 . 677 .Now,byLemma6wehave:
[ Q ( ʶ p ): Q ]= ˆ ( p )= p − 1 .
This extension is not D -smooth for any D smaller than q , and therefore every construc-
tion of it on a root computation tree requires degree at least q .
Thus, such drawings are not possible on a bounded-degree root computation tree.
Radical Computation Trees. To show that the coordinates of a Fruchterman and
Reingold equilibriumareingeneral not computable with a radical computation tree
we consider embedding the path with three edges, shown in Figure 3. We assume
that all of the vertices are embedded colinearly and withoutedge or vertex overlaps.
These assumptions correspond to the equilibrium that is typically produced by the
Fruchterman and Reingold algorithm.
 
Search WWH ::




Custom Search