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

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

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

กราฟแบบไม่มีทิศทางเป็นระบบของจุดยอดและขอบโดยแต่ละขอบเชื่อมต่อจุดยอดสองจุดเข้าด้วยกัน ดังเช่นที่พบได้ทั่วไปในทฤษฎีกราฟ สำหรับวัตถุประสงค์ของทฤษฎีบทของ Steinitz กราฟเหล่านี้จะต้องจำกัดให้เป็นกราฟจำกัด (จุดยอดและขอบเป็นเซตจำกัด ) และกราฟแบบง่าย (ไม่มีขอบสองเส้นใดเชื่อมต่อจุดยอดสองจุดเดียวกัน และไม่มีขอบใดเชื่อมต่อจุดยอดกับตัวมันเอง) จากรูปทรงหลายเหลี่ยมใดๆ เราสามารถสร้างกราฟได้ โดยให้จุดยอดของกราฟสอดคล้องกับจุดยอดของรูปทรงหลายเหลี่ยม และโดยการเชื่อมต่อจุดยอดสองจุดใดๆ ของกราฟด้วยขอบ เมื่อใดก็ตามที่จุดยอดสองจุดที่สอดคล้องกันของรูปทรงหลายเหลี่ยมเป็นจุดปลายของขอบของรูปทรงหลายเหลี่ยม กราฟนี้เรียกว่าโครงร่างของรูปทรงหลายเหลี่ยม^{[ 7 ]}

กราฟเรียกว่ากราฟระนาบถ้าสามารถวาดกราฟได้โดยให้จุดยอดเป็นจุดบนระนาบยุคลิดและขอบเป็นเส้นโค้งที่เชื่อมต่อจุดเหล่านี้ โดยที่ไม่มีเส้นโค้งของขอบสองเส้นใดตัดกัน และจุดที่แทนจุดยอดจะอยู่บนเส้นโค้งที่แทนขอบก็ต่อเมื่อจุดยอดนั้นเป็นจุดปลายของขอบเท่านั้น ตามทฤษฎีบทของ Fáryภาพวาดระนาบทุกภาพสามารถทำให้ตรงได้ โดยที่เส้นโค้งที่แทนขอบเป็นส่วนของเส้นตรงกราฟเรียกว่ากราฟ3-เชื่อมต่อถ้ามีจุดยอดมากกว่าสามจุด และหลังจากลบจุดยอดสองจุดใดๆ ออกไปแล้ว จุดยอดคู่ใดๆ ที่เหลือยังคงเชื่อมต่อกันด้วยเส้นทาง ทฤษฎีบทของ Steinitz กล่าวว่าเงื่อนไขทั้งสองนี้เป็นทั้งเงื่อนไขที่จำเป็นและเพียงพอที่จะกำหนดลักษณะของโครงร่างของทรงหลายเหลี่ยมนูนสามมิติ: กราฟที่กำหนดเป็นกราฟของทรงหลายเหลี่ยมนูนสามมิติ ก็ต่อเมื่อเป็นกราฟระนาบและเชื่อมต่อจุดยอด 3 จุด^{[ 5 ] [ 8 ]}${\displaystyle G}$${\displaystyle G}$

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

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

