ในทฤษฎีกราฟปัญหาการทดสอบความเป็นกราฟระนาบคือ ปัญหา เชิงอัลกอริทึมในการทดสอบว่ากราฟที่กำหนดให้เป็นกราฟระนาบ หรือ ไม่ (กล่าวคือ สามารถวาดกราฟนั้นลงบนระนาบได้โดยไม่มีจุดตัดของเส้นขอบหรือไม่) นี่เป็นปัญหาที่ได้รับการศึกษาอย่างดีในวิทยาศาสตร์คอมพิวเตอร์ซึ่งมีอัลกอริทึมเชิงปฏิบัติมากมาย เกิดขึ้น โดยหลาย อัลกอริทึมใช้ประโยชน์จากโครงสร้างข้อมูล ใหม่ๆ วิธีการส่วนใหญ่เหล่านี้ทำงานในเวลาO ( n ) (เวลาเชิงเส้น) โดยที่ nคือจำนวนเส้นขอบ (หรือจุดยอด) ในกราฟ ซึ่งเป็นเวลาที่เหมาะสมที่สุดในเชิงอะซิมโทติกแทนที่จะเป็นเพียงค่าบูลีนค่าเดียว ผลลัพธ์ของอัลกอริทึมการทดสอบความเป็นกราฟระนาบอาจเป็นการฝังกราฟ ระนาบ หากกราฟเป็นกราฟระนาบ หรือเป็นอุปสรรคต่อความเป็นกราฟระนาบ เช่นกราฟย่อย Kuratowskiหากกราฟนั้นไม่ใช่ กราฟระนาบ

โดยทั่วไปแล้ว อัลกอริทึมการทดสอบความเป็นระนาบจะใช้ประโยชน์จากทฤษฎีบทในทฤษฎีกราฟที่อธิบายลักษณะของเซตของกราฟระนาบในแง่ที่ไม่ขึ้นอยู่กับการวาดกราฟ ซึ่งรวมถึง...

• ทฤษฎีบทของคุราตอฟสกีกล่าวว่า กราฟจะเป็นกราฟระนาบก็ต่อเมื่อกราฟนั้นไม่มีกราฟย่อยที่เป็นส่วนย่อยของK ₅ ( กราฟสมบูรณ์บนจุดยอด ห้าจุด ) หรือK _3,3 ( กราฟยูทิลิตี้ ซึ่งเป็นกราฟสองส่วนสมบูรณ์บนจุดยอดหกจุด โดยสามจุดเชื่อมต่อกับอีกสามจุด)
• ทฤษฎีบทของแวกเนอร์ กล่าวว่า กราฟจะเป็นกราฟระนาบก็ต่อเมื่อ กราฟนั้นไม่มีไมเนอร์ (กราฟย่อยของการหดตัว) ที่สมมาตรกับK ₅หรือK _3,3
• เกณฑ์ความเรียบของกราฟแบบ Fraysseix –Rosenstiehlเป็นเกณฑ์ที่ใช้ในการจำแนกกราฟระนาบโดยพิจารณาจากการเรียงลำดับจากซ้ายไปขวาของขอบใน ต้นไม้ ค้นหาแบบเจาะลึก (depth-first search tree)

เกณฑ์ความเรียบของ Fraysseix–Rosenstiehl สามารถนำมาใช้โดยตรงเป็นส่วนหนึ่งของอัลกอริธึมสำหรับการทดสอบความเรียบ ในขณะที่ทฤษฎีบทของ Kuratowski และ Wagner มีการประยุกต์ใช้ทางอ้อม: หากอัลกอริธึมสามารถค้นหาสำเนาของK ₅หรือK _3,3ภายในกราฟที่กำหนดได้ ก็จะมั่นใจได้ว่ากราฟอินพุตไม่ใช่กราฟระนาบและส่งคืนค่าโดยไม่ต้องคำนวณเพิ่มเติม

เกณฑ์อื่นๆ ที่ใช้ในการกำหนดลักษณะของกราฟระนาบทางคณิตศาสตร์ แต่มีความสำคัญน้อยกว่าในอัลกอริธึมการทดสอบความเป็นกราฟระนาบ ได้แก่:

• เกณฑ์ความเรียบของกราฟของวิทนีย์ที่ระบุว่า กราฟจะเป็นกราฟระนาบก็ต่อเมื่อเมทริกซ์กราฟิก ของกราฟนั้น เป็นเมทริกซ์ร่วมกราฟิกด้วย
• เกณฑ์ความเป็นระนาบของ Mac Laneซึ่งจำแนกกราฟระนาบโดยฐานของ ปริภูมิวัฏจักรของ กราฟ เหล่า นั้น
• ทฤษฎีบทของ Schnyderที่อธิบายลักษณะของกราฟระนาบโดยมิติลำดับของลำดับย่อย ที่เกี่ยวข้อง และ
• เกณฑ์ความราบเรียบของ Colin de Verdièreโดยใช้ทฤษฎีกราฟเชิงสเปกตรัม

วิธี การเพิ่มเส้นทางแบบคลาสสิกของHopcroftและTarjan ^{[ 1 ]}เป็นอัลกอริทึมการทดสอบระนาบแบบเชิงเส้นเวลาแรกที่เผยแพร่ในปี 1974 การใช้งานอัลกอริทึมของHopcroftและTarjanมีให้ในLibrary of Efficient Data types and AlgorithmsโดยMehlhorn , MutzelและNäher ^{[ 2 ] [ 3 ] [ 4 ]}ในปี 2012 Taylor [ ^{5 ]}ได้ขยายอัลกอริทึมนี้เพื่อสร้างการเรียงสับเปลี่ยนทั้งหมดของลำดับขอบแบบวนรอบสำหรับการฝังระนาบของส่วนประกอบที่เชื่อมต่อกันสอง ^ทาง

