گراف‌های مسطح با خطوط راست

گراف مسطح با خطوط راست(PSLG)، گرافی است که در صفحه جا داده می‌شود، و یال‌های آن خط‌های راست در صفحه هستند. قضیه فری(Fáry's theorem) ادعا می‌کند هر گراف مسطحی می‌تواند به چنین گرافی در صفحه تبدیل شود.

در هندسه محاسباتی به PSLGها تقسیم کننده‌های سفحه‌ای می‌گویند، با این فرض که هر زیربخش یک چند ضلعی می‌باشد. هر PSLG که درجه هر راس آن بیشتر از1باشد، صفحه را به تعدادی ناحیهٔ چند ضلعی تقسیم می‌کند و برعکس. نبودن رئوس با درجه 1 در حکم بالا کار را برای نوشتن بسیاری از الگوریتم‌ها آسان نموده ولی این شرط الزامی نیست.

PSLGها می‌توانند در نمایش انواع نقشه ها بکار گرفته شوند، مانند : نقشه‌های جغرافیایی در سیستم‌های اطلاعاتی جغرافیایی. موارد خاص استفاده ازPSLGها در مثلث بندی ها(مثلث‌بندی چندضلعی‌ها و مجموعه نقاط) می‌باشد. مثلث بندی کاربردهای بسیاری در زمینه‌های گوناگون دارد.

PSLGها می‌توانند گروه خاصی از گراف‌های اقلیدسی باشند. اگرچه در مباحث مربوط به گراف‌های اقلیدسی بیشتر در مورد خصوصیات اندازه‌ای آن‌ها بحث می‌شود، مانند فاصله بین رئوس، در حالی که در مباحث مربوط بهPSLGها موضوع اصلی پیرامون خصوصیات توپولوژیکال آنها است. برای برخی از گراف‌ها مانند Delaunay triangulation هر دو دسته خصوصیات اندازه‌ای و توپولوژیکال حائز اهمیت است.

جستارهای وابسته

Doubly-connected edge list، داده ساختاری برای نمایش PSLGها

[ Planar straight-line graph]