แม้ว่าบทพิสูจน์ดั้งเดิมของสไตน์นิทซ์จะไม่ได้แสดงออกมาในรูปของทฤษฎีกราฟ แต่ก็สามารถเขียนใหม่ได้ในรูปเหล่านั้น และเกี่ยวข้องกับการค้นหาลำดับของการแปลง ΔY และ YΔที่ลดกราฟระนาบ 3-เชื่อมต่อใดๆ ให้เหลือเพียงกราฟของทรงสี่เหลี่ยมพีระมิด การแปลง YΔ จะลบจุดยอดที่มีดีกรีสามออกจากกราฟ และเพิ่มขอบระหว่างจุดยอดข้างเคียงเดิมทั้งหมด หากขอบเหล่านั้นยังไม่มีอยู่ การแปลงย้อนกลับ การแปลง ΔY จะลบขอบของรูปสามเหลี่ยมออกจากกราฟและแทนที่ด้วยจุดยอดที่มีดีกรีสามใหม่ที่อยู่ติดกับจุดยอดทั้งสามนั้น เมื่อพบลำดับดังกล่าวแล้ว ก็สามารถย้อนกลับและแปลงเป็นการดำเนินการทางเรขาคณิตที่สร้างทรงหลายเหลี่ยมที่ต้องการทีละขั้นตอนโดยเริ่มจากทรงสี่เหลี่ยมพีระมิด การแปลง YΔ แต่ละครั้งในลำดับย้อนกลับสามารถทำได้ทางเรขาคณิตโดยการตัดจุดยอดที่มีดีกรีสามออกจากทรงหลายเหลี่ยม การแปลง ΔY ในลำดับย้อนกลับสามารถทำได้ทางเรขาคณิตโดยการลบหน้าสามเหลี่ยมออกจากรูปทรงหลายเหลี่ยมและขยายหน้าข้างเคียงจนถึงจุดที่หน้าเหล่านั้นมาบรรจบกัน แต่เฉพาะเมื่อจุดตัดสามจุดของหน้าข้างเคียงทั้งสามนั้นอยู่ด้านไกลของหน้าที่ถูกลบออกจากรูปทรงหลายเหลี่ยมเท่านั้น เมื่อจุดตัดสามจุดไม่ได้อยู่ด้านไกลของหน้านั้นการแปลงเชิงฉายของรูปทรงหลายเหลี่ยมก็เพียงพอที่จะย้ายไปยังด้านที่ถูกต้อง ดังนั้น โดยการอุปมานเกี่ยวกับจำนวนการแปลง ΔY และ YΔ ที่จำเป็นในการลดกราฟที่กำหนดให้เป็น กราฟรูปทรงหลายเหลี่ยมทุกกราฟสามารถทำให้เป็นจริงได้เป็นรูปทรงหลายเหลี่ยม^{[ 5 ]}${\displaystyle K_{4}}$${\displaystyle K_{4}}$

งานในภายหลังของ Epifanov ได้เสริมความแข็งแกร่งให้กับการพิสูจน์ของ Steinitz ที่ว่ากราฟทรงหลายเหลี่ยมทุกกราฟสามารถลดรูปได้โดยการแปลง ΔY และ YΔ Epifanov พิสูจน์ว่าหากระบุจุดยอดสองจุดในกราฟระนาบ กราฟนั้นสามารถลดรูปให้เหลือขอบเดียวระหว่างจุดปลายเหล่านั้นได้โดยการรวมการแปลง ΔY และ YΔ เข้ากับการลดรูปอนุกรม-ขนาน [ ^{10 ] การ}พิสูจน์ของ Epifanov นั้นซับซ้อนและไม่สร้างสรรค์ แต่ได้รับการทำให้ง่ายขึ้นโดย Truemper โดยใช้วิธีการที่อิงตามกราฟไมเนอร์ Truemper สังเกตว่า กราฟกริดทุก กราฟ สามารถลดรูปได้โดยการแปลง ΔY และ YΔ ในลักษณะนี้ ความสามารถในการลดรูปนี้ได้รับการรักษาไว้โดยกราฟไมเนอร์ และกราฟระนาบทุกกราฟเป็นไมเนอร์ของกราฟกริด^{[ 11 ]}แนวคิดนี้สามารถใช้แทนที่เลมมาของ Steinitz ที่ว่าลำดับการลดรูปมีอยู่จริง หลังจากเปลี่ยนแล้ว ส่วนที่เหลือของการพิสูจน์สามารถดำเนินการได้โดยใช้การเหนี่ยวนำในลักษณะเดียวกับการพิสูจน์ดั้งเดิมของ Steinitz ^{[ 8 ]}สำหรับการพิสูจน์เหล่านี้ ซึ่งดำเนินการโดยใช้วิธีการใดๆ ในการค้นหาลำดับของการแปลง ΔY- และ YΔ- จะมีกราฟทรงหลายเหลี่ยมที่ต้องใช้จำนวนขั้นตอนที่ไม่เป็นเชิงเส้น กล่าวคือ กราฟระนาบทุกกราฟสามารถลดขนาดได้โดยใช้จำนวนขั้นตอนไม่เกินสัดส่วนกับและกราฟจำนวนอนันต์ต้องใช้จำนวนขั้นตอนอย่างน้อยเป็นสัดส่วนกับโดยที่คือจำนวนจุดยอดในกราฟ^{[ 12 ] [ 13 ]}${\displaystyle K_{4}}$${\displaystyle n^{3/2}}$${\displaystyle n^{3/2}}$${\displaystyle n}$

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

