Information Technology Reference
In-Depth Information
The Galois Complexity of Graph Drawing:
Why Numerical Solutions Are Ubiquitous for
Force-Directed, Spectral, and Circle Packing Drawings
Michael J. Bannister, William E. Devanny,
David Eppstein, and Michael T. Goodrich
Department of Computer Science, University of California, Irvine
Abstract.
Many well-known graph drawing techniques, including force directed
drawings, spectral graph layouts, multidimensional scaling, and circle packings,
have algebraic formulations. However, practical methods for producing such draw-
ings ubiquitously use iterative numerical approximations rather than constructing
and then solving algebraic expressions representing their exact solutions. To ex-
plain this phenomenon, we use Galois theory to show that many variants of these
problems have solutions that cannot be expressed by nested radicals or nested
roots of low-degree polynomials. Hence, such solutions cannot be computed ex-
actly even in extended computational models that include such operations.
1
Introduction
One of the most powerful paradigms for drawing a graph is to construct an algebraic
formulation for a suitably-defined optimal drawing of the graph and then solve this
formulation to produce a drawing. Examples of this
algebraic graph drawing
approach
include the force-directed, spectral, multidimensional scaling, and circle packing draw-
ing techniques (which we review in the full version of the paper for readers unfamiliar
with them).
Even though this paradigm starts from an algebraic formulation, the ubiquitous
method for solving such formulations is to approximately optimize them numerically in
an iterative fashion. That is, with a few exceptions for linear systems [1-3], approximate
numerical solutions for algebraic graph drawing are overwhelmingly preferred over
exact symbolic solutions. It is therefore natural to ask if this preference for numerical
solutions over symbolic solutions is inherent in algebraic graph drawing or duetosome
other phenomena, such as laziness or lack of mathematical sophistication on the part of
those who are producing the algebraic formulations.
In this paper, we introduce a framework for deciding whether certain algebraic graph
drawing formulations have symbolic solutions, and we show that exact symbolic solu-
tions are, in fact, impossible in several algebraic computation models, for some simple
examples of common algebraic graph drawing formulations, including force-directed
This research was supported in part by ONR MURI grant N00014-08-1-1015 and NSF grants
1217322, 1011840, and 1228639.
