Home Issues About JGAA Instructions for Authors
 
 
Special Issue on Selected Papers from the Twenty-second International Symposium on Graph Drawing, GD 2014
DOI: 10.7155/jgaa.00349
The Galois Complexity of Graph Drawing: Why Numerical Solutions are Ubiquitous for Force-Directed, Spectral, and Circle Packing Drawings
Vol. 19, no. 2, pp. 619-656, 2015. Regular paper.
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 drawings ubiquitously use iterative numerical approximations rather than constructing and then solving algebraic expressions representing their exact solutions. To explain 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 exactly even in extended computational models that include such operations. We formulate an abstract model of exact symbolic computation that augments algebraic computation trees with functions for computing radicals or roots of low-degree polynomials, and we show that this model cannot solve these graph drawing problems.
Submitted: October 2014.
Reviewed: February 2015.
Revised: February 2015.
Accepted: February 2015.
Final: February 2015.
Published: November 2015.
Communicated by Christian Duncan and Antonios Symvonis
article (PDF)
BibTeX