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

การฝังแบบแบนราบจะไม่มีลิงก์โดยอัตโนมัติ แต่ในทางกลับกันจะไม่เป็นเช่นนั้น^{[ 2 ]}กราฟสมบูรณ์K ₆กราฟPetersenและกราฟอีกห้ากราฟในตระกูล Petersenไม่มีการฝังแบบไม่มีลิงก์^{[ 1 ]}กราฟย่อยทุก กราฟ ของกราฟที่ฝังแบบไม่มีลิงก์ได้ จะสามารถฝังแบบไม่มีลิงก์ได้อีกครั้ง^{[ 3 ]}เช่นเดียวกับกราฟทุกกราฟที่สามารถเข้าถึงได้จากกราฟที่ฝังแบบไม่มีลิงก์ได้โดย การ แปลงYΔ- และ ΔY- ^{[ 2 ]}กราฟที่ฝังแบบไม่มีลิงก์ได้มี กราฟ ในตระกูล Petersenเป็นกราฟย่อยที่ต้องห้าม [ ^{4 ]}และรวมถึงกราฟระนาบและกราฟจุดยอด^{[ 2 ]} กราฟ เหล่านี้สามารถจดจำได้ และสามารถสร้างการฝังแบบแบนราบสำหรับกราฟเหล่านี้^{ได้ภายใน} O ( n ² ) [ ^{5 ]}

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

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

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

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

กล่าวกันว่ากราฟมีการเชื่อมโยงโดยเนื้อแท้ หากไม่ว่าจะฝังอย่างไร การฝังก็จะมีการเชื่อมโยงเสมอ แม้ว่าการฝังแบบไม่มีการเชื่อมโยงและการฝังแบบแบนจะไม่เหมือนกัน แต่กราฟที่มีการฝังแบบไม่มีการเชื่อมโยงก็เหมือนกับกราฟที่มีการฝังแบบแบน^{[ 8 ]}

ดังที่Sachs (1983)แสดงให้เห็น กราฟทั้งเจ็ดของตระกูล Petersen นั้นเชื่อมโยงกันโดยเนื้อแท้ ไม่ว่ากราฟแต่ละกราฟจะฝังอยู่ในพื้นที่อย่างไร ก็จะมีวงจรสองวงที่เชื่อมโยงกัน กราฟเหล่านี้ได้แก่กราฟสมบูรณ์K ₆กราฟPetersenกราฟที่เกิดจากการลบขอบออกจากกราฟสองส่วนสมบูรณ์K _4,4และกราฟสามส่วนสมบูรณ์ K _3,3,1

กราฟระนาบทุก กราฟ มีการฝังแบบแบนราบและไม่มีลิงก์: เพียงแค่ฝังกราฟลงในระนาบและฝังระนาบลงในอวกาศ หากกราฟเป็นระนาบ นี่เป็นวิธีเดียวที่จะฝังกราฟลงในอวกาศแบบแบนราบและไม่มีลิงก์ได้: การฝังแบบแบนราบทุกแบบสามารถเปลี่ยนรูปได้อย่างต่อเนื่องเพื่อให้วางอยู่บนระนาบแบนราบ และในทางกลับกัน กราฟที่ไม่มีลิงก์ที่ไม่ใช่ระนาบทุกกราฟมีการฝังแบบไม่มีลิงก์หลายแบบ^{[ 2 ]}

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

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

