. Ait-aoudia, R. Samy, D. Jegou, and . Michelucci, Reduction of constraint systems, 2014.
URL : https://hal.archives-ouvertes.fr/hal-00848677

J. Bang-jensen, Z. Gregory, and . Gutin, Digraphs: theory, algorithms and applications, 2008.

M. Barto?, G. Elber, and I. Hanniel, Topologically guaranteed univariate solutions of underconstrained polynomial systems via no-loop and single-component tests, Computer-Aided Design, vol.438, pp.1035-1044, 2011.

B. Bettig and C. M. Hoffmann, Geometric Constraint Solving in Parametric Computer-Aided Design, Journal of computing and information science in engineering 11, p.21001, 2011.
DOI : 10.1016/j.cad.2006.01.005

W. Boehm and H. Prautzsch, The insertion algorithm, Computer-Aided Design, vol.17, issue.2, pp.58-59, 1985.
DOI : 10.1016/0010-4485(85)90246-5

N. Bose, Gröbner bases: An algorithmic method in polynomial ideal theory, Multidimensional Systems Theory and Applications, pp.89-127, 1995.

P. Bunus and P. Fritzson, A Debugging Scheme for Declarative Equation Based Modeling Languages, International Symposium on Practical Aspects of Declarative Languages, pp.280-298, 2002.
DOI : 10.1007/3-540-45587-6_18

V. Cheutet, M. Daniel, S. Hahmann, L. Greca, J. Léon et al., CONSTRAINT MODELING FOR CURVES AND SURFACES IN CAGD: A SURVEY, International Journal of Shape Modeling, vol.24, issue.02, pp.2-159, 2007.
DOI : 10.1007/BF01900346
URL : https://hal.archives-ouvertes.fr/hal-00118989

S. C. Chou, Mechanical Geometry Theorem Proving Mathematics and Its Applications, p.9789027726506, 1988.
DOI : 10.1007/978-94-009-4037-6

S. Chou, An introduction to Wu's method for mechanical theorem proving in geometry, Journal of Automated Reasoning, vol.4, issue.3, pp.237-267, 1988.
DOI : 10.1007/BF00244942

S. Chou and X. Gao, Ritt-Wu's decomposition algorithm and geometry theorem proving, 10th International Conference on Automated Deduction, pp.207-220, 1990.
DOI : 10.1007/3-540-52885-7_89

D. Cox, J. Little, and D. O. Shea, Ideals, varieties, and algorithms, 1992.

H. S. Coxeter, . Macdonald, L. Samuel, and . Greitzer, Geometry revisited, Maa, vol.19, 1967.
DOI : 10.5948/UPO9780883859346

R. Diestel, Graph Theory. Electronic library of mathematics, p.9783540261834, 2006.

T. W. Dubé, The structure of polynomial ideals and Gröbner bases, In: SIAM Journal on Computing, vol.194, pp.750-773, 1990.

A. L. Dulmage, S. Nathan, and . Mendelsohn, Coverings of bipartite graphs, Journal canadien de math??matiques, vol.10, issue.0, pp.516-534, 1958.
DOI : 10.4153/CJM-1958-052-0

G. Elber, Linearizing the area and volume constraints, 2000.

B. Falcidieno, F. Giannini, J. Léon, and J. Pernot, Processing Free Form Objects within a Product Development Process Framework, In: Advances in Computers and Information in Engineering Research, vol.1, pp.317-344, 2014.
DOI : 10.1115/1.860328_ch13
URL : https://hal.archives-ouvertes.fr/hal-00922950

G. E. Farin, J. Hoschek, and M. Kim, Handbook of computer aided geometric design, 2002.

M. Fontana, F. Giannini, and M. Meirana, FREE FORM FEATURES FOR AESTHETIC DESIGN, International Journal of Shape Modeling, vol.30, issue.02, pp.273-302, 2000.
DOI : 10.1145/151280.151283

F. Jr, D. Lr, and . Fulkerson, Maximal flow through a network, Classic papers in combinatorics, pp.243-248, 2009.

S. Foufou and D. Michelucci, Interrogating witnesses for geometric constraint solving, Information and Computation 216, pp.24-38, 2012.
DOI : 10.1016/j.ic.2011.09.006
URL : https://hal.archives-ouvertes.fr/hal-00784001

