Information Technology Reference
In-Depth Information
u
2
u
0
u
1
v
0
v
1
v
2
v
3
u
3
Fig. 3.
A graph whose Fruchterman-
Reingold coordinates cannot be com-
puted by a radical computation tree.
Fig. 4.
A graph whose Kamada-Kawai
coordinates cannot be computed by a
radical computation tree.
Let
a>
0 be the distance from
v
0
to
v
1
(equal by symmetry to the distance from
v
2
to
v
3
)andlet
b>
0 be the distance from
v
1
to
v
2
. We can then express the sumofall
the forces at vertex
v
0
by the equation
2
a
+
b
=
2
a
5
+3
a
4
b
+
a
3
b
2
5
a
2
b
2
1
a
−
1
a
+
b
−
1
−
−
5
ab
−
F
0
=
a
2
−
,
2
a
3
+3
a
2
b
+
ab
2
and the sum of all the forces at vertex
v
1
by the equation
a
+
b
=
−
a
4
b
−
a
3
b
2
+
a
2
b
3
−
a
2
+
ab
4
−
ab
+
b
2
a
2
+
1
1
b
−
1
a
+
b
2
F
1
=
−
−
.
a
2
b
+
ab
2
In an equilibrium state we have
F
1
=
F
2
=0.Equivalently, the numerator
p
of
F
1
and
the numerator
q
of
F
2
are both zero, where
p
(
a, b
)=2
a
5
+3
a
4
b
+
a
3
b
2
5
a
2
b
2
=0
−
−
5
ab
−
a
4
b
a
3
b
2
+
a
2
b
3
a
2
+
ab
4
ab
+
b
2
=0
.
q
(
a, b
)=
−
−
−
−
To solve this system of two equations and two unknowns we can eliminate variable
a
and produce the following polynomial, shown as a product of irreducible polynomials,
whose roots give the values of
b
that lead to a solution.
1
3
b
2
(3
b
15
48
b
12
+ 336
b
9
1196
b
6
+ 1440
b
3
+ 144)
.
−
−
The factor
b
2
corresponds to degenerate drawings and may safely be eliminated. Let
f
be the degree-fifteen factor; then
f
(
x
)=
g
(
x
3
) for a quintic polynomial
g
. A radical
computation tree can compute the roots of
f
from the roots of
g
, so we need only show
that the roots of
g
cannot be computed in a radical computation tree. To do this, we
convert
g
to a monic polynomial
h
with the same splitting field, via the transformation
h
(
x
)=
x
5
144
g
(6
/x
)=
x
5
+60
x
4
299
x
3
+ 504
x
2
−
−
432
x
+ 162
.
The polynomial
h
canbeshowntobeirreducible by manually verifying that it has no
linear or quadratic factors. Its discriminant is
2
6
3
9
2341
2
2749,and
h
factors
modulo primes 5 and 7 (which do not divide the discriminant) into irreducibles:
−
·
·
·
(
x
+1)(
x
4
+3
x
3
+6
x
2
+
x
+1) (mod7)
h
(
x
)
≡
(
x
2
+3
x
+4)(
x
3
+2
x
2
+
x
+3) (mod5)
.
h
(
x
)
≡