ถ้ากราฟGมีการฝังแบบไม่มีลิงก์หรือแบบแบนราบ ไมเนอร์ทุกตัวของG (กราฟที่เกิดจากการหดตัวของขอบและการลบขอบและจุดยอด) ก็จะมีการฝังแบบไม่มีลิงก์หรือแบบแบนราบเช่นกัน การลบไม่สามารถทำลายความแบนราบของการฝังได้ และการหดตัวสามารถทำได้โดยการทิ้งจุดปลายด้านหนึ่งของขอบที่หดตัวไว้ในตำแหน่งเดิม และกำหนดเส้นทางใหม่ของขอบทั้งหมดที่เชื่อมต่อกับจุดปลายอีกด้านหนึ่งตามเส้นทางของขอบที่หดตัว ดังนั้น ตามทฤษฎีบทของ Robertson–Seymourกราฟที่ฝังแบบไม่มีลิงก์ได้จะมีลักษณะกราฟต้องห้ามเป็นกราฟที่ไม่มีไมเนอร์ชุดจำกัดใดๆ^{[ 3 ]}

ชุดของไมเนอร์ต้องห้ามสำหรับกราฟที่ฝังตัวได้โดยไม่มีการเชื่อมโยงนั้นถูกระบุโดยSachs (1983)ได้แก่ กราฟทั้งเจ็ดของตระกูล Petersenซึ่งล้วนเป็นกราฟที่เชื่อมโยงกันโดยเนื้อแท้และมีไมเนอร์น้อยที่สุด อย่างไรก็ตาม Sachs ไม่สามารถพิสูจน์ได้ว่ากราฟเหล่านี้เป็นกราฟที่เชื่อมโยงกันน้อยที่สุดเพียงกราฟเดียว และในที่สุดRobertson, Seymour & Thomas (1995) ก็สามารถพิสูจน์ได้สำเร็จ

การกำหนดลักษณะย่อยที่ต้องห้ามของกราฟที่ไม่มีลิงก์นำไปสู่ขั้นตอน วิธีที่ใช้ เวลาพหุนามสำหรับการระบุ แต่ไม่ใช่สำหรับการสร้างการฝังตัวจริง ๆKawarabayashi, Kreutzer & Mohar (2010)อธิบายขั้นตอนวิธีที่ใช้เวลาเชิงเส้นที่ทดสอบว่ากราฟสามารถฝังตัวแบบไม่มีลิงก์ได้หรือไม่ และถ้าได้ ก็จะสร้างการฝังตัวแบบระนาบของกราฟ ขั้นตอนวิธีนี้ค้นหากราฟย่อยแบบระนาบขนาดใหญ่ภายในกราฟที่กำหนด ซึ่งหากมีการฝังตัวแบบไม่มีลิงก์อยู่ การฝังตัวนั้นจะต้องเคารพการฝังตัวแบบระนาบของกราฟย่อยนั้น โดยการลดความซับซ้อนของกราฟซ้ำ ๆ ทุกครั้งที่พบกราฟย่อยดังกล่าว พวกเขาลดปัญหาลงเหลือปัญหาที่กราฟที่เหลือมีtreewidth ที่จำกัด ซึ่งในจุดนั้นสามารถแก้ไขได้ด้วย การ เขียน โปรแกรมแบบไดนามิก

ปัญหาของการทดสอบอย่างมีประสิทธิภาพว่าการฝังที่กำหนดนั้นเป็นแบบแบนหรือไม่มีลิงก์นั้นถูกตั้งขึ้นโดยRobertson, Seymour & Thomas (1993a)ปัญหานี้ยังคงไม่ได้รับการแก้ไข และมีความซับซ้อนเทียบเท่ากับปัญหาการแก้ปมซึ่งเป็นปัญหาของการทดสอบว่าเส้นโค้งเดียวในอวกาศนั้นไม่มีปม^{[ 5 ]}การทดสอบว่าไม่มีปม (และด้วยเหตุนี้ การทดสอบว่าการฝังไม่มีลิงก์) เป็นที่ทราบกันว่าอยู่ในNPแต่ไม่เป็นที่ทราบกันว่าเป็นNP- complete ^{[ 9 ]}

