The non-solvability by radicals of generic 3-connected planar Laman graphs

Owen, J.; Power, S.

doi:10.1090/S0002-9947-06-04049-9

The non-solvability by radicals of generic 3-connected planar Laman graphs
HTML articles powered by AMS MathViewer

by J. C. Owen and S. C. Power PDF

Trans. Amer. Math. Soc. 359 (2007), 2269-2303 Request permission

Abstract:

We show that planar embeddable $3$-connected Laman graphs are generically non-soluble. A Laman graph represents a configuration of points on the Euclidean plane with just enough distance specifications between them to ensure rigidity. Formally, a Laman graph is a maximally independent graph, that is, one that satisfies the vertex-edge count $2v - 3 = e$ together with a corresponding inequality for each subgraph. The following main theorem of the paper resolves a conjecture of Owen (1991) in the planar case. Let $G$ be a maximally independent $3$-connected planar graph, with more than 3 vertices, together with a realisable assignment of generic distances for the edges which includes a normalised unit length (base) edge. Then, for any solution configuration for these distances on a plane, with the base edge vertices placed at rational points, not all coordinates of the vertices lie in a radical extension of the distance field.

References

L. Asimow and B. Roth, The rigidity of graphs, Trans. Amer. Math. Soc. 245 (1978), 279–289. MR 511410, DOI 10.1090/S0002-9947-1978-0511410-9
W. Bouma, I. Fudos I, C. Hoffmann C., J, Cai, R. Paige, A geometric constraint solver, Computer Aided Design 27 (1995), 487-501.
Reinhard Diestel, Graph theory, Graduate Texts in Mathematics, vol. 173, Springer-Verlag, New York, 1997. Translated from the 1996 German original. MR 1448665
David Cox, John Little, and Donal O’Shea, Ideals, varieties, and algorithms, Undergraduate Texts in Mathematics, Springer-Verlag, New York, 1992. An introduction to computational algebraic geometry and commutative algebra. MR 1189133, DOI 10.1007/978-1-4757-2181-2
D.J. Jacobs, A.J. Rado, L.A. Kuhn and M.F. Thorpe, Protein flexibility predictions using graph theory, Proteins, Structure, Functions and Genetics, 44 (2001), 150-165.
X.-S. Gao, S.-C Chou, Solving geometric constraint systems. II. A symbolic approach and decision of rc-constructibility, Computer-Aided Design, 30 (1998), 115-122.
Ruth Haas, David Orden, Günter Rote, Francisco Santos, Brigitte Servatius, Herman Servatius, Diane Souvaine, Ileana Streinu, and Walter Whiteley, Planar minimally rigid graphs and pseudo-triangulations, Comput. Geom. 31 (2005), no. 1-2, 31–61. MR 2131802, DOI 10.1016/j.comgeo.2004.07.003
W. V. D. Hodge and D. Pedoe, Methods of algebraic geometry. Vol. II. Book III: General theory of algebraic varieties in projective space. Book IV: Quadrics and Grassmann varieties, Cambridge, at the University Press, 1952. MR 0048065
J. E. Hopcroft and R. E. Tarjan, Dividing a graph into triconnected components, SIAM J. Comput. 2 (1973), 135–158. MR 327391, DOI 10.1137/0202012
G. Laman, On graphs and rigidity of plane skeletal structures, J. Engrg. Math. 4 (1970), 331–340. MR 269535, DOI 10.1007/BF01534980
R. Light and J. Gossard, Modification of geometric models through variational constraints, Computer Aided Design, 14 (1982) 209.
J.C. Owen, Algebraic solution for geometry from dimensional constraints, in ACM Symposium on Foundations in Solid Modeling, pages 397-407, Austen, Texas, 1991.
John C. Owen and Steve C. Power, The nonsolvability by radicals of generic 3-connected planar graphs, Automated deduction in geometry, Lecture Notes in Comput. Sci., vol. 2930, Springer, Berlin, 2004, pp. 124–131. MR 2090404, DOI 10.1007/978-3-540-24616-9_{8}
Ian Stewart, Galois theory, Chapman and Hall, London, 1973. MR 0330122
Ileana Streinu, A combinatorial approach to planar non-colliding robot arm motion planning, 41st Annual Symposium on Foundations of Computer Science (Redondo Beach, CA, 2000) IEEE Comput. Soc. Press, Los Alamitos, CA, 2000, pp. 443–453. MR 1931841, DOI 10.1109/SFCS.2000.892132
Ileana Streinu, Combinatorial roadmaps in configuration spaces of simple planar polygons, Algorithmic and quantitative real algebraic geometry (Piscataway, NJ, 2001) DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 60, Amer. Math. Soc., Providence, RI, 2003, pp. 181–205. MR 1995020, DOI 10.1090/dimacs/060/12
W. T. Tutte, Graph theory, Encyclopedia of Mathematics and its Applications, vol. 21, Addison-Wesley Publishing Company, Advanced Book Program, Reading, MA, 1984. With a foreword by C. St. J. A. Nash-Williams. MR 746795
B. L. van der Waerden, Modern Algebra. Vol. I, Frederick Ungar Publishing Co., New York, N. Y., 1949. Translated from the second revised German edition by Fred Blum; With revisions and additions by the author. MR 0029363
Neil White (ed.), Matroid applications, Encyclopedia of Mathematics and its Applications, vol. 40, Cambridge University Press, Cambridge, 1992. MR 1165537, DOI 10.1017/CBO9780511662041
Walter Whiteley, Rigidity and scene analysis, Handbook of discrete and computational geometry, CRC Press Ser. Discrete Math. Appl., CRC, Boca Raton, FL, 1997, pp. 893–916. MR 1730205