Tutt-inbäddningen ( barycentrisk inbäddning ) av en enkel 3-vertex-kopplad plan graf är en inbäddning utan skärningar med linjesegment med de ytterligare egenskaperna att den yttre ytan har en konvex polygon som sin gräns och att varje inre vertex är det geometriska centrumet av dess grannar. Om den yttre polygonen är fixerad, bestämmer detta tillstånd på de inre hörnen deras positioner unikt som en lösning på ett system av linjära ekvationer . Lösning av ekvationerna ger en plan inbäddning . Tutts "gummipackning" -sats säger att det aldrig finns kantskärningar i en enda lösning och, mer strikt, att vilken yta som helst av den resulterande plana inbäddningen är konvex [1] . En inbäddning kallas "gummi"-inbäddning eftersom en sådan inbäddning kan hittas som en jämviktsposition för ett system av fjädrar eller gummiband som representerar grafens kanter.
Låt G vara en kubgraf. Låt oss fixa (genom att välja en av de fyrkantiga ytorna som den yttre ytan) fyra hörn på den yttre ytan vid hörnen av enhetskvadraten , vars x- och y -koordinater är kombinationer av nollor och ettor. De återstående fyra hörnen är sedan placerade vid fyra punkter vars x- och y -koordinater är kombinationer av 1/3 och 2/3, som visas i figuren. Resultatet är Tutts inbäddning. För varje inre hörn v av denna inbäddning har de tre närliggande hörnen tre koordinatvärden (både x och y ), en lika med v- koordinaten , en mindre och den andra 1/3 större. I genomsnitt får vi värdet på koordinaten för själva punkten v .
Villkoret att en vertex v har medelvärdet av sina grannars koordinater kan uttryckas som två linjära ekvationer , en för x -koordinaten till v , den andra för y -koordinaten . För en graf med n hörn, varav h är fixerade vid yttersidans hörn, finns det två ekvationer och två okända (koordinater) för varje inre vertex. Således får vi ett system av linjära ekvationer med 2( n − h ) ekvationer i 2( n − h ) okända, vars lösning är Tutt-inbäddningen. Som Tatt [2] visade är detta system inte degenererat för 3-vertex-anslutna plana grafer. Därför kommer systemet att ha en unik lösning och (med fast ytterkant) blir grafen Tutts enda inbäddning. Denna inbäddning kan hittas i polynomtid genom att lösa ett ekvationssystem, till exempel genom att använda sekventiell eliminering av variabler [3] .
Enligt Steinitz sats är 3-kopplade plana grafer för vilka Tutts "gummiläggande" sats gäller samma som polyedriska grafer , graferna som bildas av hörn och kanter på en konvex polyeder . Enligt Maxwell-Cremont-metoden bildar en tvådimensionell inbäddning av en plan graf en projektion av en tredimensionell konvex polyeder om och endast om inbäddningen har en jämviktsspänning , fördelningen av krafter för varje kant (i båda ändarna av kanterna i motsatta riktningar parallella med kanterna), så att krafterna vid varje vertex balanseras . För Tutt-inbäddningen är kraftfördelningen för varje kant proportionell mot kantens längd (liknande ett gummiband) och balanserar krafterna vid alla inre punkter, men inte vid hörn av den yttre polygonen. Om den yttre polygonen är en triangel, kan du tilldela repulsiva krafter på de tre yttre kanterna för att balansera krafterna vid hörn av den yttre triangeln. Således kan Tutts inbäddning användas för att hitta Schlegel-diagrammen för vilken konvex polyeder som helst . För varje 3-kopplad plan graf G har antingen grafen G själv eller dess dual en triangel, så att vi får en polyedrisk representation av grafen G eller dess dual. I fallet när den dubbla grafen har en triangulär yta, ger den polära konjugationen en polyedrisk representation av själva grafen G [3] .
Gortler, Gottsman och Thurston [4] visade resultat liknande Tutts "gummipackning"-sats för grafinbäddningar i en torus [5] .
Chilacamarri, Dean och Litman [6] studerade en tredimensionell inbäddning av grafer av fyrdimensionella polytoper , bildade med samma metod som i Tutts inbäddningsmetod - vi väljer en yttre fasett av polytopen som den yttre sidan av tre- dimensionell inbäddning och fixera topparnas position i tredimensionellt utrymme. De återstående hörnen på polyedern kan flyttas och kanterna kan ersättas av fjädrar (eller gummisnören). Låt oss nu hitta konfigurationen av fjädersystemet med minimal energi. Som de visade kommer ekvationssystemet som erhålls på detta sätt återigen att vara icke-degenererat, men det är fortfarande oklart under vilka förhållanden denna metod kommer att finna en inbäddning där alla ytor på polyedern är konvexa [7] .
Det faktum att vilken enkel plan graf som helst kan ritas med raka kanter kallas Fareys sats [8] . Tutts "gummipackning"-sats bevisar detta för 3-kopplade plana grafer, men Fareys teorem är sant för alla plana grafer oavsett anslutning. Tillämpning av Tutts teorem för grafer som inte är 3-kopplade kan leda till degeneration, där subgrafer av en given graf smälter samman till en punkt eller ett segment. Men vilken plan graf som helst kan ritas med Tutts inbäddning genom att lägga till extra kanter för att göra den 3-kopplad, sedan rita den 3-anslutna grafen och ta bort de extra kanterna från den.
En graf är vertex - k -ansluten (men inte nödvändigtvis plan) om och bara om den har en inbäddning i ett ( k −1)-dimensionellt utrymme där vilken som helst uppsättning av k hörn är belägen vid hörnen av simplexen , och för eventuell återstående vertex v de konvexa skrovgrannarna till v har full dimension och v är belägen inuti detta skal. Om en sådan inbäddning finns kan den hittas genom att fixera positionen för k hörn och lösa ekvationssystemet. Lösningen placerar varje vertex på en plats som är den genomsnittliga positionen för grannarna, precis som Tutts plana inbäddning [9] .
I finita element meshing är Laplace smoothing en vanlig metod för att efterbearbeta det resulterande nätet för att förbättra kvaliteten [10] och är särskilt populärt för fyrsidiga maskor, för vilka andra metoder, såsom Lloyds algoritm för utjämning av triangulära maskor, är mindre tillämpliga. I denna metod är varje vertex i riktning mot den genomsnittliga positionen för grannarnas positioner, men denna rörelse utförs i ett litet antal iterationer för att undvika stor förvrängning av elementstorlekarna, eller (i fallet med en icke- konvext nätområde) får intrasslade icke-plana nät.
Metoder för stapling av grafer fortsätter att vara en populär metod för grafvisualisering, men dessa system använder vanligtvis mer komplexa kraftsystem som kombinerar attraktionskrafter från grafkanter (som i Tutts inbäddning) med repulsiva krafter mellan två godtyckliga par av hörn. Dessa ytterligare krafter kan ge systemet många lokala stabila konfigurationer snarare än en global, som i Tuttas inbäddning [11] .