ค่าคงที่ กราฟColin de Verdièreคือจำนวนเต็มที่กำหนดขึ้นสำหรับกราฟใดๆ โดยใช้ทฤษฎีกราฟเชิงพีชคณิตกราฟที่มีค่าคงที่กราฟ Colin de Verdière ไม่เกิน μ สำหรับค่าคงที่ μ ใดๆ จะก่อตัวเป็นตระกูลปิดไมเนอร์ และกราฟกลุ่มแรกๆ เหล่านี้เป็นที่รู้จักกันดี ได้แก่ กราฟที่มี μ ≤ 1 คือป่าเชิงเส้น (การรวมกันแบบไม่ทับซ้อนของเส้นทาง) กราฟที่มี μ ≤ 2 คือกราฟระนาบนอกและกราฟที่มี μ ≤ 3 คือกราฟระนาบดังที่Robertson, Seymour & Thomas (1993a)ตั้งข้อสันนิษฐานและLovász & Schrijver (1998)พิสูจน์แล้ว กราฟที่มี μ ≤ 4 คือกราฟที่ฝังได้โดยไม่มีลิงก์

กราฟระนาบและกราฟยอดสามารถฝังได้โดยไม่มีการเชื่อมโยง เช่นเดียวกับกราฟที่ได้จากการแปลง YΔ- และ ΔY-จากกราฟเหล่านี้^{[ 2 ]}กราฟที่ลดรูปได้ YΔYคือกราฟที่สามารถลดรูปให้เหลือเพียงจุดยอดเดียวได้โดยการแปลง YΔ- และ ΔY- การลบจุดยอดที่แยกเดี่ยวและจุดยอดที่มีดีกรีหนึ่ง และการบีบอัดจุดยอดที่มีดีกรีสอง นอกจากนี้ยังปิดไมเนอร์ และรวมถึงกราฟระนาบทั้งหมด อย่างไรก็ตาม มีกราฟที่ไม่มีการเชื่อมโยงซึ่งไม่สามารถลดรูปได้ YΔY เช่น กราฟยอดที่เกิดจากการเชื่อมต่อจุดยอดกับจุดยอดที่มีดีกรีสามทุกจุดของทรง สิบสองเหลี่ยม รูปสี่เหลี่ยมขนมเปียกปูน^{[ 10 ]}นอกจากนี้ยังมีกราฟที่ไม่มีลิงก์ซึ่งไม่สามารถแปลงเป็นกราฟยอดโดยการแปลง YΔ- และ ΔY- การลบจุดยอดที่แยกเดี่ยวและจุดยอดที่มีดีกรีหนึ่ง และการบีบอัดจุดยอดที่มีดีกรีสอง ตัวอย่างเช่นกราฟมงกุฎ สิบจุดยอด มีการฝังแบบไม่มีลิงก์ แต่ไม่สามารถแปลงเป็นกราฟยอดด้วยวิธีนี้ได้^{[ 2 ]}

แนวคิดที่เกี่ยวข้องกับการฝังแบบไร้ลิงก์คือแนวคิดของการฝังแบบไร้ปม ซึ่งเป็นการฝังกราฟในลักษณะที่ไม่มีวงจรแบบง่ายใด ๆ ก่อให้เกิดปมที่ ไม่ธรรมดา กราฟที่ไม่มีการฝังแบบไร้ปม (นั่นคือ กราฟเหล่านั้นมีปมโดยเนื้อแท้ ) ได้แก่K ₇และK _3,3,1,1 ^{[ 11 ]}อย่างไรก็ตาม ยังมีไมเนอร์ต้องห้ามขั้นต่ำสำหรับการฝังแบบไร้ปมที่ไม่เกิดขึ้น (เช่นเดียวกับกราฟทั้งสองนี้) โดยการเพิ่มจุดยอดหนึ่งจุดลงในกราฟที่มีลิงก์โดยเนื้อแท้ แต่รายชื่อของสิ่งเหล่านี้ยังไม่เป็นที่รู้จัก^{[ 12 ]}

