Tutt-indlejringen ( barycentrisk indlejring ) af en simpel 3-vertex-forbundet plan graf er en indlejring uden skæringer med linjestykker med de yderligere egenskaber, at den ydre flade har en konveks polygon som sin grænse, og at hvert indre toppunkt er det geometriske centrum af sine naboer. Hvis den ydre polygon er fast, bestemmer denne betingelse på de indre hjørner deres positioner unikt som en løsning til et system af lineære ligninger . Løsning af ligningerne giver en plan indlejring . Tutts "gummipakning" -sætning siger, at der aldrig er kantskæringer i en enkelt løsning, og mere strengt, at enhver flade af den resulterende plane indlejring er konveks [1] . En indstøbning kaldes en "gummi"-indlejring, fordi en sådan indlejring kan findes som en ligevægtsposition af et system af fjedre eller gummibånd, der repræsenterer grafens kanter.
Lad G være en terninggraf. Lad os fastsætte (ved at vælge en af de firkantede flader som den ydre flade) fire hjørner af den ydre flade i hjørnerne af enhedskvadraten , hvis x- og y - koordinater er kombinationer af nuller og enere. De resterende fire hjørner er så placeret i fire punkter, hvis x- og y- koordinater er kombinationer af 1/3 og 2/3, som vist på figuren. Resultatet er Tutts indlejring. For hvert indre toppunkt v i denne indlejring har de tilstødende tre hjørner tre koordinatværdier (både x og y ), en lig med v- koordinaten , en mindre og den anden 1/3 større. I gennemsnit får vi værdien af koordinaten for selve punktet v .
Betingelsen for, at et toppunkt v har gennemsnittet af sine naboers koordinater, kan udtrykkes som to lineære ligninger , den ene for x -koordinaten til v , den anden for y -koordinaten . For en graf med n toppunkter, hvoraf h er fikseret ved toppunkterne på den ydre flade, er der to ligninger og to ukendte (koordinater) for hvert indre toppunkt. Således får vi et system af lineære ligninger med 2( n − h ) ligninger i 2( n − h ) ukendte, hvis løsning er Tutt-indlejringen. Som Tatt [2] viste , for 3-vertex-forbundne plane grafer er dette system ikke degenereret. Derfor vil systemet have en unik løsning og (med en fast yderkant) vil grafen være Tutts eneste indlejring. Denne indlejring kan findes i polynomisk tid ved at løse et ligningssystem, for eksempel ved at bruge sekventiel eliminering af variable [3] .
Ifølge Steinitzs sætning er 3-forbundne plane grafer, som Tutts "gummi-oplægnings"-sætning gælder for, de samme som polyedriske grafer , graferne dannet af hjørnerne og kanterne af et konveks polyeder . Ifølge Maxwell-Cremont-metoden danner en todimensional indlejring af en plan graf en projektion af et tredimensionelt konveks polyeder, hvis og kun hvis indlejringen har en ligevægtsspænding , fordelingen af kræfter for hver kant (i begge ender af kanterne i modsatte retninger parallelt med kanterne), således at kræfterne ved hvert toppunkt balanceres . For Tutt-indstøbningen er kraftfordelingen for hver kant proportional med længden af kanten (svarende til et gummibånd), der balancerer kræfterne på alle indre punkter, men ikke ved hjørnerne af den ydre polygon. Hvis den ydre polygon er en trekant, kan du tildele frastødende kræfter på de tre ydre kanter for at afbalancere kræfterne ved hjørnerne af den ydre trekant. Således kan Tutts indlejring bruges til at finde Schlegel-diagrammerne for ethvert konveks polyeder . For enhver 3-forbundet plan graf G har enten grafen G selv eller dens dual en trekant, så vi får en polyedrisk repræsentation af grafen G eller dens dual. I det tilfælde, hvor den dobbelte graf har en trekantet flade, giver den polære konjugation en polyedrisk repræsentation af selve grafen G [3] .
Gortler, Gottsman og Thurston [4] viste resultater svarende til Tutts "gummipakning" -sætning for grafindlejringer i en torus [5] .
Chilacamarri, Dean og Litman [6] studerede en tredimensionel indlejring af grafer af firedimensionelle polytoper , dannet ved samme metode som i Tutts indlejringsmetode - vi vælger én ekstern facet af polytopen som den ydre side af de tre- dimensionel indlejring og fikser positionen af hjørnerne i tredimensionelt rum. De resterende hjørner af polyhedronen kan flyttes, og kanterne kan erstattes af fjedre (eller gummisnore). Lad os nu finde konfigurationen af fjedresystemet med minimal energi. Som de viste, vil det på denne måde opnåede ligningssystem igen være ikke-degenereret, men det er fortsat uklart, under hvilke forhold denne metode vil finde en indlejring, hvor alle polyederens flader er konvekse [7] .
Det faktum, at enhver simpel plan graf kan tegnes med lige kanter, kaldes Fareys sætning [8] . Tutts "gummipakning"-sætning beviser dette for 3-forbundne plane grafer, men Fareys teorem gælder for alle plane grafer uanset tilslutningsmuligheder. Anvendelse af Tutts sætning for grafer, der ikke er 3-forbundne, kan føre til degeneration, hvor undergrafer af en given graf smelter sammen i et punkt eller et segment. En hvilken som helst plan graf kan dog tegnes med Tutts indlejring ved at tilføje ekstra kanter for at gøre den 3-forbundet, derefter tegne den 3-forbundne graf og fjerne de ekstra kanter fra den.
En graf er toppunkt - k -forbundet (men ikke nødvendigvis plan), hvis og kun hvis den har en indlejring i et ( k −1)-dimensionelt rum, hvor ethvert sæt af k hjørner er placeret ved hjørnerne af simplekset , og for enhver resterende toppunkt v de konvekse skrognaboer til v har fuld dimension og v er placeret inde i denne skal. Hvis der findes en sådan indlejring, kan den findes ved at fiksere positionen af k toppunkter og løse ligningssystemet. Løsningen placerer hvert toppunkt på et sted, der er naboernes gennemsnitlige position, ligesom Tutts plane indlejring [9] .
I finite element meshing er Laplace- udglatning en almindelig metode til efterbehandling af det resulterende mesh for at forbedre kvaliteten [10] og er især populær til firkantede masker, hvor andre metoder, såsom Lloyd's algoritme til udglatning af trekantet masker, er mindre anvendelige. I denne metode er hvert toppunkt i retning af den gennemsnitlige position af naboernes positioner, men denne bevægelse udføres i et lille antal iterationer for at undgå stor forvrængning af elementstørrelserne, eller (i tilfælde af en ikke- konveks maskeområde) bliver sammenfiltrede ikke-plane masker.
Grafstablingskraftmetoder er fortsat en populær metode til grafvisualisering, men disse systemer bruger typisk mere komplekse kraftsystemer, der kombinerer tiltrækkende kræfter fra grafkanter (som i Tutts indlejring) med frastødende kræfter mellem to vilkårlige par af hjørner. Disse yderligere kræfter kan give systemet mange lokale stabile konfigurationer i stedet for en global, som i Tuttas indlejring [11] .