عن تضمين رسم بياني في الشبكة بأقل عدد من المنحنيات

بالنظر إلى رسم بياني مستوي G مع تمثيل مستوي P، فإن تضمين الشبكة الذي يحافظ على المنطقة لـ G هو تضمين مستوي لـ G في الشبكة المستقيمة والذي له تمثيل مستوي متشابه مع P. في هذه الورقة، تم تقديم خوارزمية تحسب تضمين شبكة يحافظ على المنطقة بأقل عدد من المنحنيات في الحواف. تستخدم هذه الخوارزمية تقنيات تدفق الشبكة، وتعمل في وقت O (n² n)، حيث n هو عدد رؤوس الرسم البياني. يتم أيضًا النظر في إصدارات مقيدة من المشكلة، ويتم توسيع معظم النتائج إلى الرسوم البيانية k-الأضلاع، أي الرسوم البيانية التي تكون حوافها تسلسلاً من القطاعات بزاوية مضاعفة لـ {180 / k} درجة. يمكن العثور على تطبيقات للنتائج المذكورة أعلاه في عدة مجالات: تخطيط الدوائر VLSI، تصميم الهندسة المعمارية، الاتصال بالضوء أو الميكروويف، مشاكل النقل، والتخطيط التلقائي للمخططات الشبيهة بالرسم البياني.