Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



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

Authors: J. C. Owen and S. C. Power
Journal: Trans. Amer. Math. Soc. 359 (2007), 2269-2303
MSC (2000): Primary 68U07, 12F10, 05C40; Secondary 52C25
Published electronically: October 16, 2006
MathSciNet review: 2276620
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. L. Asimow and B. Roth, The rigidity of graphs, Trans. Amer. Math. Soc. 245 (1978), 279–289. MR 511410, 10.1090/S0002-9947-1978-0511410-9
  • 2. W. Bouma, I. Fudos I, C. Hoffmann C., J, Cai, R. Paige, A geometric constraint solver, Computer Aided Design 27 (1995), 487-501.
  • 3. Reinhard Diestel, Graph theory, Graduate Texts in Mathematics, vol. 173, Springer-Verlag, New York, 1997. Translated from the 1996 German original. MR 1448665
  • 4. 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
  • 5. 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.
  • 6. 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.
  • 7. 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, 10.1016/j.comgeo.2004.07.003
  • 8. 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
  • 9. J. E. Hopcroft and R. E. Tarjan, Dividing a graph into triconnected components, SIAM J. Comput. 2 (1973), 135–158. MR 0327391
  • 10. G. Laman, On graphs and rigidity of plane skeletal structures, J. Engrg. Math. 4 (1970), 331–340. MR 0269535
  • 11. R. Light and J. Gossard, Modification of geometric models through variational constraints, Computer Aided Design, 14 (1982) 209.
  • 12. J.C. Owen, Algebraic solution for geometry from dimensional constraints, in ACM Symposium on Foundations in Solid Modeling, pages 397-407, Austen, Texas, 1991.
  • 13. 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, 10.1007/978-3-540-24616-9_8
  • 14. Ian Stewart, Galois theory, Chapman and Hall, London, 1973. MR 0330122
  • 15. 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, 10.1109/SFCS.2000.892132
  • 16. 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
  • 17. 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
  • 18. 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
  • 19. Neil White (ed.), Matroid applications, Encyclopedia of Mathematics and its Applications, vol. 40, Cambridge University Press, Cambridge, 1992. MR 1165537
  • 20. 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

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2000): 68U07, 12F10, 05C40, 52C25

Retrieve articles in all journals with MSC (2000): 68U07, 12F10, 05C40, 52C25

Additional Information

J. C. Owen
Affiliation: D-Cubed Ltd., Park House, Cambridge CB3 0DU, United Kingdom

S. C. Power
Affiliation: Department of Mathematics and Statistics, Lancaster University, Lancaster, LA1 4YF, United Kingdom

Keywords: Maximally independent graph, 3-connected, algorithms for CAD, solvable by radicals.
Received by editor(s): October 16, 2003
Received by editor(s) in revised form: March 15, 2005
Published electronically: October 16, 2006
Article copyright: © Copyright 2006 American Mathematical Society