The nonsolvability by radicals of generic 3connected planar Laman graphs
Authors:
J. C. Owen and S. C. Power
Journal:
Trans. Amer. Math. Soc. 359 (2007), 22692303
MSC (2000):
Primary 68U07, 12F10, 05C40; Secondary 52C25
Published electronically:
October 16, 2006
MathSciNet review:
2276620
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: We show that planar embeddable connected Laman graphs are generically nonsoluble. 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 vertexedge 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
(80i:57004a), http://dx.doi.org/10.1090/S00029947197805114109
 2.
W. Bouma, I. Fudos I, C. Hoffmann C., J, Cai, R. Paige, A geometric constraint solver, Computer Aided Design 27 (1995), 487501.
 3.
Reinhard
Diestel, Graph theory, Graduate Texts in Mathematics,
vol. 173, SpringerVerlag, 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, SpringerVerlag, New York, 1992. An introduction to
computational algebraic geometry and commutative algebra. 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), 150165.
 6.
X.S. Gao, S.C Chou, Solving geometric constraint systems. II. A symbolic approach and decision of rcconstructibility, ComputerAided Design, 30 (1998), 115122.
 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
pseudotriangulations, Comput. Geom. 31 (2005),
no. 12, 31–61. MR 2131802
(2005m:05070), http://dx.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
(13,972c)
 9.
J.
E. Hopcroft and R.
E. Tarjan, Dividing a graph into triconnected components, SIAM
J. Comput. 2 (1973), 135–158. MR 0327391
(48 #5733)
 10.
G.
Laman, On graphs and rigidity of plane skeletal structures, J.
Engrg. Math. 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 397407, Austen, Texas, 1991.
 13.
John
C. Owen and Steve
C. Power, The nonsolvability by radicals of generic 3connected
planar graphs, Automated deduction in geometry, Lecture Notes in
Comput. Sci., vol. 2930, Springer, Berlin, 2004,
pp. 124–131. MR
2090404, http://dx.doi.org/10.1007/9783540246169_8
 14.
Ian
Stewart, Galois theory, Chapman and Hall, London, 1973. MR 0330122
(48 #8460)
 15.
Ileana
Streinu, A combinatorial approach to planar noncolliding 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, http://dx.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
(2004i:68234)
 17.
W.
T. Tutte, Graph theory, Encyclopedia of Mathematics and its
Applications, vol. 21, AddisonWesley Publishing Company, Advanced
Book Program, Reading, MA, 1984. With a foreword by C. St. J. A.
NashWilliams. MR
746795 (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
(10,587b)
 19.
Neil
White (ed.), Matroid applications, Encyclopedia of Mathematics
and its Applications, vol. 40, Cambridge University Press, Cambridge,
1992. MR
1165537 (92m:05004)
 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
 1.
 L. Asimow and B. Roth, The Rigidity of Graphs, Trans. Amer. Math. Soc., 245 (1978), 279289. 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), 487501.
 3.
 R. Diestel, Graph Theory, SpringerVerlag, 1997. MR 1448665
 4.
 D. Cox, J. Little, D. O'Shea, Ideals, Varieties and Algorithms, SpringerVerlag, 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), 150165.
 6.
 X.S. Gao, S.C Chou, Solving geometric constraint systems. II. A symbolic approach and decision of rcconstructibility, ComputerAided Design, 30 (1998), 115122.
 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 PseudoTriangulations, J. Computational Geometry: Theory and Applications", 2005 (May), 3161. 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), 135158. MR 0327391 (48:5733)
 10.
 G. Laman, On graphs and the rigidity of plane skeletal structures, J. Engineering Mathematics, 4 (1970), 331340.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 397407, Austen, Texas, 1991.
 13.
 J. C. Owen and S. C. Power, The Nonsolvability by Radicals of Generic 3connected 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 Noncolliding 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. 443453. 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álezVega, American Mathematical Society, 2001, 181206. MR 1995020 (2004i:68234)
 17.
 W.T. Tutte, Graph Theory, AddisonWesley, 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), 151. 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:
DCubed Ltd., Park House, Cambridge CB3 0DU, United Kingdom
Email:
john.owen@dcubed.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:
http://dx.doi.org/10.1090/S0002994706040499
PII:
S 00029947(06)040499
Keywords:
Maximally independent graph,
3connected,
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
