### The Galois Complexity of Graph Drawing

**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.