ความเค้นสมดุลบนกราฟของลูกบาศก์

รูปทรงกรวยตัดที่ยกภาพวาดที่เน้นความเครียด (โดยใช้ตำแหน่ง 2 มิติเดิม) ขึ้นสู่มิติ 3 มิติ

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

การสอดคล้องของ Maxwell–Cremona ถูกนำมาใช้เพื่อให้ได้การสร้างรูปทรงหลายเหลี่ยมของกราฟหลายเหลี่ยมโดยการรวมเข้ากับ วิธี การวาดกราฟ ระนาบ ของWT Tutteซึ่งก็คือการฝัง Tutteวิธีการของ Tutte เริ่มต้นด้วยการตรึงหน้าหนึ่งของกราฟหลายเหลี่ยมไว้ในตำแหน่งนูนบนระนาบ หน้านี้จะกลายเป็นหน้าด้านนอกของการวาดกราฟ วิธีการนี้ดำเนินต่อไปโดยการตั้งระบบสมการเชิงเส้นในพิกัดจุดยอด ซึ่งแต่ละจุดยอดที่เหลือควรถูกวางไว้ที่ค่าเฉลี่ยของเพื่อนบ้าน จากนั้นดังที่ Tutte ได้แสดงให้เห็น ระบบสมการนี้จะมีคำตอบที่ไม่ซ้ำกันซึ่งแต่ละหน้าของกราฟจะถูกวาดเป็นรูปหลายเหลี่ยมนูน^{[ 17 ]}โดยสัญชาตญาณ คำตอบนี้อธิบายรูปแบบที่จะได้รับโดยการแทนที่ขอบภายในของกราฟด้วยสปริงในอุดมคติและปล่อยให้พวกมันตั้งตัวในสถานะพลังงานต่ำสุด^{[ 18 ]}ผลลัพธ์ที่ได้เกือบจะเป็นความเค้นสมดุล: หากกำหนดน้ำหนักหนึ่งให้กับขอบภายในแต่ละด้าน จุดยอดภายในแต่ละจุดของภาพวาดจะอยู่ในสมดุล อย่างไรก็ตาม การกำหนดตัวเลขลบให้กับขอบภายนอกเพื่อให้ขอบเหล่านั้นอยู่ในสมดุลด้วยนั้นไม่ใช่เรื่องที่เป็นไปได้เสมอไป การกำหนดเช่นนี้เป็นไปได้เสมอเมื่อด้านนอกเป็นรูปสามเหลี่ยม ดังนั้นวิธีนี้จึงสามารถใช้สร้างกราฟทรงหลายเหลี่ยมใดๆ ที่มีหน้าเป็นรูปสามเหลี่ยมได้ หากกราฟทรงหลายเหลี่ยมไม่มีหน้าเป็นรูปสามเหลี่ยม กราฟคู่ ของมัน จะมีรูปสามเหลี่ยมและเป็นกราฟทรงหลายเหลี่ยมเช่นกัน ดังนั้นจึงสามารถสร้างกราฟคู่ในลักษณะนี้แล้วสร้างกราฟดั้งเดิมเป็นทรงหลายเหลี่ยมขั้วของการสร้างกราฟคู่ได้^{[ 4 ] [ 19 ]}วิธีการอื่นในการสร้างทรงหลายเหลี่ยมโดยใช้การยกจะหลีกเลี่ยงความเป็นคู่โดยการเลือกหน้าใดๆ ที่มีจุดยอดไม่เกินห้าจุดเป็นด้านนอก กราฟทรงหลายเหลี่ยมทุกกราฟจะมีหน้าดังกล่าว และโดยการเลือกรูปร่างคงที่ของหน้าดังกล่าวอย่างระมัดระวังมากขึ้น การฝัง Tutte ของกราฟที่เหลือสามารถยกขึ้นได้^{[ 20 ]}

