تقليل الانحناء

في أساليب رسم المخططات التي تُمثل حواف المخطط بخطوط متعددة (سلاسل من القطع المستقيمة المتصلة عند نقاط الانحناء )، يُستحسن تقليل عدد نقاط الانحناء لكل حافة (يُسمى أحيانًا تعقيد المنحنى ) ^{[ 1 ]} أو إجمالي عدد نقاط الانحناء في الرسم. ^{[ 2 ]} يُعد تقليل نقاط الانحناء مسألة خوارزمية لإيجاد رسم يُقلل هذه الكميات. ^{[ 3 ] [ 4 ]}

يُعدّ مثال فاري النموذجي لتقليل الانحناءات ، والذي ينص على أنه يمكن رسم أي رسم بياني مستوٍ بدون انحناءات، أي برسم جميع حوافه كقطع مستقيمة. ^{[ 5 ]}

تُسمى رسومات المخططات التي تكون حوافها مستقيمة ومتوازية مع المحاور أحيانًا بالرسومات الخطية ، وهي إحدى طرق إنشاء رسومات RAC التي تكون فيها جميع التقاطعات بزوايا قائمة. ^{[ 6 ]} ومع ذلك، فإن تحديد ما إذا كان للمخطط المستوي رسم خطي مستوٍ يُعد مسألة NP-كاملة ، ^{[ 7 ]} كما أن تحديد ما إذا كان للمخطط العشوائي رسم خطي يسمح بالتقاطعات يُعد مسألة NP-كاملة أيضًا. ^{[ 6 ]}

أظهر تاماسيا (1987) أن تقليل الانحناءات في الرسومات المتعامدة للرسوم البيانية المستوية، حيث توضع الرؤوس في شبكة عددية وتُرسم الحواف كخطوط متعددة محاذية للمحاور، يمكن إجراؤه في وقت متعدد الحدود عن طريق تحويل المسألة إلى مسألة تدفق الشبكة بأقل تكلفة . ^{[ 8 ] [ 9 ]} مع ذلك، إذا كان من الممكن تغيير التضمين المستوي للرسم البياني، فإن تقليل الانحناءات يصبح مسألة NP-كاملة، ويجب حلها بدلاً من ذلك بتقنيات مثل البرمجة العددية التي لا تضمن كلاً من وقت التشغيل السريع والإجابة الدقيقة. ^{[ 10 ]}

تسمح العديد من أنماط رسم المخططات بالانحناءات، ولكن بشكل محدود: فتعقيد المنحنى في هذه الرسومات (الحد الأقصى لعدد الانحناءات لكل حافة) محدود بقيمة ثابتة. ويمكن استخدام زيادة هذه القيمة الثابتة لتحسين جوانب أخرى من الرسم، مثل مساحته . [ ^{1 ] في} المقابل، في بعض الحالات، قد يكون نمط الرسم ممكنًا فقط عند السماح بالانحناءات؛ على سبيل المثال، ليس لكل مخطط رسم RAC (رسم تكون فيه جميع التقاطعات بزوايا قائمة) بدون انحناءات، أو بتعقيد منحنى اثنين، ولكن لكل مخطط رسم من هذا النوع بتعقيد منحنى ثلاثة. ^{[ 11 ]}