วิธีการเพิ่มจุดยอดทำงานโดยการรักษาโครงสร้างข้อมูลที่แสดงถึงการฝังที่เป็นไปได้ของกราฟย่อยที่เหนี่ยวนำของกราฟที่กำหนด และเพิ่มจุดยอดทีละจุดลงในโครงสร้างข้อมูลนี้ วิธีการเหล่านี้เริ่มต้นด้วยวิธีการ O(n²) ที่ไม่มีประสิทธิภาพ^ซึ่งคิดค้นโดยLempel , Evenและ Cederbaum ในปี 1967 ^{[ 6 ]}ได้รับการปรับปรุงโดย Even และ Tarjan ซึ่งพบวิธีแก้ปัญหาแบบเชิงเส้นสำหรับขั้นตอนการกำหนดหมายเลขs , t ^{[ 7 ]}และโดยBoothและLuekerซึ่งพัฒนา โครงสร้างข้อมูล ต้นไม้ PQด้วยการปรับปรุงเหล่านี้ ทำให้ใช้เวลาเชิงเส้นและมีประสิทธิภาพเหนือกว่าวิธีการเพิ่มเส้นทางในทางปฏิบัติ^{[ 8 ]}วิธีนี้ยังได้รับการขยายเพื่อให้สามารถคำนวณการฝังแบบระนาบ (การวาด) สำหรับกราฟระนาบได้อย่างมีประสิทธิภาพ^{[ 9 ]}ในปี พ.ศ. 2542 Shih และ Hsu ได้ทำให้วิธีการเหล่านี้ง่ายขึ้นโดยใช้ต้นไม้ PC (รูปแบบที่ไม่มีรากของต้นไม้ PQ) และการท่องต้นไม้ค้นหาเชิงลึกของ จุดยอดตามลำดับหลัง ^{[ 10 ]}

ในปี 2547 John Boyer และWendy Myrvold ^{[ 11 ]}ได้พัฒนาอัลกอริทึม O( n ) ที่เรียบง่ายขึ้น โดยได้รับแรงบันดาลใจจากวิธีการต้นไม้ PQ ซึ่งกำจัดต้นไม้ PQ และใช้การเพิ่มขอบเพื่อคำนวณการฝังแบบระนาบ หากเป็นไปได้ มิฉะนั้น จะคำนวณการแบ่งย่อย Kuratowski (ของK ₅หรือK _3,3 ) อัลกอริทึมนี้เป็นหนึ่งในสองอัลกอริทึมที่ทันสมัยที่สุดในปัจจุบัน (อีกอัลกอริทึมหนึ่งคืออัลกอริทึมการทดสอบความเป็นระนาบของ de Fraysseix, Ossona de Mendez และ Rosenstiehl ^{[ 12 ] [ 13 ]} ) ดู^{[ 14 ]}สำหรับการเปรียบเทียบเชิงทดลองกับเวอร์ชันเบื้องต้นของการทดสอบความเป็นระนาบของ Boyer และ Myrvold นอกจากนี้ การทดสอบ Boyer–Myrvold ยังได้รับการขยายเพื่อดึงการแบ่งย่อย Kuratowski หลายรายการของกราฟอินพุตที่ไม่เป็นระนาบในเวลาการทำงานที่ขึ้นอยู่กับขนาดของเอาต์พุตแบบเชิงเส้น^{[ 15 ]}รหัสต้นฉบับสำหรับการทดสอบระนาบ^{[ 16 ] [ 17 ]}และการสกัดการแบ่งย่อย Kuratowski หลายรายการ^{[ 16 ]}สามารถเข้าถึงได้โดยสาธารณะ อัลกอริทึมที่ระบุตำแหน่งกราฟย่อย Kuratowski ในเวลาเชิงเส้นในจุดยอดได้รับการพัฒนาโดย Williamson ในช่วงทศวรรษ 1980 ^{[ 18 ]}

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

การทดสอบความเรียบของกราฟได้รับการศึกษาใน แบบจำลอง อัลกอริทึมแบบไดนามิกซึ่งยังคงรักษาคำตอบของปัญหา (ในกรณีนี้คือความเรียบของกราฟ) ไว้ในขณะที่กราฟมีการอัปเดตในระดับท้องถิ่น โดยทั่วไปในรูปแบบของการแทรก/ลบขอบ ในกรณีการมาถึงของขอบ มีอัลกอริทึมเวลาอัปเดตฟังก์ชันผกผันของ Ackermann ที่แม่นยำในเชิงอะซิมโท ^ติก โดย La Poutré [ ^{20 ]}ซึ่งปรับปรุงอัลกอริทึมของ Di Battista, Tamassia และ Westbrook ^{[ 21 ] [ 22 ] [ 23 ]}ในกรณีแบบไดนามิกเต็มรูปแบบที่ขอบทั้งถูกแทรกและลบ มีขอบเขตล่างของเวลาอัปเดตแบบลอการิทึมโดยPătrașcuและDemaine [ ^{24 ]}และอัลกอริทึมเวลาอัปเดตแบบพหุลอการิทึมโดยHolm และ Rotenberg [ ^{25 ]ซึ่ง ปรับปรุงอัลกอริทึม เวลา}อัปเดตแบบย่อยเชิงเส้นโดยEppstein , Galil , Italiano , Sarnak และ Spencer ^{[ 26 ] [ 27 ]}