นอกจากนี้ยังสามารถกำหนดตระกูลกราฟได้โดยการมีอยู่หรือไม่มีอยู่ของปมและลิงก์ที่ซับซ้อนกว่าในการฝังตัว^{[ 13 ]}หรือโดยการฝังตัวแบบไม่มีลิงก์ในแมนิโฟลด์สามมิติอื่นที่ไม่ใช่ปริภูมิยุคลิด^{[ 14 ]} Flapan, Naimi & Pommersheim (2001)กำหนดการฝังตัวของกราฟว่าเป็นแบบเชื่อมโยงสามเท่าหากมีวงจรสามวงซึ่งไม่มีวงใดสามารถแยกออกจากอีกสองวงได้ พวกเขาแสดงให้เห็นว่าK ₉ไม่ใช่แบบเชื่อมโยงสามเท่าโดยเนื้อแท้ แต่K ₁₀เป็น^{[ 15 ]}โดยทั่วไปแล้ว สามารถกำหนดการ ฝังตัวแบบเชื่อมโยง nสำหรับn ใดๆ ก็ได้ ว่าเป็นการฝังตัวที่มี ลิงก์ nองค์ประกอบที่ไม่สามารถแยกออกจากกันด้วยทรงกลมเชิงทอพอโลยีเป็นสองส่วนที่แยกจากกันได้ กราฟขั้นต่ำสุดที่เป็น แบบเชื่อมโยง n โดยเนื้อแท้ เป็นที่รู้จักสำหรับnทั้งหมด^{[ 16 ]}

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

คำถามที่ว่าK ₆มีการฝังแบบไร้ลิงก์หรือแบบแบนหรือไม่นั้น ถูกตั้งขึ้นในแวดวงวิจัยโทโพโลยี ในช่วงต้นทศวรรษ 1970 โดย Bothe (1973)การฝังแบบไร้ลิงก์ได้รับความสนใจจาก แวดวง ทฤษฎีกราฟโดยHorst Sachs  ( 1983 ) ซึ่งได้ตั้งปัญหาที่เกี่ยวข้องหลายประการ รวมถึงปัญหาการค้นหาลักษณะเฉพาะของกราฟต้องห้ามสำหรับกราฟที่มีการฝังแบบไร้ลิงก์และแบบแบน Sachs แสดงให้เห็นว่ากราฟทั้งเจ็ดในตระกูล Petersen (รวมถึงK ₆ ) ไม่มีกราฟฝังแบบนั้น ดังที่Nešetřil & Thomas (1985)สังเกต กราฟที่สามารถฝังแบบไร้ลิงก์ได้นั้นปิดภายใต้กราฟไมเนอร์ซึ่งจากทฤษฎีบท Robertson–Seymour ทำให้สรุปได้ ว่ามีลักษณะเฉพาะของกราฟต้องห้ามอยู่จริง การพิสูจน์การมีอยู่ของเซตจำกัดของกราฟสิ่งกีดขวางไม่ได้นำไปสู่คำอธิบายที่ชัดเจนของเซตของไมเนอร์ต้องห้ามนี้ แต่เป็นผลมาจากผลลัพธ์ของ Sachs ที่ว่ากราฟทั้งเจ็ดของตระกูล Petersen เป็นส่วนหนึ่งของเซตนี้ ปัญหาเหล่านี้ได้รับการแก้ไขในที่สุดโดย^Robertson , Seymour & Thomas (1995) [ ^{18 ]}ซึ่งแสดงให้เห็นว่ากราฟทั้งเจ็ดของตระกูล Petersen เป็นไมเนอร์ต้องห้ามขั้นต่ำเพียงอย่างเดียวสำหรับกราฟเหล่านี้ ดังนั้น กราฟที่ฝังได้โดยไม่มีลิงก์และกราฟที่ฝังได้แบบแบนจึงเป็นเซตของกราฟเดียวกัน และเหมือนกันกับกราฟที่ไม่มีไมเนอร์ของตระกูล Petersen

