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

## Additional Information

**J. C. Owen**- Affiliation: D-Cubed Ltd., Park House, Cambridge CB3 0DU, United Kingdom
- Email: john.owen@d-cubed.co.uk
**S. C. Power**- Affiliation: Department of Mathematics and Statistics, Lancaster University, Lancaster, LA1 4YF, United Kingdom
- MR Author ID: 141635
- Email: s.power@lancaster.ac.uk
- Received by editor(s): October 16, 2003
- Received by editor(s) in revised form: March 15, 2005
- Published electronically: October 16, 2006
- © Copyright 2006 American Mathematical Society
- Journal: Trans. Amer. Math. Soc.
**359**(2007), 2269-2303 - MSC (2000): Primary 68U07, 12F10, 05C40; Secondary 52C25
- DOI: https://doi.org/10.1090/S0002-9947-06-04049-9
- MathSciNet review: 2276620