Rigid frameworks in some Euclidian space are embedded graphs having a unique local realization (up to Euclidian motions) for the given edge lengths, although globally they may have several. We study the number of distinct planar embeddings of minimally rig

OntheNumberofEmbeddingsofMinimallyRigidGraphs

DepartmentCiprianofBorcea

Mathematics

RiderUniversityLawrenceville,NJ08648

borcea@rider.edu

ABSTRACT

RigidframeworksinsomeEuclidianspaceareembeddedgraphshavingauniquelocalrealization(uptoEuclidianmotions)forthegivenedgelengths,althoughgloballytheymayhaveseveral.Westudythenumberofdistinctplanarembeddingsofminimallyrigidgraphswithnvertices.Weshowthat,moduloplanarrigidmotions,thisnumbermost 2n 4isatn 2

≈4n.Wealsoexhibitseveralfamilieswhichrealizelowerboundsoftheorderof2n,2.21nand2.88n.Fortheupperboundweusetechniquesfromcomplexal-gebraicgeometry,2,nbasedonthe(projective)Cayley-MengervarietyCM(C) P(n2

) 1(C)overthecomplexnumbers

C.Inthiscontext,pointcon gurationsarerepresentedbycoordinatesgivenbysquareddistancesbetweenallpairsofpoints.Sectioningthe,nvarietywith2n 4hyperplanesyieldsatmostdeg(CM2)zero-dimensionalandone ndsthisdegreetobeD2,n=1 2n 4n 2 components,.ThelowerboundsarerelatedtoinductiveconstructionsofminimallyrigidgraphsviaHennebergsequences.

Thesameapproachworksinhigherdimensions.Inpar-ticularweshowthatitleadstoanupperboundof2D3,n2n 3edge n 6

=

forthenumberofspatialembeddingswithgenericlengthsn 3

ofthe1-skeletonofasimplicialpolyhedron,uptorigidmotions.

CategoriesandSubjectDescriptors

F.2.2[TheoryofComputation]:NonnumericalAlgorithmsandProblems—GeometricalProblemsandComputation;G.2.2[DiscreteMathematics]:GraphTheory;G.1.5[NumericalAnalysis]:RootsofNonlinearequations

GeneralTerms

Theory

Keywords

DistanceGeometry,Cayley-MengerVariety,Rigidity,GraphEmbedding,UpperBound,LowerBound

Permissiontomakedigitalorhardcopiesofallorpartofthisworkforpersonalorclassroomuseisgrantedwithoutfeeprovidedthatcopiesarenotmadeordistributedforpro£torcommercialadvantageandthatcopiesbearthisnoticeandthefullcitationonthe£rstpage.Tocopyotherwise,torepublish,topostonserversortoredistributetolists,requirespriorspeci£cpermissionand/orafee.

SoCG’02,June5-7,2002,Barcelona,Spain.

Copyright2002ACM1-58113-504-1/02/0006...$5.00.

ComputerIleanaScienceStreinu

Department

SmithCollege

Northampton,MA01063

streinu@cs.smith.edu

1.

INTRODUCTION

Inthispaperweareconcernedwithgraphembeddingssubjecttoedgelengthsconstraints.Weuseembedding(orrealization)intheextendedsense,whichallowssomever-ticestocoincideandsomeedgestocross.Foragivengraphandforagivensetofedgelengths,anaturalquestiontoaskis:howmanyembeddingsinRdarethere?

Obviously,fora xeddimensiond,somegraphshaveacontinuumofembeddings,ormayhavenoembeddingatallforparticularchoicesofedgelengths.Weconsiderminimallyrigidgraphsonnverticesmensiond(whichhavedn d+12

indi-edgesanduniquelocalrealizationsforgenericchoicesofedgelengths),withpartic-ularregardtodimensions2and3.

Ourresultsgiveageneralupperboundinarbitrarydimen-sion,whichisoftheorderof2dnfor xeddandnsu cientlylarge.Wealsoexhibitafamilyofgraphsinducingalowerboundoftheorderof2.88nindimension2.

HistoricalPerspective.Distancegeometryreliesonfoun-dationalworkofCayleyoncon gurationsofnpointsinEuclideand-space.AselaboratedbyMenger(see[3],237),thisledtoconditionscharacterizingsystemsof n

p.positiverealsthatarise daspairwisesquareddistancesbe-2

tweennpointsinR.Seealso[4]and[10].Indimension3,distancegeometryhasbeenusedforthestudyofmolec-ularconformationinchemistry([8],[9],[18]).Indeed,inter-atomicdistanceinformationcanbeobtainedfromnuclearmagneticresonancespectraofamolecule.Solvingthegraphembeddingproblemdeterminescoordinatesfortheatoms,andhencethe3-dimensionalshapeofthemolecule.Otherapplicationsincludesurveyingandsatelliteranging.

OurinvestigationisalsorelatedtoclassicalstudiesintheKinematicsofmechanicallinkages,inparticulartheproblemoftracingalgebraiccurves.Wunderlich([33])givesaninter-estingfamilyofgeneralizedplanarcouplercurveswithde-greegrowingexponentiallyinthenumberoflinks.RelatedworkwasalsodoneincombinatorialRigidityTheory([7],[31],[14]).Rigidframeworksareembeddedgraphshavingauniquelocalrealizationforthegivenedgelengths.Butglob-allytheremaybeseveralrealizations.Usingspecialcombi-nationsofgraphsandedgelengths,Saxe[27]hasshownthatitisNP-hardtosolvethegraphembeddingproblemindi-mensiontwo,aswellastodeterminewhetherithasauniquesolution.Undertheassumptionofgenericity,Hendrickson[17]studiedconditionsonrigidframeworksthatguaranteeauniqueglobalrealization.