ในเรขาคณิตเชิงคำนวณและทฤษฎีกราฟเชิงเรขาคณิตกราฟเส้นตรงระนาบ ( PSLG ) หรือที่เรียกว่ากราฟเส้นตรงระนาบหรือกราฟเส้นตรงระนาบคือการฝังกราฟระนาบลงในระนาบโดยที่ขอบของกราฟจะถูกแมปเป็นส่วนของเส้นตรง^{[ 1 ]}ทฤษฎีบทของ Fáry (1948) ระบุว่ากราฟระนาบทุกกราฟมีการฝังแบบนี้

ในเรขาคณิตเชิงคำนวณ PSLG มักถูกเรียกว่าการแบ่งย่อยแบบระนาบโดยมีข้อสันนิษฐานหรือข้อกล่าวอ้างว่าการแบ่งย่อยนั้นเป็นรูปหลายเหลี่ยม ไม่ใช่มีขอบเขตโค้ง

PSLG อาจใช้เป็นตัวแทนของแผนที่ ต่างๆ เช่นแผนที่ทางภูมิศาสตร์ในระบบสารสนเทศทางภูมิศาสตร์^{[ 2 ]}

กรณีพิเศษของ PSLG คือการสร้างรูปสามเหลี่ยม ( การสร้างรูปสามเหลี่ยมจากรูปหลายเหลี่ยมการสร้างรูปสามเหลี่ยมจากเซตจุด ) การสร้างรูปสามเหลี่ยมจากเซตจุดเป็น PSLG สูงสุดในแง่ที่ว่า เป็นไปไม่ได้ที่จะเพิ่มขอบตรงเข้าไปโดยที่กราฟยังคงเป็นระนาบ การสร้างรูปสามเหลี่ยมมีแอปพลิเคชันมากมายในหลากหลายสาขา

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

มีโครงสร้างข้อมูลที่รู้จักกันดีสามแบบสำหรับการแสดง PSLG ได้แก่โครงสร้างข้อมูลขอบปีก (Winged-edge) , ขอบครึ่ง (Halfedge)และขอบสี่ (Quadedge ) โครงสร้างข้อมูลขอบปีกเป็นโครงสร้างที่เก่าแก่ที่สุดในสามแบบ แต่การจัดการมักต้องใช้การแยกแยะกรณีที่ซับซ้อน เนื่องจากตัวอ้างอิงขอบไม่ได้จัดเก็บทิศทางของขอบ และทิศทางของขอบรอบหน้าไม่จำเป็นต้องสอดคล้องกัน โครงสร้างข้อมูลขอบครึ่งจะจัดเก็บทิศทางทั้งสองของขอบและเชื่อมโยงอย่างถูกต้อง ทำให้การดำเนินการและรูปแบบการจัดเก็บง่ายขึ้น โครงสร้างข้อมูลขอบสี่จะจัดเก็บทั้งการแบ่งย่อยระนาบและส่วนคู่พร้อมกัน บันทึกของมันประกอบด้วยบันทึกขอบเท่านั้น สี่รายการสำหรับแต่ละขอบ และในรูปแบบที่เรียบง่ายนั้นเหมาะสมสำหรับการจัดเก็บ PSLG ^{[ 3 ]}

• การระบุตำแหน่งจุดสำหรับจุดที่ต้องการสอบถาม ให้หาว่าจุดนั้นอยู่บนด้านใดของ PSLG
• การซ้อนทับแผนที่คือการหาการซ้อนทับของแผนที่ PSLG สองแผนที่ ซึ่งเป็นการแบ่งระนาบโดยแผนที่ PSLG สองแผนที่ที่ซ้อนทับกัน ในระบบสารสนเทศทางภูมิศาสตร์ (GIS) ปัญหานี้เรียกว่า " การซ้อนทับ แผนที่เฉพาะเรื่อง "

• รายการขอบที่เชื่อมต่อสองทาง (Doubly connected edge list ) โครงสร้างข้อมูลสำหรับแสดง PSLG
• ขนาดคุณลักษณะเฉพาะที่