ตามทฤษฎีบทการบรรจุวงกลม แบบหนึ่ง สำหรับกราฟทรงหลายเหลี่ยมทุกกราฟ จะมีระบบวงกลมในระนาบหรือบนทรงกลมใดๆ ที่แทนจุดยอดและหน้าของกราฟ โดยที่:

• จุดยอดที่อยู่ติดกันสองจุดของกราฟจะถูกแทนด้วยวงกลมสัมผัส
• แต่ละหน้าคู่ที่อยู่ติดกันของกราฟจะถูกแทนด้วยวงกลมสัมผัส
• แต่ละคู่ของจุดยอดและหน้าสัมผัสจะถูกแทนด้วยวงกลมที่ตัดกันเป็นมุมฉากและ
• วงกลมคู่อื่นๆ ทั้งหมดจะแยกออกจากกัน^{[ 21 ]}

ระบบวงกลมเดียวกันนี้สร้างการแสดงแทนของกราฟคู่โดยการสลับบทบาทของวงกลมที่แทนจุดยอดและวงกลมที่แทนหน้า จากการแสดงแทนดังกล่าวบนทรงกลมที่ฝังอยู่ในปริภูมิยูคลิดสามมิติ เราสามารถสร้างรูปทรงหลายเหลี่ยมนูนที่เทียบเท่าเชิงการจัดเรียงกับกราฟที่กำหนดได้ โดยเป็นการตัดกันของครึ่งพื้นที่ที่มีขอบเขตผ่านวงกลมของหน้า จากจุดยอดแต่ละจุดของรูปทรงหลายเหลี่ยมนี้ขอบฟ้าบนทรงกลมที่มองจากจุดยอดนั้นคือวงกลมที่แทนจุดยอดนั้น คุณสมบัติของขอบฟ้าจะกำหนดตำแหน่งสามมิติของแต่ละจุดยอด และรูปทรงหลายเหลี่ยมสามารถกำหนดได้อย่างเทียบเท่ากับเปลือกนูนของจุดยอดที่จัดวางในลักษณะนี้ ทรงกลมกลายเป็นทรงกลมกลางของการสร้าง: ขอบแต่ละด้านของรูปทรงหลายเหลี่ยมสัมผัสกับทรงกลม ณ จุดที่วงกลมจุดยอดสัมผัสสองวงตัดกับวงกลมหน้าสัมผัสสองวง^{[ 22 ]}

เป็นไปได้ที่จะพิสูจน์ทฤษฎีบทของ Steinitz ในรูปแบบที่แข็งแกร่งกว่า โดยที่กราฟทรงหลายเหลี่ยมใดๆ ก็สามารถสร้างขึ้นได้ด้วยทรงหลายเหลี่ยมนูนที่มีพิกัดเป็นจำนวนเต็ม [ ^{23 ] ตัวอย่าง}เช่น การพิสูจน์แบบอุปนัยดั้งเดิมของ Steinitz สามารถเสริมความแข็งแกร่งได้ด้วยวิธีนี้ อย่างไรก็ตาม จำนวนเต็มที่ได้จากการสร้างของ Steinitz นั้นเป็นเลขชี้กำลังสองเท่าของจำนวนจุดยอดของกราฟทรงหลายเหลี่ยมที่กำหนด การเขียนตัวเลขขนาดนี้ลงในสัญกรณ์ไบนารีจะต้องใช้จำนวนบิตที่เป็นเลขชี้กำลัง^{[ 19 ]}ในทางเรขาคณิต หมายความว่าคุณลักษณะบางอย่างของทรงหลายเหลี่ยมอาจมีขนาดใหญ่กว่าคุณลักษณะอื่นๆ เป็นเลขชี้กำลังสองเท่า ทำให้การสร้างที่ได้จากวิธีนี้มีปัญหาสำหรับการใช้งานใน การ วาดกราฟ^{[ 4 ]}