Sachs (1983)ยังได้ขอขอบเขตของจำนวนขอบและจำนวนสีของกราฟฝังตัวแบบไม่มีลิงก์อีกด้วย จำนวนขอบใน กราฟแบบไม่มีลิงก์ที่มี nจุดยอดมีค่าสูงสุด4n  − 10: กราฟยอดสูงสุด ที่มีn > 4 _จะ  มีขอบจำนวนเท่านี้พอดี^{[ 1 ]}และMader (1968)ได้พิสูจน์ขอบเขตบนที่ตรงกันบนคลาสทั่วไปของกราฟที่ไม่มีไมเนอร์K6 Nešetřil & Thomas (1985)สังเกตว่าคำถามของ Sachs เกี่ยวกับจำนวนสีจะได้รับการแก้ไขโดยการพิสูจน์ข้อสันนิษฐานของ Hadwiger ที่ว่ากราฟ k -chromatic ใดๆ จะมี กราฟสมบูรณ์k จุดยอด เป็นไมเนอร์การพิสูจน์โดยRobertson, Seymour & Thomas (1993c)ในกรณีk  = 6 ของข้อสันนิษฐานของ Hadwiger นั้นเพียงพอที่จะยุติคำถามของ Sachs ได้ กล่าวคือ กราฟที่ไม่มีลิงก์สามารถระบายสีได้ด้วยสีอย่างมากที่สุดห้าสี เนื่องจากกราฟ 6-chromatic ใดๆ ก็ตามจะมี ไมเนอร์ K ₆และไม่ใช่กราฟที่ไม่มีลิงก์ และยังมีกราฟที่ไม่มีลิงก์เช่นK ₅ที่ต้องใช้ห้าสีทฤษฎีบท snark บ่งชี้ว่ากราฟลูกบาศก์ ที่ฝังได้โดยไม่มีลิงก์ทุกกราฟสามารถระบายสีขอบ ได้ ด้วย 3 สี

การฝังแบบไร้ลิงก์เริ่มได้รับการศึกษาใน ชุมชนวิจัย อัลกอริทึมในช่วงปลายทศวรรษ 1980 ผ่านผลงานของFellows & Langston (1988)และMotwani, Raghunathan & Saran (1988)ในเชิงอัลกอริทึม ปัญหาของการจดจำกราฟที่ฝังได้แบบไร้ลิงก์และแบนราบได้รับการแก้ไขเมื่อมีการพิสูจน์ลักษณะเฉพาะของไมเนอร์ต้องห้าม: อัลกอริทึมของRobertson & Seymour (1995)สามารถใช้เพื่อทดสอบในเวลาพหุนามว่ากราฟที่กำหนดมีไมเนอร์ต้องห้ามเจ็ดรายการใดหรือไม่^{[ 19 ]}วิธีนี้ไม่ได้สร้างการฝังแบบไร้ลิงก์หรือแบนราบเมื่อมีอยู่ แต่อัลกอริทึมที่สร้างการฝังได้รับการพัฒนาโดยvan der Holst (2009)และอัลกอริทึมที่มีประสิทธิภาพมากขึ้นในเวลาเชิงเส้นถูกค้นพบโดยKawarabayashi, Kreutzer & Mohar (2010 )

คำถามสุดท้ายของSachs (1983)เกี่ยวกับความเป็นไปได้ของทฤษฎีบทที่คล้ายคลึงกับทฤษฎีบทของ Fáryสำหรับกราฟที่ไม่มีการเชื่อมโยง ดูเหมือนจะยังไม่มีคำตอบ: เมื่อใดที่การมีอยู่ของการฝังแบบไม่มีการเชื่อมโยงหรือแบบแบนราบที่มีขอบโค้งหรือ ขอบ เชิงเส้นเป็นช่วงๆจะบ่งชี้ถึงการมีอยู่ของการฝังแบบไม่มีการเชื่อมโยงหรือแบบแบนราบซึ่งขอบเป็นส่วนของเส้น ตรง ?