Geodesic
The Galois Complexity of Graph Drawing: Why Numerical Solutions are Ubiquitous for Force-Directed, Spectral, and Circle Packing Drawings
Journal of Graph Algorithms and Applications, Special Issue on Selected Papers from the Twenty-second International Symposium on Graph Drawing, GD 2014 , Tome 19 (2015) no. 2, pp. 619-656.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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.
DOI : 10.7155/jgaa.00349
Keywords: graph drawing, numerical, force-directed, Fruchterman and Reingold, Kamada and Kawai, spectral, eigenvalues, circle packing, galois theory 
@article{JGAA_2015_19_2_a3,
     author = {Michael Bannister and William Devanny and David Eppstein and Michael Goodrich},
     title = {The {Galois} {Complexity} of {Graph} {Drawing:} {Why} {Numerical} {Solutions} are {Ubiquitous} for {Force-Directed,} {Spectral,} and {Circle} {Packing} {Drawings}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {619--656},
     publisher = {mathdoc},
     volume = {19},
     number = {2},
     year = {2015},
     doi = {10.7155/jgaa.00349},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00349/}
}
TY  - JOUR
AU  - Michael Bannister
AU  - William Devanny
AU  - David Eppstein
AU  - Michael Goodrich
TI  - The Galois Complexity of Graph Drawing: Why Numerical Solutions are Ubiquitous for Force-Directed, Spectral, and Circle Packing Drawings
JO  - Journal of Graph Algorithms and Applications
PY  - 2015
SP  - 619
EP  - 656
VL  - 19
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00349/
DO  - 10.7155/jgaa.00349
LA  - en
ID  - JGAA_2015_19_2_a3
ER  - 
%0 Journal Article
%A Michael Bannister
%A William Devanny
%A David Eppstein
%A Michael Goodrich
%T The Galois Complexity of Graph Drawing: Why Numerical Solutions are Ubiquitous for Force-Directed, Spectral, and Circle Packing Drawings
%J Journal of Graph Algorithms and Applications
%D 2015
%P 619-656
%V 19
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00349/
%R 10.7155/jgaa.00349
%G en
%F JGAA_2015_19_2_a3
Michael Bannister; William Devanny; David Eppstein; Michael Goodrich. The Galois Complexity of Graph Drawing: Why Numerical Solutions are Ubiquitous for Force-Directed, Spectral, and Circle Packing Drawings. Journal of Graph Algorithms and Applications, 
							Special Issue on Selected Papers from the Twenty-second International Symposium on Graph Drawing, GD 2014
					, Tome 19 (2015) no. 2, pp. 619-656. doi : 10.7155/jgaa.00349. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00349/

Cité par Sources :