S. Foufou, D. Michelucci, and J. Jurzak, Numerical decomposition of geometric constraints, Proceedings of the 2005 ACM symposium on Solid and physical modeling , SPM '05, pp.143-151, 2005.
DOI : 10.1145/1060244.1060261

I. Fudos and C. M. Hoffmann, A graph-constructive approach to solving systems of geometric constraints, ACM Transactions on Graphics, vol.16, issue.2, pp.179-216, 1997.
DOI : 10.1145/248210.248223

X. Gao and S. Chou, Solving geometric constraint systems. II. A symbolic approach and decision of Rc-constructibility, Computer-Aided Design, vol.30, issue.2, pp.115-122, 1998.
DOI : 10.1016/S0010-4485(97)00055-9

. Ge, S. Jian-xin, X. Chou, and . Gao, Geometric constraint satisfaction using optimization methods, Computer-Aided Design, vol.31, issue.14, pp.867-879, 1999.
DOI : 10.1016/S0010-4485(99)00074-3

C. Gonzalez-ochoa, S. Mccammon, and J. Peters, Computing moments of objects enclosed by piecewise polynomial surfaces, ACM Transactions on Graphics, vol.17, issue.3, pp.143-157, 1998.
DOI : 10.1145/285857.285858

G. Gouaty, L. Fang, D. Michelucci, M. Daniel, J. Pernot et al., Variational geometric modeling with black box constraints and DAGs, Computer-Aided Design, vol.75, issue.76, pp.1-12, 2016.
DOI : 10.1016/j.cad.2016.02.002
URL : https://hal.archives-ouvertes.fr/hal-01281351

J. E. Graver, B. Servatius, and H. Servatius, Combinatorial Rigidity. Graduate studies in mathematics
DOI : 10.1090/gsm/002

S. Guillet, Modification et construction de formes gauches soumisesàsoumisesà des contraintes de conception, 1999.

S. Hahmann, B. Sauvage, and G. Bonneau, Area preserving deformation of multiresolution curves, Computer aided geometric design 22.4, pp.349-367, 2005.
DOI : 10.1016/j.cagd.2005.01.006
URL : https://hal.archives-ouvertes.fr/hal-00319648

E. J. Haug, Computer aided kinematics and dynamics of mechanical systems, 1989.

C. M. Hoffman, A. Lomonosov, and M. Sitharam, Decomposition Plans for Geometric Constraint Systems, Part I: Performance Measures for CAD, Journal of Symbolic Computation 31.4, pp.367-408, 2001.
DOI : 10.1006/jsco.2000.0402

C. M. Hoffmann, Geometric and Solid Modeling: An Introduction, pp.1-55860, 1989.

C. M. Hoffmann and R. Juan, Erep: An editable, highlevel representation for geometric design and analysis, Selected and Expanded Papers from the IFIP TC5/WG5. 2 Working Conference on BIBLIOGRAPHY Geometric Modeling for Product Realization, pp.129-164, 1992.

C. M. Hoffmann, A. Lomonosov, and M. Sitharam, Finding solvable subsets of constraint graphs, International Conference on Principles and Practice of Constraint Programming, pp.463-477, 1997.
DOI : 10.1007/BFb0017460

C. M. Hoffmann, M. Sitharam, and B. Yuan, Making constraint solvers more usable: overconstraint problem, Computer-Aided Design, vol.36, issue.4, pp.377-399, 2004.
DOI : 10.1016/S0010-4485(03)00099-X

H. Hu, M. Kleiner, and J. Pernot, Over-constraints detection and resolution in geometric equation systems, Computer-Aided Design, vol.90, 2017.
DOI : 10.1016/j.cad.2017.05.019

C. Jermann, B. Neveu, and G. Trombettoni, Algorithms for identifying rigid subsystems in geometric constraint systems, In: IJCAI, vol.3, pp.233-238, 2003.
URL : https://hal.archives-ouvertes.fr/hal-01408610

C. Jermann, G. Trombettoni, B. Neveu, and P. Mathis, DECOMPOSITION OF GEOMETRIC CONSTRAINT SYSTEMS: A SURVEY, International Journal of Computational Geometry & Applications, vol.16, issue.05n06, pp.379-414, 2006.
DOI : 10.1145/321662.321668
URL : https://hal.archives-ouvertes.fr/hal-00481267

D. Kincaid, E. W. Ronald, and . Cheney, Numerical analysis: mathematics of scientific computing, 2002.

