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

DOI:
https://doi.org/10.1090/S0002-9947-06-04049-9

Published electronically:
October 16, 2006

MathSciNet review:
2276620

Full-text PDF

Abstract | References | Similar Articles | Additional Information

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**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.**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**, https://doi.org/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**, https://doi.org/10.1137/0202012**10.**G. Laman,*On graphs and rigidity of plane skeletal structures*, J. Engrg. Math.**4**(1970), 331–340. MR**0269535**, https://doi.org/10.1007/BF01534980**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**, https://doi.org/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**, https://doi.org/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, Addison-Wesley, 1984. MR**0746795 (87c:05001)****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**

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

Email:
john.owen@d-cubed.co.uk

**S. C. Power**

Affiliation:
Department of Mathematics and Statistics, Lancaster University, Lancaster, LA1 4YF, United Kingdom

Email:
s.power@lancaster.ac.uk

DOI:
https://doi.org/10.1090/S0002-9947-06-04049-9

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