Planarityเป็นเกมคอมพิวเตอร์ปริศนา ปี 2005 โดย John Tantalo ซึ่งอิงตามแนวคิดของ Mary Radcliffe ที่Western Michigan University [ ^{1 ] ชื่อ} นี้มาจากแนวคิดของกราฟระนาบในทฤษฎีกราฟ ซึ่งเป็นกราฟที่สามารถฝังลงในระนาบยุคลิดได้โดยที่ไม่มีขอบตัดกัน ตามทฤษฎีบทของ Fáryหากกราฟเป็นกราฟระนาบ จะสามารถวาดได้โดยไม่มีจุดตัดกัน ทำให้ขอบทั้งหมดเป็นส่วนของเส้นตรง ในเกม Planarity ผู้เล่นจะได้รับเค้าโครงวงกลมของกราฟระนาบ โดยมีจุดยอดทั้งหมดวางอยู่บนวงกลมเดียวกันและมีจุดตัดกันมากมาย เป้าหมายของผู้เล่นคือการกำจัดจุดตัดทั้งหมดและสร้าง การฝังกราฟ เป็นเส้นตรง โดยการย้ายจุดยอดทีละจุดไปยังตำแหน่งที่ดีกว่า

เกมนี้เขียนด้วยFlashโดย John Tantalo ที่Case Western Reserve Universityในปี 2548 ^{[ 2 ]} ความนิยมทางออนไลน์และชื่อเสียงในท้องถิ่นที่เขาได้รับทำให้ Tantalo กลายเป็นหนึ่งในบุคคลที่น่าสนใจที่สุดของ Cleveland ในปี 2549 ^{[ 3 ] [ 4 ]} ซึ่งต่อมาได้เป็นแรงบันดาลใจให้ Chris MontgomeryจากXiph.org สร้างเวอร์ชันGTK+ขึ้นมา ซึ่งมีอัลกอริธึมการสร้างระดับเพิ่มเติมและความสามารถในการจัดการโหนดหลายโหนดพร้อมกัน^{[ 5 ]}

นิยามของปริศนาความระนาบไม่ได้ขึ้นอยู่กับวิธีการสร้างกราฟระนาบในปริศนา แต่การใช้งานดั้งเดิมใช้อัลกอริทึมดังต่อไปนี้:

1. สร้างชุดเส้นตรงแบบสุ่มในระนาบ โดยที่ไม่มีเส้นตรงสองเส้นใดขนานกัน และไม่มีเส้นตรงสามเส้นใดมาบรรจบกันที่จุดเดียวกัน
2. คำนวณจุดตัดของเส้นตรงทุกคู่
3. สร้างกราฟที่มีจุดยอดแทนจุดตัดแต่ละจุด และเส้นเชื่อมแทนส่วนของเส้นตรงแต่ละเส้นที่เชื่อมจุดตัดสองจุด ( การจัดเรียงของเส้นตรง)

ถ้ากราฟถูกสร้างขึ้นจากเส้นตรง กราฟนั้นจะมีจุดยอด (แต่ละเส้นตรงมีจุดยอด และแต่ละจุดยอดจะใช้ร่วมกับเส้นตรงอื่นอีกหนึ่งเส้น) และขอบ (แต่ละเส้นตรงมีขอบ) พอดี ระดับแรกของระนาบถูกสร้างขึ้นจากเส้นตรง ดังนั้นจึงมีจุดยอดและขอบ แต่ละระดับถัดไปจะถูกสร้างขึ้นจากเส้นตรงมากกว่าระดับก่อนหน้าหนึ่งเส้น ถ้าระดับใดถูกสร้างขึ้นจากเส้นตรง ระดับถัดไปจะมีจุดยอดและขอบมากกว่าเดิม ${\displaystyle L}$${\displaystyle {\tbinom {L}{2}}={\tfrac {L(L-1)}{2}}}$${\displaystyle L-1}$${\displaystyle L(L-2)}$${\displaystyle L-2}$${\displaystyle L=4}$${\displaystyle L(L-1)/2=6}$${\displaystyle L(L-2)=8}$${\displaystyle L}$${\displaystyle L}$${\displaystyle 2L-1}$

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

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

ในสาขาเรขาคณิตเชิงคำนวณกระบวนการย้ายเซตย่อยของจุดยอดในการฝังกราฟเพื่อกำจัดจุดตัดของขอบได้รับการศึกษาโดย Pach และ Tardos (2002) ^{[ 9 ]}และคนอื่นๆ โดยได้รับแรงบันดาลใจจากปริศนาระนาบ^{[ 10 ] [ 11 ] [ 12 ] [ 13 ]}ผลลัพธ์ของนักวิจัยเหล่านี้แสดงให้เห็นว่า (ในทางทฤษฎี สมมติว่าสนามการเล่นเป็นระนาบอนันต์แทนที่จะเป็นสี่เหลี่ยมผืนผ้าที่มีขอบเขต) เป็นไปได้เสมอที่จะแก้ปริศนาในขณะที่ปล่อยให้จุดยอดอินพุตคงที่ในตำแหน่งเดิม สำหรับค่าคงที่ที่ยังไม่ได้กำหนดอย่างแม่นยำ แต่อยู่ระหว่าง 1/4 และน้อยกว่า 1/2 เล็กน้อย เมื่อกราฟระนาบที่จะคลายปมเป็นกราฟวงจรจำนวนจุดยอดที่คงที่อาจมีจำนวนมากขึ้น อย่างไรก็ตาม การหาจำนวนจุดยอดที่มากที่สุดที่อาจคงอยู่ในตำแหน่งเดิมสำหรับปริศนาอินพุตเฉพาะ (หรือเทียบเท่ากับจำนวนการเคลื่อนย้ายที่น้อยที่สุดที่จำเป็นในการแก้ปริศนา) นั้นเป็นปัญหาNP- complete ${\displaystyle n^{\epsilon }}$${\displaystyle n}$${\displaystyle \epsilon }$

Verbitsky (2008)ได้แสดงให้เห็นว่ารูปแบบวงกลมแบบ สุ่ม ที่ใช้สำหรับสถานะเริ่มต้นของ Planarity นั้นเกือบจะแย่ที่สุดเท่าที่จะเป็นไปได้ในแง่ของจำนวนจุดตัด : ไม่ว่ากราฟระนาบใดจะถูกพันกันค่าที่คาดหวังของจำนวนจุดตัดสำหรับรูปแบบนี้จะอยู่ภายในปัจจัยสามเท่าของจำนวนจุดตัดที่มากที่สุดในบรรดารูปแบบทั้งหมด^{[ 14 ]}

ในปี 2014 นักคณิตศาสตร์David Eppsteinได้ตีพิมพ์บทความ^{[ 15 ]}ซึ่งนำเสนออัลกอริทึมที่มีประสิทธิภาพสำหรับการแก้ปัญหากราฟระนาบที่สร้างขึ้นโดยเกม Planarity ดั้งเดิม โดยอิงตามลักษณะเฉพาะของอัลกอริทึมการสร้างปริศนา

• Planarity.net — เกม Flash ต้นฉบับ
• ระบบ NetLogo — รวมอยู่เป็นโปรแกรมตัวอย่าง (เกม) ในระบบ NetLogo
• Planarity — เวอร์ชันที่ใช้SVGและไลบรารีJavaScript d3
• Multitouch Planarity — เวอร์ชันสำหรับเล่นหลายผู้เล่นและรองรับการสัมผัสหลายจุด เขียนด้วยภาษา Pythonโดยใช้ไลบรารี libavg