ในการวาดกราฟและทฤษฎีกราฟเชิงเรขาคณิตการฝังแบบ Tutteหรือการฝังแบบ barycentricของกราฟ ระนาบ แบบง่ายที่ มีจุดยอด เชื่อมต่อ 3 จุดคือการฝังแบบเส้นตรงที่ไม่มีจุดตัดโดยมีคุณสมบัติว่าด้านนอกเป็นรูปหลายเหลี่ยมแบบนูนและจุดยอด ภายในแต่ละจุด อยู่ที่ค่าเฉลี่ย (หรือ barycenter) ของตำแหน่งจุดยอดข้างเคียง หากรูปหลายเหลี่ยมด้านนอกคงที่ เงื่อนไขนี้สำหรับจุดยอดภายในจะกำหนดตำแหน่งของจุดยอดเหล่านั้นได้อย่างไม่ซ้ำกัน ซึ่งเป็นคำตอบของระบบสมการเชิงเส้นการแก้สมการเชิงเรขาคณิตจะสร้างการฝังแบบระนาบทฤษฎีบทสปริงของ Tutte ซึ่งพิสูจน์โดยWT Tutte  ( 1963 ) ระบุว่าคำตอบที่ไม่ซ้ำกันนี้จะไม่มีจุดตัดเสมอ และที่สำคัญกว่านั้นคือทุกด้านของการฝังแบบระนาบที่ได้จะเป็นแบบนูน^{[ 1 ]}เรียกว่าทฤษฎีบทสปริงเพราะการฝังแบบนี้สามารถพบได้ในตำแหน่งสมดุลสำหรับระบบสปริงที่แสดงถึงขอบของกราฟ

ให้Gเป็นกราฟของลูกบาศก์ และ (เลือกหน้าสี่เหลี่ยมด้านใดด้านหนึ่งเป็นด้านนอก) กำหนดจุดยอดทั้งสี่ของด้านนอกไว้ที่มุมทั้งสี่ของสี่เหลี่ยมจัตุรัสหน่วย ซึ่งเป็นจุดที่ มีพิกัด xและyเป็นค่าผสมของศูนย์และหนึ่งทั้งสี่ค่า จากนั้น ถ้าจุดยอดที่เหลืออีกสี่จุดถูกวางไว้ที่จุดที่มี พิกัด xและyเป็นค่าผสมของ 1/3 และ 2/3 ดังแสดงในรูป ผลลัพธ์ที่ได้จะเป็นการฝังแบบ Tutte เพราะที่จุดยอดภายในแต่ละจุดvของการฝัง และสำหรับแต่ละพิกัดทั้งสอง จุดข้างเคียงสามจุดของvจะมีค่าพิกัดเท่ากับvน้อยกว่า 1/3 และมากกว่า 1/3 ค่าเฉลี่ยของค่าเหล่านี้จะเท่ากับค่าพิกัดของvเอง

เงื่อนไขที่ว่าจุดยอดvอยู่ที่ตำแหน่งเฉลี่ยของจุดยอดข้างเคียง สามารถแสดงได้ด้วยสมการเชิงเส้น สองสมการ สมการ หนึ่งสำหรับ พิกัด x  ของ  vและอีกสมการหนึ่งสำหรับ พิกัด y  ของ  vสำหรับกราฟที่มีจุดยอดn จุด โดยที่ hจุดนั้นถูกตรึงไว้บนหน้าด้านนอก จะมีสองสมการสำหรับแต่ละจุดยอดภายใน และยังมีตัวแปรที่ไม่ทราบค่าสองตัว (พิกัด) สำหรับแต่ละจุดยอดภายในด้วย ดังนั้นจึงได้ระบบสมการเชิงเส้นที่มี 2( n  −  h ) สมการใน 2( n  −  h ) ตัวแปรที่ไม่ทราบค่า ซึ่งคำตอบของระบบนี้คือการฝังตัวแบบ Tutte ดังที่Tutte (1963)ได้แสดงให้เห็น สำหรับกราฟระนาบที่เชื่อมต่อกันด้วยจุดยอด 3 จุด ระบบนี้ไม่เสื่อมสภาพ ดังนั้นจึงมีคำตอบที่ไม่ซ้ำกัน และ (เมื่อหน้าด้านนอกถูกตรึงไว้) กราฟจะมีการฝังตัวแบบ Tutte ที่ไม่ซ้ำกัน การฝังตัวนี้สามารถหาได้ในเวลาพหุนามโดยการแก้ระบบสมการ ตัวอย่างเช่น โดยใช้การกำจัดแบบเกาส์เซียน^{[ 2 ]}