นักวิจัยรุ่นต่อมาได้ค้นพบอัลกอริธึมการสร้างแบบยกกำลังที่ใช้บิตจำนวนเชิงเส้นต่อจุดยอดเท่านั้น^{[ 20 ] [ 24 ]}นอกจากนี้ยังสามารถผ่อนปรนข้อกำหนดที่ว่าพิกัดต้องเป็นจำนวนเต็ม และกำหนดพิกัดในลักษณะที่พิกัด- ของจุดยอดเป็นจำนวนเต็มที่แตกต่างกันในช่วงตั้งแต่ 0 ถึงและพิกัดอีกสองพิกัดเป็นจำนวนจริงในช่วงหน่วยเพื่อให้แต่ละขอบมีความยาวอย่างน้อยหนึ่ง ในขณะที่ทรงหลายเหลี่ยมโดยรวมมีปริมาตรเชิงเส้น^{[ 25 ] [ 26 ]}กราฟทรงหลายเหลี่ยมบางชนิดเป็นที่ทราบกันว่าสามารถสร้างได้บนกริดที่มีขนาดพหุนามเท่านั้น โดยเฉพาะอย่างยิ่งในกรณีของพีระมิด (การสร้างกราฟวงล้อ ) ปริซึม (การสร้างกราฟปริซึม ) และทรงหลายเหลี่ยมซ้อนกัน (การสร้างเครือข่ายอพอลโลเนียน ) ^{[ 27 ]}${\displaystyle x}$${\displaystyle 2n-4}$

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

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

ในทรงหลายเหลี่ยมใดๆ ที่แสดงถึงกราฟทรงหลายเหลี่ยมที่กำหนดให้หน้าของ ทรงหลายเหลี่ยมนั้น ก็คือวงจรใน ทรงหลายเหลี่ยม นั้นเองที่ไม่แยกออกเป็นสองส่วน กล่าวคือ การลบวงจรหน้าออกจากทรงหลายเหลี่ยมจะทำให้ส่วนที่เหลือของทรงหลายเหลี่ยมยังคงเป็นกราฟย่อยที่เชื่อมต่อกัน วงจรดังกล่าวเรียกว่าวงจรส่วนปลายดังนั้น โครงสร้างเชิงการจัดเรียงของหน้า (แต่ไม่ใช่รูปทรงเรขาคณิต) จึงถูกกำหนดอย่างไม่ซ้ำกันจากโครงสร้างของกราฟ การเสริมความแข็งแกร่งอีกประการหนึ่งของทฤษฎีบทของสไตน์นิทซ์โดยบาร์เน็ตต์และกรุนบอมกล่าวว่า สำหรับกราฟทรงหลายเหลี่ยมใดๆ หน้าใดๆ ของกราฟ และรูปหลายเหลี่ยมนูนใดๆ ที่แสดงถึงหน้านั้น เป็นไปได้ที่จะหาการสร้างทรงหลายเหลี่ยมของกราฟทั้งหมดที่มีรูปร่างที่กำหนดสำหรับหน้าที่กำหนด สิ่งนี้เกี่ยวข้องกับทฤษฎีบทของทุตต์ที่ว่า กราฟทรงหลายเหลี่ยมใดๆ สามารถวาดลงบนระนาบได้โดยที่ทุกหน้าเป็นรูปนูนและมีรูปร่างที่กำหนดสำหรับหน้านอก อย่างไรก็ตามภาพวาดกราฟ บนระนาบ ที่สร้างขึ้นโดยวิธีของทุตต์ไม่จำเป็นต้องยกขึ้นเป็นทรงหลายเหลี่ยมนูนเสมอไป แต่ Barnette และ Grünbaum พิสูจน์ผลลัพธ์นี้โดยใช้วิธีการอุปนัย^{[ 30 ]} นอกจากนี้ ยังเป็นไปได้เสมอ ที่จะหาการสร้างภาพสำหรับกราฟทรงหลายเหลี่ยมและวัฏจักรใดๆใน ซึ่ง สร้างเงาของการสร้างภาพภายใต้ การ ฉายแบบขนาน^{[ 31 ]}${\displaystyle G}$${\displaystyle G}$${\displaystyle G}$${\displaystyle G}$${\displaystyle G}$${\displaystyle G}$${\displaystyle G}$${\displaystyle C}$${\displaystyle G}$${\displaystyle C}$

