Information Technology Reference
In-Depth Information
By Dedekind's theorem, the factorization modulo 7 implies the existence of a 4-cycle in
Gal(split(
h
)
/
Q
), and the factorization modulo 5 implies the existence of a permutation
that is the composition of a transposition and a 3-cycle. Raising the second permutation
to the power 3 yields a transposition. By Lemma 9, Gal(split(
h
)
/
Q
)=
S
5
.Soby
Lemma 7 the valueof
b
cannot be computed by a radical computation tree. Thus, we
cannot compute the equilibrium coordinates of the path with three edges under the
assumptions that the vertices are collinear and there are no vertex or edge overlaps.
Theorem 3.
There exists agraph on four vertices such thatitisnot possible ona
radicalcomputation tree to construct the coordinates of every possible Fruchterman
andReingold equilibrium.
To show that the coordinates of a Kamada and Kawai equilibriumareingeneral not
computable with a radical computation tree we consider the graph depicted in Figure 4.
Theorem 4.
There exists agraph on four vertices such thatitisnot possible ona
radicalcomputation tree to construct the coordinates of every possible Kamadaand
Kawaiequilibrium.
Proof.
See the full version of the paper.
4
Impossibility Results for Spectral Graph Drawing
Root computation trees.
We b egin with the following result for root computation trees.
Theorem 5.
Fo r arbitrarily large values of
n
,there are graphson
n
vertices such
thatconstructing spectral graph drawingsbased on the adjacency,Laplacian,relaxed
Laplacian,ortransitionmatrix requires a root computation tree of degree
ʩ
(
n
0
.
677
)
.
If there exist infinitely many Sophie Germain primes, then there are graphsforwhich
computing these drawingsrequires degree
ʩ
(
n
)
.
Proof.
Since all of the referenced matrices have rational entries, it suffices to consider
the computability of their eigenvalues. Further, if we restrict our attention to regular
graphs it suffices to consider the eigenvalues of just the adjacency matrix,
M
=adj(
G
),
by Lemma 1. Let
p
beaprimeand
G
the cycle on
p
vertices. By Lemma 2 the eigenval-
ues of
A
=adj(
G
) are given by 2cos(2
ˀk/p
) for 0
1. In a root computation
tree of degree at least 2 the primitive root of unity
ʶ
p
=exp(2
iˀ/p
) can be computed
from 2cos(2
ˀk/p
) for all
k
≤
k
≤
p
−
=0. Therefore, from the proof of Theorem 2, for arbitrarily
large
n
,therearegraphs on
n
vertices such that
M
has one rational eigenvector (for
k
=0) and the computation of any other eigenvector on a root computation tree requires
degree
ʩ
(
n
0
.
667
). If infinitely many Sophie Germain primes exist, there are graphs for
which computing these eigenvectors requires degree
ʩ
(
n
).
Thus, such drawings are not possible on a bounded-degree root computation tree.
Radical Computation Trees.
To show that in general the eigenvectors associated
with a graph are not constructible with a radical tree we consider the graph,
Y
,on
nine vertices in Figure 5 for the Laplacian and relaxed Laplacian matrices, and in the