K. Kondo, Algebraic method for manipulation of dimensional relationships in geometric models, Computer-Aided Design, vol.24, issue.3, pp.141-147, 1992.
DOI : 10.1016/0010-4485(92)90033-7

S. G. Krantz and H. R. Parks, The Implicit Function Theorem: History , Theory, and Applications. Modern Birkhäuser Classics, p.9781461459811, 2012.

A. Kubicki, D. Michelucci, and S. Foufou, Witness computation for solving geometric constraint systems, 2014 Science and Information Conference, pp.759-770, 2014.
DOI : 10.1109/SAI.2014.6918272
URL : https://hal.archives-ouvertes.fr/hal-01205759

G. Laman, On graphs and rigidity of plane skeletal structures, Journal of Engineering Mathematics, vol.4, issue.4, pp.331-340, 1970.
DOI : 10.1007/BF01534980

H. Lamure and D. Michelucci, Qualitative Study of Geometric Constraints, Geometric Constraint Solving and Applications, pp.234-258, 1998.
DOI : 10.1007/978-3-642-58898-3_12

J. Lasseter, Principles of traditional animation applied to 3D computer animation, ACM SIGGRAPH Computer Graphics, vol.21, issue.4, pp.35-44, 1987.
DOI : 10.1145/37402.37407

R. S. Latham and A. E. Middleditch, Connectivity analysis: a tool for processing geometric constraints, Computer-Aided Design, vol.28, issue.11, pp.917-928, 1996.
DOI : 10.1016/0010-4485(96)00023-1

C. E. Leiserson, B. Tao, and . Schardl, A work-efficient parallel breadth-first search algorithm (or how to cope with the nondeterminism of reducers), Proceedings of the 22nd ACM symposium on Parallelism in algorithms and architectures, SPAA '10, pp.303-314, 2010.
DOI : 10.1145/1810479.1810534

D. Lesage, Un modèle dynamique de spécifications d'ingénierie basé sur une approche de géométrie variationnelle, 2002.

R. A. Light, C. David, and . Gossard, Variational geometry: a new method for modifying part geometry for finite element analysis, Computers & Structures, vol.17, pp.5-6, 1983.

V. C. Lin, C. David, . Gossard, A. Robert, and . Light, Variational geometry in computer-aided design, In: ACM SIGGRAPH Computer Graphics, vol.153, pp.171-177, 1981.

R. Maculet and M. Daniel, Conception, modélisation géométrique et contraintes en CAO: une synthèse In: Revue d'intelligence artificielle 18, pp.5-6, 2004.

P. Michalik and B. Brüderlin, Constraint-based design of B-spline surfaces from curves, Proceedings of the ninth ACM symposium on Solid modeling and applications. Eurographics Association, pp.213-223, 2004.

D. Michelucci and S. Foufou, Detecting All Dependences in Systems of Geometric Constraints Using the Witness Method, pp.98-112, 2006.
DOI : 10.1007/978-3-540-77356-6_7

D. Michelucci, S. Foufou, L. Lamarque, and P. Schreck, Geometric constraints solving, Proceedings of the 2006 ACM symposium on Solid and physical modeling , SPM '06, pp.185-196, 2006.
DOI : 10.1145/1128888.1128915
URL : https://hal.archives-ouvertes.fr/hal-01246071

D. Michelucci, P. Schreck, E. Simon, C. Thierry, J. Fünfzig et al., Using the witness method to detect rigid subsystems of geometric constraints in CAD, Proceedings of the 14th ACM Symposium on Solid and Physical Modeling, SPM '10, pp.91-100, 2010.
DOI : 10.1145/1839778.1839791
URL : https://hal.archives-ouvertes.fr/hal-00691703

M. Moinet, G. Mandil, and P. Serre, Defining tools to address over-constrained geometric problems in Computer Aided Design, Computer-Aided Design, vol.48, pp.42-52, 2014.
DOI : 10.1016/j.cad.2013.11.002

P. Okunev, R. Charles, and . Johnson, Necessary and sufficient conditions for existence of the LU factorization of an arbitrary matrix, 2005.

J. C. Owen, Algebraic solution for geometry from dimensional constraints, Proceedings of the first ACM symposium on Solid modeling foundations and CAD/CAM applications , SMA '91, pp.397-407, 1991.
DOI : 10.1145/112515.112573
URL : https://cumincad.architexturez.net/system/files/pdf/9ad2.content.pdf

J. G. Oxley, Matroid Theory. Oxford graduate texts in mathematics, p.9780199202508, 2006.

