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

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 0511410 (80i:57004a)
  • 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. R. Diestel, Graph Theory, Springer-Verlag, 1997. MR 1448665
  • 4. D. Cox, J. Little, D. O'Shea, Ideals, Varieties and Algorithms, Springer-Verlag, 1992. MR 1189133 (93j:13031)
  • 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. 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
  • 8. W.V.D. Hodge, D. Pedoe, Methods of Algebraic Geometry Volume 2, Cambridge University Press, 1952.MR 0048065 (13:972c)
  • 9. 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)
  • 10. G. Laman, On graphs and the rigidity of plane skeletal structures, J. Engineering Mathematics, 4 (1970), 331-340.MR 0269535 (42:4430)
  • 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. 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
  • 14. I. Stewart, Galois Theory, Chapman and Hall, 1973. MR 0330122 (48:8460)
  • 15. 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
  • 16. 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)
  • 17. W.T. Tutte, Graph Theory, Addison-Wesley, 1984. MR 0746795 (87c:05001)
  • 18. B.L. Van Der Waerden, Modern Algebra Vol. I, English Translation 1948.MR 0029363 (10:587b)
  • 19. W. Whiteley, in Matroid Applications ed. N. White, Encyclodedia of Mathematics and its applications 40 (1992), 1-51. MR 1165537 (92m:05004)
  • 20. 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

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

American Mathematical Society