Information Technology Reference
In-Depth Information
graph drawings (in both the Fruchterman-Reingold [4] and Kamada-Kawai [5] ap-
proaches), spectral graph drawings [6], classical multidimensional scaling [7], and cir-
cle packings [8]. Note that these impossibility results go beyond saying that such sym-
bolic solutions are computationally infeasible or undecidable to find—instead, we show
that such solutions do not exist.
To prove ourresults, we use Galois theory, a connection between the theories of
algebraic numbers and abstract groups. Two classical applications of Galois theory
use it to prove the impossibility of the classical Greek problem of doubling the cube
using compass and straightedge, and of solving fifth-degree polynomials by nested
radicals. In ourterms,theseresults concern quadratic computation trees and radical
computation trees, respectively. Our proofs build on this theory by applying Galois
theory to the algebraic numbers given by the vertex positions in different types of
graph drawings. For force-directed and spectral drawing,wefindsmallgraphs (in
one case as small as a length-three path) whose drawings directly generate unsolvable
Galois groups. For circle packing, an additional argument involving the compass and
straightedge constructibility of M obius transformations allows us to transform arbitrary
circle packings into a canonical form with two concentric circles, whose construction is
equivalent to the calculation of certain algebraic numbers. Because of this mathematical
foundation, we refer to this topic as the
Galois complexity
of graph drawing.
Related Work.
The problems for which Galois theory has been used to prove un-
solvability in simple algebraic computational models include shortest paths around
polyhedral obstacles [9], shortest paths throughweighted regions of the plane [10], the
geometric median of planar points [11], computing structure from motion in computer
vision [12], and finding polygons of maximal area with specified edgelengths [13]. In
each of these cases, the non-existence of a nested radical formula for the solution is
established by finding aGaloisgroup containing a symmetric group of constant degree
at least five. In our terminology, this shows that these problems cannot be solved by a
radical computation tree. We are not aware of any previous non-constant lower bounds
on the degree of the polynomial roots needed to solve a problem, comparable to our
new bounds using the root computation tree model. Brightwell and Scheinerman [14]
show that some circle packinggraph representations cannot be constructed by compass
and straightedge (what we call the quadratic computation tree model).
2
Preliminaries
Models of Computation.
We define models of computation based on the
algebraic
computation tree
[15, 16], in which each node computes a value or makes a decision
using standard arithmetic functions of previously computed values.
Specifically, we
define the following variant models:
-
A
quadratic computation tree
is an algebraic computation tree in which the set of
allowable functions for each computation node is augmented with square roots and
complex conjugation. These trees capture the geometric constructions that can be
performed by compass and unmarked straightedge.