การสร้างรูปทรงหลายเหลี่ยมโดยใช้ทฤษฎีบทการบรรจุวงกลมเป็นการเสริมความแข็งแกร่งอีกประการหนึ่งของทฤษฎีบทของ Steinitz: กราฟระนาบที่เชื่อมต่อ 3 ทุกกราฟสามารถแสดงเป็นรูปทรงหลายเหลี่ยมแบบนูนได้ในลักษณะที่ขอบทั้งหมดของกราฟสัมผัสกับทรงกลมหน่วย เดียวกัน ซึ่งก็คือทรงกลมกลางของรูปทรงหลายเหลี่ยม^{[ 22 ]}โดยการทำการแปลงโมเบียส ที่เลือกอย่างระมัดระวัง ของการบรรจุวงกลมก่อนที่จะแปลงเป็นรูปทรงหลายเหลี่ยม เป็นไปได้ที่จะหาการสร้างรูปทรงหลายเหลี่ยมที่สร้างสมมาตรทั้งหมดของกราฟพื้นฐาน ในแง่ที่ว่าการ แปลง กราฟอัตโนมัติ ทุกแบบ เป็นสมมาตรของการสร้างรูปทรงหลายเหลี่ยม^{[ 32 ] [ 33 ]}โดยทั่วไปแล้ว ถ้าเป็นกราฟรูปทรงหลายเหลี่ยม และ เป็น ทรงนูนสามมิติเรียบใดๆ ก็สามารถหาการแสดงรูปทรงหลายเหลี่ยมของซึ่งขอบทั้งหมดสัมผัสกับได้^{[ 34 ]}${\displaystyle G}$${\displaystyle K}$${\displaystyle G}$${\displaystyle K}$

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

ในมิติใดๆ ที่สูงกว่าสามมิติปัญหา Steinitz เชิงอัลกอริทึมประกอบด้วยการพิจารณาว่าแลตทิซ ที่กำหนด เป็นแลตทิซหน้าของโพลีโทปนูนหรือไม่ ไม่น่าจะมีความซับซ้อนของเวลาพหุนาม เนื่องจากเป็น ปัญหา NP-hardและสมบูรณ์ แบบยิ่งขึ้น สำหรับทฤษฎีการมีอยู่ของจำนวนจริงแม้แต่สำหรับโพลีโทปสี่มิติ ตามทฤษฎีสากลของ Richter-Gebert ^{[ 38 ]}ในที่นี้ ทฤษฎีการมีอยู่ของจำนวนจริงเป็นกลุ่มของปัญหาการคำนวณที่สามารถกำหนดได้ในแง่ของการค้นหาตัวแปรจริงที่สอดคล้องกับระบบสมการและอสมการพหุนามที่กำหนด สำหรับปัญหา Steinitz เชิงอัลกอริทึม ตัวแปรของปัญหาดังกล่าวอาจเป็นพิกัดจุดยอดของโพลีโทป และสมการและอสมการสามารถใช้เพื่อระบุความเรียบของแต่ละหน้าในแลตทิซหน้าที่กำหนดและความนูนของแต่ละมุมระหว่างหน้า ความสมบูรณ์หมายความว่าปัญหาอื่นๆ ทุกปัญหาในคลาสนี้สามารถแปลงเป็นอินสแตนซ์ที่เทียบเท่าของปัญหา Steinitz เชิงอัลกอริทึมได้ในเวลาพหุนาม การมีอยู่ของการแปลงดังกล่าวบ่งชี้ว่า หากปัญหา Steinitz เชิงอัลกอริทึมมีวิธีแก้ปัญหาในเวลาพหุนาม ปัญหาทุกปัญหาในทฤษฎีการมีอยู่ของจำนวนจริงและปัญหาทุกปัญหาใน NP ก็มีวิธีแก้ปัญหาในเวลา พหุนามเช่นกัน ^{[ 39 ]}อย่างไรก็ตาม เนื่องจากกราฟที่กำหนดอาจสอดคล้องกับแลตทิซหน้ามากกว่าหนึ่งรายการ จึงเป็นการยากที่จะขยายผลลัพธ์ความสมบูรณ์นี้ไปยังปัญหาการจดจำกราฟจุดยอด-ขอบของโพลีโทป 4 มิติ การกำหนดความซับซ้อนในการคำนวณของปัญหาการจดจำกราฟนี้ยังคงเปิดอยู่^{[ 40 ]}

