The Galois Complexity of Graph Drawing: Why Numerical Solutions Are Ubiquitous for Force-Directed, Spectral, and Circle Packing Drawings

Bannister, Michael J. and Devanny, William E. and Eppstein, David and Goodrich, Michael T. (2014) The Galois Complexity of Graph Drawing: Why Numerical Solutions Are Ubiquitous for Force-Directed, Spectral, and Circle Packing Drawings. In: Graph Drawing 22nd International Symposium, GD 2014, September 24-26, 2014 , pp. 149-161(Official URL: http://dx.doi.org/10.1007/978-3-662-45803-7_13).

Full text not available from this repository.

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.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-662-45803-7_13
Classifications: M Methods > M.100 Algebraic
Z Theory > Z.999 Others
Divisions: UNSPECIFIED
Depositing User: Administration GDEA
Date Deposited: 22 May 2015 09:02
Last Modified: 22 May 2015 09:02
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1429

Actions (login required)

View Item View Item