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: We show that planar embeddable -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 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 be a maximally independent -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.
- 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
- L. Asimow and B. Roth, The Rigidity of Graphs, Trans. Amer. Math. Soc., 245 (1978), 279-289. MR 0511410 (80i:57004a)
- W. Bouma, I. Fudos I, C. Hoffmann C., J, Cai, R. Paige, A geometric constraint solver, Computer Aided Design 27 (1995), 487-501.
- R. Diestel, Graph Theory, Springer-Verlag, 1997. MR 1448665
- D. Cox, J. Little, D. O'Shea, Ideals, Varieties and Algorithms, Springer-Verlag, 1992. MR 1189133 (93j:13031)
- 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.
- R. Haas, D. Orden, G. Rote, F. Santos, B. Servatius, H. Servatius, D. Souvaine, I. Streinu and W. Whiteley, Planar Minimally Rigid Graphs and Pseudo-Triangulations, J. Computational Geometry: Theory and Applications", 2005 (May), 31-61. MR 2131802
- W.V.D. Hodge, D. Pedoe, Methods of Algebraic Geometry Volume 2, Cambridge University Press, 1952.MR 0048065 (13:972c)
- J.E. Hopcroft and R.E. Tarjan, Dividing a graph into connected components, Siam J. of Computing, 2 (1973), 135-158. MR 0327391 (48:5733)
- G. Laman, On graphs and the rigidity of plane skeletal structures, J. Engineering Mathematics, 4 (1970), 331-340.MR 0269535 (42:4430)
- 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.
- J. C. Owen and S. C. Power, The Nonsolvability by Radicals of Generic 3-connected Planar Graphs, 4th International Workshop on Automated Deduction in Geometry 2002, RISC Linz, Lecture Notes in Artificial Intelligence vol. 2930, F. Winkler (Ed.) Springer, 2004. MR 2090404
- I. Stewart, Galois Theory, Chapman and Hall, 1973. MR 0330122 (48:8460)
- I. 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
- I. Streinu, Combinatorial Roadmaps in Configuration Spaces of Simple Planar Polygons, DIMACS Workshop on Algorithmic and Quantitative Aspects of Real Algebraic Geometry in Mathematics and Computer Science, March 2001, DIMACS Center, Rutgers University, Eds. S. Basu and L. González-Vega, American Mathematical Society, 2001, 181-206. MR 1995020 (2004i:68234)
- W.T. Tutte, Graph Theory, Addison-Wesley, 1984. MR 0746795 (87c:05001)
- B.L. Van Der Waerden, Modern Algebra Vol. I, English Translation 1948.MR 0029363 (10:587b)
- W. Whiteley, in Matroid Applications ed. N. White, Encyclodedia of Mathematics and its applications 40 (1992), 1-51. MR 1165537 (92m:05004)
- W. Whiteley, Rigidity and scene analysis, Handbook of Discrete and Computational Geometry, eds. J.E. Goodman and J. O'Rourke, CRC Press, 1997. MR 1730205
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