ตามทฤษฎีบทของสไตน์นิทซ์กราฟระนาบ 3-เชื่อมต่อที่ทฤษฎีบทสปริงของทุตต์ใช้ได้นั้น ตรงกับกราฟทรงหลายเหลี่ยมซึ่งเป็นกราฟที่เกิดจากจุดยอดและขอบของทรงหลายเหลี่ยมนูนตามการจับคู่ของแม็กซ์เวลล์-เครโมนาการฝังกราฟระนาบสองมิติจะสร้างภาพฉายแนวตั้งของทรงหลายเหลี่ยมนูนสามมิติก็ต่อเมื่อการฝังนั้นมีแรงเค้นสมดุลซึ่งเป็นการกำหนดแรงให้กับแต่ละขอบ (ส่งผลต่อจุดปลายทั้งสองในทิศทางที่เท่ากันและตรงกันข้ามขนานกับขอบ) โดยที่แรงจะหักล้างกันที่ทุกจุดยอด สำหรับการฝังแบบทุตต์ การกำหนดแรงดึงดูดให้กับแต่ละขอบตามสัดส่วนของความยาว (เหมือนสปริง) จะทำให้แรงหักล้างกันที่จุดยอดภายในทั้งหมด แต่สิ่งนี้ไม่จำเป็นต้องเป็นแรงเค้นสมดุลที่จุดยอดของรูปหลายเหลี่ยมภายนอก อย่างไรก็ตาม เมื่อรูปหลายเหลี่ยมภายนอกเป็นรูปสามเหลี่ยม ก็สามารถกำหนดแรงผลักให้กับขอบทั้งสามเพื่อให้แรงหักล้างกันได้เช่นกัน ด้วยวิธีนี้ การฝังแบบ Tutte สามารถใช้เพื่อค้นหาแผนภาพ Schlegelของรูปทรงหลายเหลี่ยมนูน ทุก รูป สำหรับกราฟระนาบ 3-เชื่อมต่อG ทุกกราฟ ไม่ว่าจะ เป็น Gเองหรือกราฟคู่ของGก็มีรูปสามเหลี่ยม ดังนั้นสิ่งนี้จึงให้การแสดงรูปทรงหลายเหลี่ยมของGหรือของกราฟคู่ ในกรณีที่กราฟคู่เป็นกราฟที่มีรูปสามเหลี่ยมการโพลาไรเซชันจะให้การแสดงรูปทรงหลายเหลี่ยมของGเอง^{[ 2 ]}

ในกระบวนการประมวลผลทางเรขาคณิต วิธีการฝังตัวของ Tutte ใช้สำหรับการกำหนดพารามิเตอร์uv แบบ 2 มิติ ของพื้นผิว 3 มิติโดยส่วนใหญ่ใช้ในกรณีที่โทโพโลยีของพื้นผิวยังคงเหมือนเดิม( โทโพโลยีแบบดิสก์) วิธีการของ Tutte ลดพลังงานการบิดเบี้ยวทั้งหมดของพื้นที่พารามิเตอร์โดยพิจารณาจุดยอดที่แปลงแล้วแต่ละจุดเป็นมวลจุด และขอบที่ลากผ่านจุดยอดที่สอดคล้องกันเป็นสปริง ความแน่นของสปริงแต่ละตัวถูกกำหนดโดยความยาวของขอบในพื้นผิว 3 มิติเดิมเพื่อรักษารูปทรง เนื่องจากเป็นการสมเหตุสมผลที่จะมีความยาวขอบพารามิเตอร์ที่สั้นกว่าสำหรับขอบที่เล็กกว่าของและความยาวขอบพารามิเตอร์ที่ยาวกว่าสำหรับขอบที่ใหญ่กว่าของค่าคงที่ของสปริงจึงมักถูกกำหนดให้เป็นส่วนกลับของระยะทางสัมบูรณ์ระหว่างจุดยอดในพื้นที่ 3 มิติ ${\displaystyle {\mathcal {S}}^{*}}$${\displaystyle {\mathcal {S}}}$${\displaystyle {\mathcal {S}}}$${\displaystyle {\mathcal {S}}^{*}}$${\displaystyle {\mathcal {S}}}$${\displaystyle {\mathcal {S}}}$${\displaystyle w_{ij}}$${\displaystyle i,~j}$