J. Pernot, S. Guillet, J. Léon, B. Falcidieno, and F. Giannini, Multi-minimisations for shape control of fully freeform deformation features (/spl delta, Shape Modeling Applications Proceedings. IEEE, pp.53-62, 2004.

J. Pernot, B. Falcidieno, F. Giannini, and J. Léon, Incorporating free-form features in aesthetic and engineering product design: State-of-the-art report, Computers in Industry, vol.59, issue.6, pp.626-637, 2008.
DOI : 10.1016/j.compind.2008.03.004
URL : https://hal.archives-ouvertes.fr/hal-01403250

J. Pernot, Fully free form deformation features for aesthetic and engineering designs, 2004.

J. Pernot, Q. Qiao, and P. Veron, Constraints Automatic Relaxation to Design Products with Fully Free Form Features, Advances in Integrated Design and Manufacturing in Mechanical Engineering II, pp.145-160, 2007.
DOI : 10.1007/978-1-4020-6761-7_10

J. Pernot, B. Falcidieno, F. Giannini, and J. Léon, Fully free-form deformation features for aesthetic shape design, Journal of Engineering Design, vol.15, issue.2, pp.115-133, 2005.
DOI : 10.1109/SMA.2001.923397

L. Piegl and W. Tiller, The NURBS Book. Monographs in Visual Communication, p.9783540615453, 1996.

D. Podgorelec, V. Borut?alikborut?borut?alik, and . Domiter, Dealing with redundancy and inconsistency in constructive geometric constraint solving, Advances in Engineering Software, vol.39, issue.9, pp.770-786, 2008.
DOI : 10.1016/j.advengsoft.2007.10.003

A. Pothen and C. Fan, Computing the block triangular form of a sparse matrix, ACM Transactions on Mathematical Software, vol.16, issue.4, pp.303-324, 1990.
DOI : 10.1145/98267.98287

. Sauvage, S. Basile, G. Hahmann, and . Bonneau, Length Preserving Multiresolution Editing of Curves, Computing, vol.72, issue.1-2, pp.161-170, 2004.
DOI : 10.1007/s00607-003-0054-y
URL : https://hal.archives-ouvertes.fr/hal-00319651

D. Serrano, Constraint management in conceptual design, 1987.

D. Serrano, Automatic dimensioning in design for manufacturing, Proceedings of the first ACM symposium on Solid modeling foundations and CAD/CAM applications , SMA '91, pp.379-386, 1991.
DOI : 10.1145/112515.112568

M. Sitharam, J. Peters, and Y. Zhou, Solving minimal, wellconstrained, 3d geometric constraint systems: combinatorial optimization of algebraic complexity, 2004.

M. Sitharam and Y. Zhou, A tractable, approximate, combinatorial 3d rigidity characterization, Fifth Automated Deduction in Geometry (ADG), 2004.

N. Sridhar, R. Agrawal, L. Gary, and . Kinzel, Algorithms for the structural diagnosis and decomposition of sparse, underconstrained design systems, Computer-Aided Design, vol.28, issue.4, pp.237-249, 1996.
DOI : 10.1016/0010-4485(96)88488-0

G. Strang, Linear Algebra and Its Applications, p.9780030105678, 2006.

R. Tarjan, Depth-first search and linear graph algorithms, SIAM journal on computing 1.2, pp.146-160, 1972.
DOI : 10.1137/0201010
URL : http://www.csee.wvu.edu/~xinl/library/papers/comp/Tarjan_siam1972.pdf

. Thierry, E. Simon, P. Schreck, D. Michelucci, C. Fünfzig et al., Extensions of the witness method to characterize under-, over- and well-constrained geometric constraint systems, Computer-Aided Design, vol.43, issue.10, pp.1234-1249, 2011.
DOI : 10.1016/j.cad.2011.06.018
URL : https://hal.archives-ouvertes.fr/hal-00691690

K. Thulasiraman, N. Madisetti, and . Swamy, Graphs: theory and algorithms, 2011.
DOI : 10.1002/9781118033104

W. Wu, BASIC PRINCIPLES OF MECHANICAL THEOREM PROVING IN ELEMENTARY GEOMETRIES, 2012.
DOI : 10.1142/9789812791085_0012

P. Xiaobo, C. Liping, Z. Fanli, and Z. Ji, Singularity analysis of geometric constraint systems, J. Comput. Sci. & Technol, vol.173, pp.314-323, 2002.