นักวิจัยยังพบลักษณะเฉพาะทางทฤษฎีกราฟของกราฟของโพลีเฮดราสามมิติที่ไม่นูนบางประเภทพิเศษ^{[ 37 ] [ 41 ]}และโพลีโทปนูนสี่มิติ^{[ 40 ] [ 42 ] [ 43 ]}อย่างไรก็ตาม ในทั้งสองกรณี ปัญหาทั่วไปยังคงไม่ได้รับการแก้ไข อันที่จริง แม้แต่ปัญหาในการกำหนดว่ากราฟสมบูรณ์ ใด เป็นกราฟของโพลีเฮดราที่ไม่นูน (นอกเหนือจากเตตระเฮดรอนและโพลีเฮดรอน Császár ) ก็ยังไม่ได้รับการแก้ไข^{[ 44 ]}${\displaystyle K_{4}}$${\displaystyle K_{7}}$

ทฤษฎีบทของ Eberhardอธิบายลักษณะบางส่วนของมัลติเซตของรูปหลายเหลี่ยมที่สามารถรวมกันเพื่อสร้างหน้าของทรงหลายเหลี่ยมนูนได้ สามารถพิสูจน์ได้โดยการสร้างกราฟระนาบที่เชื่อมต่อ 3 จุดด้วยเซตของหน้ารูปหลายเหลี่ยมที่กำหนด จากนั้นใช้ทฤษฎีบทของ Steinitz เพื่อหาการสร้างทรงหลายเหลี่ยมของกราฟนั้น^{[ 3 ]}

László Lovászได้แสดงให้เห็นถึงความสอดคล้องกันระหว่างการแสดงกราฟแบบทรงหลายเหลี่ยมและเมทริกซ์ที่สร้างค่าคงที่ของกราฟ Colin de Verdière ค่าคงที่ของ Colin de Verdière คือค่า corank สูงสุด ของเมทริกซ์ประชิด แบบถ่วงน้ำหนัก ของกราฟ ภายใต้เงื่อนไขเพิ่มเติมบางประการที่ไม่เกี่ยวข้องกับกราฟทรงหลายเหลี่ยม เงื่อนไขเหล่านี้เป็นเมทริกซ์สมมาตร จัตุรัส ที่มีดัชนีเป็นจุดยอด โดยมีน้ำหนักของจุดยอดอยู่ในสัมประสิทธิ์แนวทแยงและมีน้ำหนักของขอบอยู่ในสัมประสิทธิ์นอกแนวทแยงเมื่อจุดยอดและไม่ติดกัน สัมประสิทธิ์จะต้องเป็นศูนย์ ค่าคงที่นี้จะมีค่าอย่างมากที่สุดสามก็ต่อเมื่อกราฟนั้นเป็นกราฟระนาบดังที่ Lovász แสดงให้เห็น เมื่อกราฟเป็นรูปทรงหลายเหลี่ยม การแสดงผลของกราฟนั้นในรูปของรูปทรงหลายเหลี่ยมสามารถทำได้โดยการหาเมทริกซ์ประชิดแบบถ่วงน้ำหนักที่มีอันดับร่วมสาม การหาเวกเตอร์สามตัวที่สร้างฐานสำหรับปริภูมิว่างการใช้สัมประสิทธิ์ของเวกเตอร์เหล่านี้เป็นพิกัดสำหรับจุดยอดของรูปทรงหลายเหลี่ยม และการปรับขนาดจุดยอดเหล่านี้อย่างเหมาะสม^{[ 45 ]}${\displaystyle i}$${\displaystyle M_{i,i}}$${\displaystyle i,j}$${\displaystyle M_{i,j}}$${\displaystyle M_{j,i}}$${\displaystyle i}$${\displaystyle j}$${\displaystyle M_{i,j}}$