${\displaystyle {\text{พลังงานการบิดเบือน,}}~E=\Sigma _{(i,j)\in E({\mathcal {S}})}~w_{ij}~\|{\textbf {u}}_{\text{i}}-{\textbf {u}}_{\text{j}}\|^{2}{\text{, โดยที่ }}w_{ij}={\frac {1}{\|{\textbf {v}__{\text{i}}-{\textbf {v}__{\text{j}}\|}}{\text{, }}\{{\textbf {u}}_{\text{i}}\}\in {\mathcal {S}}^{*}{\text{, }}\{{\textbf {v}}_{\text{i}}\}\in {\mathcal {ส}}}$

โดยที่แทนเซตของขอบในพื้นผิว 3 มิติเดิม เมื่อน้ำหนักเป็นบวก (ดังเช่นในกรณีข้างต้น) จะรับประกันได้ว่าการแมปเป็นแบบหนึ่งต่อหนึ่งโดยไม่มีการผกผันใดๆ แต่เมื่อไม่มีการใช้ข้อจำกัดเพิ่มเติมใดๆ โซลูชันที่ลดพลังงานการบิดเบือนให้น้อยที่สุดจะยุบตัวลงเหลือเพียงจุดเดียวในพื้นที่พารามิเตอร์อย่างง่ายดาย ${\displaystyle E({\mathcal {S}})}$${\displaystyle w_{ij}}$

ดังนั้น จึงจำเป็นต้องกำหนดเงื่อนไขขอบเขต โดยที่ชุดของจุดยอดที่ทราบแล้วบนพื้นผิว 3 มิติ จะถูกแมปไปยังจุดที่ทราบแล้วในพื้นที่พารามิเตอร์ 2 มิติ วิธีทั่วไปในการเลือกเงื่อนไขขอบเขตดังกล่าวคือการพิจารณาจุดยอดบนวงรอบขอบเขตที่ใหญ่ที่สุดของพื้นผิว 3 มิติเดิม ซึ่งสามารถจำกัดให้แมปไปยังวงแหวนด้านนอกของดิสก์หน่วยในพื้นที่พารามิเตอร์ 2 มิติได้ โปรดทราบว่า หากพื้นผิว 3 มิติเป็นแมนิโฟลด์ ขอบเขตสามารถตรวจจับได้โดยการตรวจสอบว่าขอบเขตเหล่านั้นเป็นของหน้าเดียวของตาข่ายเท่านั้น

การประยุกต์ใช้การกำหนดพารามิเตอร์ในงานกราฟิกและแอนิเมชัน ได้แก่ การแมปพื้นผิว และอื่นๆ อีกมากมาย

การฝังแบบ Tutte อาจพิจารณาได้โดยมีน้ำหนักบวกที่ขอบ โดยแต่ละจุดยอดภายในเป็นค่าเฉลี่ยถ่วงน้ำหนักของตำแหน่งของจุดยอดข้างเคียง^{[ 3 ]} Orick, Stephenson & Collins (2017)ได้กำหนดปัญหาของการหาจุดศูนย์กลางของวงกลมในการแสดงการบรรจุวงกลมของกราฟระนาบ โดยกำหนดรัศมีของวงกลม เป็นการฝังแบบ Tutte ที่มีน้ำหนัก โดยคำนวณน้ำหนักจากรัศมีที่กำหนด พวกเขาเขียนว่าถึงแม้ด้านนอกของการฝังของพวกเขาจะไม่จำเป็นต้องเป็นนูนตามที่จำเป็นสำหรับการพิสูจน์ความถูกต้องของการฝังแบบ Tutte แต่ "วิธีการนี้ยังคงใช้งานได้จริง" ^{[ 4 ]}

Colin de Verdière (1991)ได้ขยายทฤษฎีบทสปริงของ Tutte ไปยังกราฟบนพื้นผิวจีนัส ที่สูงกว่า ที่มีความโค้งไม่เป็นบวกโดยที่ขอบถูกแทนด้วยเส้นจีโอ เดสิ ก^{[ 5 ]} ผลลัพธ์นี้ได้รับการค้นพบใหม่โดยอิสระโดย Hass & Scott (2015) ในภายหลัง^[ 6 ] ^{ผลลัพธ์ที่คล้าย} กันสำหรับกราฟที่ฝังอยู่ในทอรัสได้รับการพิสูจน์โดยอิสระโดยDelgado-Friedrichs (2005) [ ^{7 ]} โดยGortler, Gotsman & Thurston (2006) [ ^{8 ]} และโดย Lovász ⁽ 2019 ) ^{[ 9 ]}

Chilakamarri, Dean & Littman (1995) ศึกษาการฝังกราฟสามมิติของกราฟของ โพลีโทปสี่มิติซึ่งสร้างขึ้นโดยวิธีเดียวกับการฝังของ Tutte: เลือกด้านหนึ่งของโพลีโทปเป็นด้านนอกของการฝังสามมิติ และตรึงจุดยอดของด้านนั้นให้อยู่ในตำแหน่งที่เป็นจุดยอดของทรงหลายเหลี่ยมสามมิติในอวกาศ ให้จุดยอดที่เหลือของโพลีโทปเคลื่อนที่ได้อย่างอิสระในอวกาศ และแทนที่ขอบแต่ละด้านของโพลีโทปด้วยสปริง จากนั้น หาการจัดเรียงพลังงานต่ำสุดของระบบสปริง ดังที่พวกเขาแสดงให้เห็น ระบบสมการที่ได้มาในวิธีนี้จะไม่เสื่อมสภาพอีกครั้ง แต่ยังไม่ชัดเจนว่าภายใต้เงื่อนไขใดที่วิธีนี้จะพบการฝังที่ทำให้ทุกด้านของโพลีโทปเป็นทรงหลายเหลี่ยมนูน^{[ 10 ]}

ผลลัพธ์ที่ว่า กราฟระนาบ แบบง่าย ทุก กราฟสามารถวาดได้ด้วยขอบเส้นตรงเรียกว่าทฤษฎีบทของ Fáry ^{[ 11 ]}ทฤษฎีบทสปริงของ Tutte พิสูจน์สิ่งนี้สำหรับกราฟระนาบที่เชื่อมต่อ 3 จุด แต่ผลลัพธ์นี้เป็นจริงโดยทั่วไปสำหรับกราฟระนาบโดยไม่คำนึงถึงการเชื่อมต่อ การใช้ระบบสปริงของ Tutte สำหรับกราฟที่ไม่เชื่อมต่อ 3 จุดอาจส่งผลให้เกิดความเสื่อม ซึ่งกราฟย่อยของกราฟที่กำหนดจะยุบตัวลงบนจุดหรือส่วนของเส้นตรง อย่างไรก็ตาม กราฟระนาบใดๆ ก็สามารถวาดได้โดยใช้การฝัง Tutte โดยการเพิ่มขอบพิเศษเพื่อให้เชื่อมต่อ 3 จุด วาดกราฟที่เชื่อมต่อ 3 จุดที่ได้ และจากนั้นลบขอบพิเศษออก

กราฟจะ เชื่อมต่อกันด้วย kจุดยอดแต่ไม่จำเป็นต้องเป็นกราฟระนาบ ก็ต่อเมื่อมีการฝังตัวแบบนูนลงในปริภูมิมิติ ( k  −1) ซึ่งจุดยอด k ใดๆจะถูกวางไว้ที่จุดยอดของซิมเพล็กซ์และสำหรับจุดยอดที่เหลือแต่ละจุดvเปลือกนูนของเพื่อนบ้านของ  vจะมีมิติเต็มโดยมีvอยู่ภายใน หากมีการฝังตัวดังกล่าวอยู่ ก็สามารถหาได้โดยการกำหนดตำแหน่งของ จุดยอด k ที่เลือกไว้ และแก้ระบบสมการที่วางจุดยอดแต่ละจุดไว้ที่ค่าเฉลี่ยของเพื่อนบ้าน เช่นเดียวกับการฝังตัวแบบระนาบของ Tutte ^{[ 12 ]}

ในการสร้างตาข่ายองค์ประกอบจำกัด การ ปรับเรียบแบบลาปลาเซียนเป็นวิธีการทั่วไปสำหรับการประมวลผลหลังการสร้างตาข่ายเพื่อปรับปรุงคุณภาพขององค์ประกอบ^{[ 13 ]}โดยเฉพาะอย่างยิ่งเป็นที่นิยมสำหรับตาข่ายรูปสี่เหลี่ยมซึ่งวิธีการอื่น ๆ เช่นอัลกอริทึมของลอยด์สำหรับการปรับเรียบตาข่ายรูปสามเหลี่ยมนั้นใช้ได้น้อยกว่า ในวิธีนี้ จุดยอดแต่ละจุดจะถูกย้ายไปยังหรือเข้าหาค่าเฉลี่ยของตำแหน่งของจุดยอดข้างเคียง แต่การเคลื่อนที่นี้จะดำเนินการเพียงจำนวนรอบเล็กน้อย เพื่อหลีกเลี่ยงการบิดเบือนขนาดขององค์ประกอบอย่างมาก หรือ (ในกรณีของโดเมนตาข่ายที่ไม่นูน) ตาข่ายที่ไม่เป็นระนาบที่พันกันยุ่งเหยิง

ระบบ การวาดกราฟแบบใช้แรงดึงดูดยังคงเป็นวิธีการที่นิยมใช้ในการแสดงภาพกราฟ แต่ระบบเหล่านี้มักใช้ระบบแรงที่ซับซ้อนกว่าซึ่งรวมแรงดึงดูดบนขอบกราฟ (เช่นเดียวกับการฝังตัวของ Tutte) กับแรงผลักระหว่างจุดยอดคู่ใดๆ แรงเพิ่มเติมเหล่านี้อาจทำให้ระบบมีการกำหนดค่าที่เสถียรในระดับท้องถิ่นหลายแบบ แทนที่จะเป็นโซลูชันระดับโลกเพียงโซลูชันเดียว เช่นเดียวกับการฝังตัวของ Tutte ^{[ 14 ]}