ประวัติของทฤษฎีบทของ Steinitz ได้รับการอธิบายโดยGrünbaum (2007) [ ^{46 ] ซึ่งบันทึกการปรากฏตัวครั้ง แรก}ในรูปแบบที่คลุมเครือในสิ่งพิมพ์ของErnst Steinitzซึ่งเขียนขึ้นครั้งแรกในปี 1916 ^{[ 6 ]} Steinitz ได้ให้รายละเอียดเพิ่มเติมในบันทึกการบรรยายในภายหลัง ซึ่งตีพิมพ์หลังจากการเสียชีวิตของเขาในปี 1928 แม้ว่าการวิเคราะห์ทฤษฎีบทของ Steinitz ในปัจจุบันจะระบุว่าเป็นลักษณะเฉพาะของรูปทรงหลายเหลี่ยมในเชิงทฤษฎีกราฟ แต่ Steinitz ไม่ได้ใช้ภาษาของกราฟ^{[ 46 ]}การกำหนดทฤษฎีบทในเชิงทฤษฎีกราฟได้รับการแนะนำในช่วงต้นทศวรรษ 1960 โดยBranko GrünbaumและTheodore Motzkinโดยมีการแปลงการพิสูจน์เป็นทฤษฎีกราฟในตำราConvex Polytopes ของ Grünbaum ในปี 1967 ด้วย ^{[ 46 ]}งานของ Epifanov เกี่ยวกับการแปลง ΔY- และ YΔ-ซึ่งเสริมความแข็งแกร่งให้กับการพิสูจน์ของ Steinitz ได้รับแรงบันดาลใจจากปัญหาอื่นนอกเหนือจากลักษณะเฉพาะของโพลีเฮดราTruemper (1989)ยกย่อง Grünbaum ที่สังเกตเห็นความเกี่ยวข้องของงานนี้กับทฤษฎีบทของ Steinitz ^{[ 11 ]}

ความสอดคล้องระหว่างแผนภาพความเค้นและการยกทรงหลายเหลี่ยมของ Maxwell-Cremona ได้รับการพัฒนาในชุดเอกสารโดยJames Clerk Maxwellตั้งแต่ปี 1864 ถึง 1870 โดยอิงจากงานก่อนหน้าของPierre Varignon , William Rankineและคนอื่นๆ และได้รับความนิยมในช่วงปลายศตวรรษที่ 19 โดยLuigi Cremona [ ^{47 ] ข้อ}สังเกตที่ว่าความสอดคล้องนี้สามารถใช้กับTutte embeddingเพื่อพิสูจน์ทฤษฎีบทของ Steinitz มาจากEades & Garvan (1995) ^[ 4 ^]ดูเพิ่มเติมที่Richter-Gebert (1996 ) ^{[ 38 ]}

ทฤษฎีบทการบรรจุวงกลมได้รับการพิสูจน์โดยPaul Koebeในปี 1936 ^{[ 48 ] [ 49 ]}และ (โดยอิสระ) โดย EM Andreev ในปี 1970 ^{[ 49 ] [ 50 ]} ทฤษฎีบท นี้ได้รับความนิยมในช่วงกลางทศวรรษ 1980 โดยWilliam Thurstonซึ่ง (แม้จะอ้างถึง Koebe และ Andreev) มักได้รับการยกย่องว่าเป็นหนึ่งในผู้ค้นพบ^{[ 49 ]}ทฤษฎีบทเวอร์ชันของ Andreev ได้รับการกำหนดรูปแบบแล้วเป็นลักษณะเฉพาะแบบ Steinitz สำหรับทรงหลายเหลี่ยมบางรูปในปริภูมิไฮเปอร์โบลิก [ ^{50 ] และการใช้การบรรจุวงกลมเพื่อ สร้าง}ทรงหลายเหลี่ยมที่มีทรงกลมตรงกลางมาจากงานของ Thurston ^{[ 51 ]}ปัญหาของการกำหนดลักษณะของทรงหลายเหลี่ยมที่มีทรงกลมแนบในหรือล้อมรอบ ซึ่งในที่สุดก็ได้รับการแก้ไขโดยใช้วิธีการที่อิงตามการจัดเรียงวงกลม ย้อนกลับไปถึงงานที่ไม่ได้ตีพิมพ์ของเรเน่ เดส์การ์ตส์ราวปี 1630 ^{[ 52 ]}และยาคอบ สไตเนอร์ในปี 1832 ^{[ 35 ] [ 53 ]}ตัวอย่างแรกของทรงหลายเหลี่ยมที่ไม่มีการสร้างด้วยทรงกลมล้อมรอบหรือทรงกลมแนบในนั้นได้มาจากสไตนิทซ์ในปี 1928 ^{[ 35 ] [ 54 ]}