نظرية الفاصل المستوي

قام ليبتون وتارجان (1979) بتوسيع الرسم البياني المستوي المعطى بإضافة حواف إضافية، إذا لزم الأمر، ليصبح مستوياً أقصى (كل وجه في تمثيل مستوٍ هو مثلث). ثم قاموا بإجراء بحث بالعرض أولاً ، يبدأ من رأس عشوائي.${\displaystyle v}$وتقسيم الرؤوس إلى مستويات حسب بعدها عن${\displaystyle v}$. لو${\displaystyle l_{1}}$هو المستوى الوسيط (المستوى الذي يكون فيه عدد الرؤوس في المستويين الأعلى والأدنى على الأكثر)${\displaystyle n/2}$ثم يجب أن تكون هناك مستويات${\displaystyle l_{0}}$و${\displaystyle l_{2}}$التي هي${\displaystyle O({\sqrt {n}})}$خطوات أعلى وأسفل${\displaystyle l_{1}}$على التوالي والتي تحتوي على${\displaystyle O({\sqrt {n}})}$الرؤوس، على التوالي، وإلا فسيكون هناك أكثر من${\displaystyle n}$الرؤوس في المستويات القريبة${\displaystyle l_{1}}$تُظهر هذه النتائج أنه لا بد من وجود فاصل.${\displaystyle S}$تشكلت من خلال اتحاد${\displaystyle l_{0}}$و${\displaystyle l_{2}}$، نقاط نهاية الحافة${\displaystyle e}$ل${\displaystyle G}$الذي لا ينتمي إلى شجرة البحث بالعرض أولاً والذي يقع بين المستويين، والرؤوس الموجودة على مساري شجرة البحث بالعرض أولاً من نقاط النهاية لـ${\displaystyle e}$العودة إلى المستوى${\displaystyle l_{0}}$حجم الفاصل${\displaystyle S}$إن البناء بهذه الطريقة هو على الأكثر${\displaystyle {\sqrt {8n}}\approx 2.83{\sqrt {n}}}$يمكن إيجاد رؤوس الفاصل والرسمين الفرعيين المنفصلين في وقت خطي . ^{[ 4 ]}

ينطبق هذا البرهان لنظرية الفاصل أيضًا على الرسوم البيانية المستوية الموزونة، حيث يكون لكل رأس تكلفة غير سالبة. يمكن تقسيم الرسم البياني إلى ثلاث مجموعات.${\displaystyle A}$،${\displaystyle S}$، و${\displaystyle B}$بحيث${\displaystyle A}$و${\displaystyle B}$كل منها على الأكثر${\displaystyle 2/3}$من التكلفة الإجمالية و${\displaystyle S}$لديه${\displaystyle O({\sqrt {n}})}$رؤوس، بدون حواف من${\displaystyle A}$و${\displaystyle B}$[ ^{4 ]} من خلال تحليل بنية فاصلة مماثلة بمزيد من الدقة، يُبين دجيدجيف (1982) ^أن الحد الأقصى لحجم${\displaystyle S}$يمكن اختصارها إلى${\displaystyle {\sqrt {6n}}\approx 2.45{\sqrt {n}}}$[ ^{2 ]​}

يقترح هولزر وآخرون (2009) نسخة مبسطة من هذا النهج: حيث يقومون بتوسيع الرسم البياني ليكون مستويًا أقصى، ثم يبنون شجرة بحث بالعرض أولًا كما كان من قبل. بعد ذلك، لكل حافة${\displaystyle e}$هذا ليس جزءًا من الشجرة، بل يشكلون دورة من خلال الجمع${\displaystyle e}$باستخدام مسار الشجرة الذي يربط نقاط نهايته. ثم يستخدمون رؤوس إحدى هذه الدورات كفاصل. على الرغم من أن هذا النهج لا يضمن إيجاد فاصل صغير للرسوم البيانية المستوية ذات القطر الكبير، إلا أن تجاربهم تشير إلى أنه يتفوق على طريقتي ليبتون-تارجان ودجيدجيف للترتيب الطبقي بالعرض أولاً على أنواع عديدة من الرسوم البيانية المستوية. ^{[ 5 ]}

بالنسبة للرسم البياني المستوي الأقصى بالفعل، من الممكن إظهار بناء أقوى لفاصل دورة بسيط ، وهي دورة ذات طول صغير بحيث يكون لكل من داخل الدورة وخارجها (في التضمين المستوي الوحيد للرسم البياني) على الأكثر${\displaystyle 2n/3}$الرؤوس. يثبت ميلر (1986) ذلك (بحجم فاصل يبلغ${\displaystyle {\sqrt {8n}}}$) باستخدام تقنية ليبتون-تارجان لنسخة معدلة من البحث بالعرض أولاً حيث تشكل مستويات البحث دورات بسيطة. ^{[ 6 ]}

أثبت ألون وسيمور وتوماس (1994) وجود فواصل الدورة البسيطة بشكل مباشر: ليكن${\displaystyle C}$أن تكون دورة من على الأكثر${\displaystyle {\sqrt {8n}}}$رؤوس، مع أكثر من${\displaystyle 2n/3}$الرؤوس الخارجية${\displaystyle C}$، مما يشكل تقسيمًا متساويًا قدر الإمكان بين الداخل والخارج. وتُظهر هذه الافتراضات أن هذه الافتراضات تُجبر${\displaystyle C}$ليكون فاصلاً. وإلا، فإن المسافات داخل${\displaystyle C}$يجب أن تساوي المسافات في القرص المحصور بـ${\displaystyle C}$(سيشكل المسار الأقصر عبر باطن القرص جزءًا من حدود دورة أفضل). بالإضافة إلى ذلك،${\displaystyle C}$يجب أن يكون الطول بالضبط${\displaystyle {\sqrt {8n}}}$وإلا فإنه يمكن تحسينه باستبدال أحد أضلاعه بالضلعين الآخرين لمثلث. إذا كانت رؤوس المثلث في${\displaystyle C}$يتم ترقيمها (في اتجاه عقارب الساعة) من${\displaystyle 1}$ل${\displaystyle {\sqrt {8n}}}$، والرأس${\displaystyle i}$يتم مطابقته مع الرأس${\displaystyle {\sqrt {8n}}-i+1}$إذاً، يمكن ربط هذه الأزواج المتطابقة بمسارات منفصلة الرؤوس داخل القرص، وذلك بصيغة من نظرية مينجر للرسوم البيانية المستوية. ومع ذلك، فإن الطول الإجمالي لهذه المسارات سيتجاوز بالضرورة${\displaystyle n}$وهذا تناقض. وببعض العمل الإضافي، يُظهرون بطريقة مماثلة وجود فاصل دوري بسيط بحجم لا يتجاوز${\displaystyle {\sqrt {9n/2}}\approx 2.12{\sqrt {n}}}$[ ^{7 ]​}

قام دجيدجيف وفينكاتيسان (1997) بتحسين العامل الثابت في نظرية فاصل الدورة البسيطة إلى${\displaystyle 1.97{\sqrt {n}}}$كما يمكن لطريقتهم إيجاد فواصل دورات بسيطة للرسوم البيانية ذات أوزان الرؤوس غير السالبة، بحجم فاصل لا يتجاوز${\displaystyle 2{\sqrt {n}}}$ويمكنها توليد فواصل أصغر حجمًا على حساب تقسيم غير متساوٍ للرسم البياني. ^{[ 8 ]} في الرسوم البيانية المستوية ثنائية الاتصال غير القصوى، توجد فواصل دورات بسيطة يتناسب حجمها مع المعيار الإقليدي لمتجه أطوال الأوجه، ويمكن إيجادها في وقت شبه خطي. ^{[ 9 ]}

وفقًا لنظرية تعبئة الدوائر لكوبي-أندرييف-ثورستون ، يمكن تمثيل أي رسم بياني مستوٍ بتعبئة أقراص دائرية في المستوى ذات دواخل منفصلة، ​​بحيث يكون رأسان في الرسم البياني متجاورين إذا وفقط إذا كان الزوج المقابل من الأقراص متماسًا. وكما بيّن ميلر وآخرون (1997)، فإنه بالنسبة لمثل هذه التعبئة، توجد دائرة تحتوي على أكثر من${\displaystyle 3n/4}$الأقراص الملامسة لها أو الموجودة داخلها، على الأكثر${\displaystyle 3n/4}$الأقراص الملامسة لها أو خارجها، والتي تعبرها${\displaystyle O({\sqrt {n}})}$الأقراص. ^{[ 10 ]}

ولإثبات ذلك، استخدم ميلر وزملاؤه الإسقاط المجسم لرسم خريطة التعبئة على سطح كرة وحدة في ثلاثة أبعاد. باختيار الإسقاط بعناية، يمكن جعل مركز الكرة نقطة مركزية لمراكز الأقراص على سطحها، بحيث يقسم أي مستوى يمر بمركز الكرة الكرة إلى نصفين، يحتوي كل منهما على أو يتقاطع مع أكثر من${\displaystyle 3n/4}$من الأقراص. إذا تم اختيار مستوى يمر بالمركز عشوائيًا وبشكل منتظم، فسيتم عبور قرص باحتمالية تتناسب مع نصف قطره. لذلك، فإن العدد المتوقع للأقراص التي يتم عبورها يتناسب مع مجموع أنصاف أقطار الأقراص. ومع ذلك، فإن مجموع مربعات أنصاف الأقطار يتناسب مع المساحة الكلية للأقراص، والتي هي على الأكثر المساحة الكلية لسطح الكرة الوحدة، وهي قيمة ثابتة. تُظهر حجة تتضمن متباينة جنسن أنه عندما يكون مجموع مربعات${\displaystyle n}$إذا كانت الأعداد الحقيقية غير السالبة محدودة بثابت، فإن مجموع هذه الأعداد يكون${\displaystyle O({\sqrt {n}})}$لذلك، فإن العدد المتوقع للأقراص التي يقطعها مستوى عشوائي هو${\displaystyle O({\sqrt {n}})}$ويوجد مستوى يقطع على الأكثر هذا العدد من الأقراص. يتقاطع هذا المستوى مع الكرة في دائرة عظمى ، والتي بدورها تُسقط لأسفل إلى دائرة في المستوى بالخصائص المطلوبة.${\displaystyle O({\sqrt {n}})}$تمثل الأقراص التي يتقاطع معها هذا الدائرة رؤوس فاصل بياني مستوٍ يفصل الرؤوس التي تقع أقراصها داخل الدائرة عن الرؤوس التي تقع أقراصها خارج الدائرة، بحد أقصى${\displaystyle 3n/4}$الرؤوس في كل من هاتين المجموعتين الفرعيتين. ^{[ 11 ]}

تؤدي هذه الطريقة إلى خوارزمية عشوائية تجد فاصلًا كهذا في زمن خطي ، ^{[ 10 ]} وخوارزمية حتمية أقل عملية بنفس الحد الزمني الخطي. ^{[ 12 ]} من خلال تحليل هذه الخوارزمية بعناية باستخدام الحدود المعروفة لكثافة التعبئة في التعبئة الدائرية ، يمكن إثبات أنها تجد فواصل بحجم لا يتجاوز ^{[ 13 ].}$${\displaystyle {\sqrt {\frac {2\pi }{\sqrt {3}}}}\left({\frac {1+{\sqrt {3}}}{2{\sqrt {2}}}}+o(1)\right){\sqrt {n}}\approx 1.84{\sqrt {n}}.}$$ على الرغم من أن هذا الحد المحسّن لحجم الفاصل يأتي على حساب تقسيم غير متساوٍ للرسم البياني، إلا أن سبيلمان وتينغ (1996) يجادلان بأنه يوفر عاملًا ثابتًا محسّنًا في الحدود الزمنية للتشريح المتداخل مقارنةً بالفواصل التي قدمها ألون وسيمور وتوماس (1990) . ويمكن تحسين حجم الفواصل الناتجة عمليًا باستخدام توزيع غير منتظم لمستويات القطع العشوائية. ^{[ 14 ]}

يمكن تجنب الإسقاط المجسم في حجة ميلر وآخرون من خلال النظر في أصغر دائرة تحتوي على نسبة ثابتة من مراكز الأقراص، ثم توسيعها بمقدار ثابت يتم اختياره بشكل منتظم في النطاق${\displaystyle [1,2]}$كما في دراسة ميلر وآخرون، تشكل الأقراص المتقاطعة مع الدائرة الموسعة فاصلاً صالحاً، ومن المتوقع أن يكون الفاصل بالحجم المناسب. أما الثوابت الناتجة فهي أسوأ نوعاً ما. ^{[ 15 ]}

لطالما استُخدمت طرق التجميع الطيفي ، التي تُجمَّع فيها رؤوس الرسم البياني وفقًا لإحداثيات المتجهات الذاتية للمصفوفات المُستخرجة من الرسم البياني، كطريقة استدلالية لحل مسائل تقسيم الرسوم البيانية غير المستوية. ^{[ 16 ]} وكما بيّن سبيلمان وتينغ (2007) ، يُمكن أيضًا استخدام التجميع الطيفي لاستنباط برهان بديل لصيغة مُخفَّفة من نظرية الفاصل المستوي التي تنطبق على الرسوم البيانية المستوية ذات الدرجة المحدودة. في طريقتهم، تُرتَّب رؤوس الرسم البياني المستوي المُعطى وفقًا للإحداثيات الثانية للمتجهات الذاتية لمصفوفة لابلاس الخاصة بالرسم البياني، ويُقسَّم هذا الترتيب عند النقطة التي تُقلِّل نسبة عدد الحواف المقطوعة بالتقسيم إلى عدد الرؤوس على الجانب الأصغر من التقسيم. وكما بيّنوا، فإن كل رسم بياني مستوي ذي درجة محدودة له تقسيم من هذا النوع تكون فيه النسبة${\displaystyle O(1/{\sqrt {n}})}$على الرغم من أن هذا التقسيم قد لا يكون متوازنًا، إلا أن تكرار التقسيم داخل الجانب الأكبر من الجانبين وأخذ اتحاد القطع المتكونة في كل تكرار سيؤدي في النهاية إلى تقسيم متوازن مع${\displaystyle O({\sqrt {n}})}$الحواف. تشكل نهايات هذه الحواف فاصلاً بحجم${\displaystyle O({\sqrt {n}})}$[ ^{17 ]​}

يتضمن أحد أشكال نظرية الفاصل المستوي فواصل الحواف ، وهي مجموعات صغيرة من الحواف تشكل قطعًا بين مجموعتين فرعيتين.${\displaystyle A}$و${\displaystyle B}$رؤوس الرسم البياني. المجموعتان${\displaystyle A}$و${\displaystyle B}$يجب ألا يتجاوز حجم كل منها جزءًا ثابتًا من العدد${\displaystyle n}$عدد رؤوس الرسم البياني (اصطلاحًا، يكون حجم كلتا المجموعتين على الأكثر${\displaystyle 2n/3}$وينتمي كل رأس من رؤوس الرسم البياني إلى واحد فقط من${\displaystyle A}$و${\displaystyle B}$يتكون الفاصل من الحواف التي لها نقطة نهاية واحدة في${\displaystyle A}$ونقطة نهاية واحدة في${\displaystyle B}$تتضمن حدود حجم فاصل الحواف درجة الرؤوس بالإضافة إلى عدد الرؤوس في الرسم البياني: الرسوم البيانية المستوية التي يكون فيها أحد الرؤوس بدرجة${\displaystyle n-1}$لا تحتوي الرسوم البيانية المستوية ، بما في ذلك الرسوم البيانية الدائرية والنجمية ، على فاصل حواف بعدد حواف أقل من الخطي، لأن أي فاصل حواف سيتضمن جميع الحواف التي تربط الرأس ذي الدرجة العالية بالرؤوس على الجانب الآخر من القطع. ومع ذلك، فإن كل رسم بياني مستوٍ ذي درجة قصوى${\displaystyle \Delta }$يحتوي على فاصل حافة بحجم${\displaystyle O({\sqrt {\Delta n}})}$[ ^{18 ]​}

يشكل فاصل الدورة البسيط في الرسم البياني الثنائي لرسم بياني مستوٍ فاصلًا للحواف في الرسم البياني الأصلي. ^{[ 19 ]} إن تطبيق نظرية فاصل الدورة البسيط لجازيت وميلر (1990) على الرسم البياني الثنائي لرسم بياني مستوٍ معين يعزز${\displaystyle O({\sqrt {\Delta n}})}$تحديد حجم فاصل الحواف من خلال إظهار أن كل رسم بياني مستوي له فاصل حواف يتناسب حجمه مع المعيار الإقليدي لمتجه درجات الرؤوس.

يصف باباديميتريو وسيديري (1996) خوارزمية زمنية متعددة الحدود لإيجاد أصغر فاصل حواف يقسم الرسم البياني${\displaystyle G}$إلى رسمين بيانيين فرعيين متساويين في الحجم، عندما${\displaystyle G}$هي رسم بياني فرعي مُستحث من رسم بياني شبكي بدون ثقوب أو بعدد ثابت من الثقوب. ومع ذلك، يفترضون أن المسألة من فئة NP-كاملة بالنسبة للرسوم البيانية المستوية العشوائية، ويُظهرون أن تعقيد المسألة هو نفسه بالنسبة للرسوم البيانية الشبكية ذات عدد الثقوب العشوائي كما هو الحال بالنسبة للرسوم البيانية المستوية العشوائية.

يمكن الاستفادة من تحليل الفواصل في تصميم خوارزميات فعّالة تعتمد على أسلوب فرق تسد لحل مسائل الرسوم البيانية المستوية. على سبيل المثال، من المسائل التي يمكن حلها بهذه الطريقة إيجاد أقصر دورة في رسم بياني موجّه مستوٍ مُثقّل. ويمكن حل هذه المسألة باتباع الخطوات التالية:

• قسّم الرسم البياني المعطى${\displaystyle G}$إلى ثلاث مجموعات فرعية${\displaystyle S}$،${\displaystyle A}$،${\displaystyle B}$وفقًا لنظرية الفاصل المستوي
• ابحث بشكل متكرر عن أقصر الدورات في${\displaystyle A}$و${\displaystyle B}$
• استخدم خوارزمية ديكسترا لإيجاد، لكل رأس${\displaystyle s}$في${\displaystyle S}$أقصر دورة عبر${\displaystyle s}$في${\displaystyle G}$.
• أعد أقصر الدورات التي تم العثور عليها من خلال الخطوات المذكورة أعلاه.

الوقت اللازم لإجراء الاستدعاءين المتكررين لـ${\displaystyle A}$و${\displaystyle B}$في هذه الخوارزمية، يهيمن الوقت اللازم لتنفيذها${\displaystyle O({\sqrt {n}})}$تستدعي هذه الخوارزمية خوارزمية ديكسترا، لذا فهي تجد أقصر دورة في${\displaystyle O(n^{3/2}\log n)}$وقت.

خوارزمية أسرع لحل نفس مشكلة أقصر دورة، تعمل في وقت${\displaystyle O(n\log ^{3}n)}$تم تقديم هذه الخوارزمية بواسطة وولف-نيلسن (2009) . تستخدم خوارزميته نفس بنية فرق تسد القائمة على الفواصل، ولكنها تستخدم فواصل دورية بسيطة بدلاً من الفواصل العشوائية، بحيث تكون رؤوس${\displaystyle S}$ينتمي إلى وجه واحد من الرسوم البيانية داخل وخارج فاصل الدورة. ثم يستبدل${\displaystyle O({\sqrt {n}})}$ يتم فصل استدعاءات خوارزمية ديكسترا مع خوارزميات أكثر تطورًا لإيجاد أقصر المسارات من جميع الرؤوس على وجه واحد من الرسم البياني المستوي، ولدمج المسافات من الرسمين البيانيين الفرعيين. بالنسبة للرسوم البيانية المستوية الموزونة ولكن غير الموجهة، فإن أقصر دورة تعادل القطع الأدنى في الرسم البياني الثنائي ، ويمكن إيجادها في${\displaystyle O(n\log \log n)}$^{[ 27 ]} ويمكن إيجاد أقصر دورة في رسم بياني مستوٍ غير موجه وغير مرجح (محيطه ) في الزمن${\displaystyle O(n)}$^{[ 28 ]} (ومع ذلك ، فإن الخوارزمية الأسرع للرسوم البيانية غير الموزونة لا تعتمد على نظرية الفاصل.)

اقترح فريدريكسون خوارزمية أخرى أسرع لإيجاد أقصر المسارات من مصدر واحد، وذلك بتطبيق نظرية الفاصل في الرسوم البيانية المستوية. ^{[ 29 ]} تُعد هذه الخوارزمية تحسينًا لخوارزمية ديكسترا، حيث تعتمد على البحث التكراري على مجموعة فرعية مختارة بعناية من الرؤوس. تأخذ هذه النسخة${\displaystyle O(n{\sqrt {\log n}})}$في وقت واحد${\displaystyle n}$الرسم البياني ذو الرؤوس المتعددة. تُستخدم الفواصل لإيجاد تقسيم للرسم البياني، أي تقسيم مجموعة الحواف إلى مجموعتين فرعيتين أو أكثر، تُسمى مناطق. يُقال إن عقدة ما موجودة في منطقة ما إذا كانت إحدى حواف تلك المنطقة متصلة بها. تُسمى العقدة الموجودة في أكثر من منطقة واحدة عقدة حدودية للمناطق التي تحتويها. تستخدم هذه الطريقة مفهوم${\displaystyle r}$-تقسيم${\displaystyle n}$الرسم البياني ذو العقدة الواحدة هو تقسيم الرسم البياني إلى${\displaystyle O(n/r)}$مناطق، تحتوي كل منها على${\displaystyle O(r)}$العقد بما في ذلك${\displaystyle O({\sqrt {r}})}$عقد الحدود. أظهر فريدريكسون أن${\displaystyle r}$يمكن العثور على قسمة في${\displaystyle O(n\log n)}$الوقت عن طريق التطبيق المتكرر لنظرية الفاصل.

فيما يلي مخطط خوارزميته لحل المشكلة.

1. مرحلة المعالجة المسبقة: يتم تقسيم الرسم البياني إلى مجموعات فرعية مختارة بعناية من الرؤوس، وتحديد أقصر المسارات بين جميع أزواج الرؤوس في هذه المجموعات الفرعية، حيث لا تقع الرؤوس الوسيطة على هذا المسار ضمن المجموعة الفرعية. تتطلب هذه المرحلة رسمًا بيانيًا مستويًا.${\displaystyle G_{0}}$ليتم تحويلها إلى${\displaystyle G}$مع عدم وجود أي رأس بدرجة أكبر من ثلاثة. من نتيجة لصيغة أويلر ، سيكون عدد الرؤوس في الرسم البياني الناتج هو${\displaystyle n\leq 6n_{0}-12}$، أين${\displaystyle n_{0}}$يمثل عدد الرؤوس في${\displaystyle G_{0}}$تضمن هذه المرحلة أيضًا الخصائص التالية لمنتج مناسب${\displaystyle r}$-قسمة. مناسب${\displaystyle r}$- تقسيم الرسم البياني المستوي هو${\displaystyle r}$القسمة بحيث،
   • يحتوي كل رأس من رؤوس الحدود على ثلاث مناطق على الأكثر، و
   • أي منطقة غير متصلة تتكون من مكونات متصلة، وكلها تشترك في رؤوس حدودية مع نفس المجموعة من منطقة واحدة أو منطقتين متصلتين.
2. مرحلة البحث:
   • الهدف الرئيسي: إيجاد أقصر المسافات من المصدر إلى كل رأس في المجموعة الفرعية. عندما يكون الرأس${\displaystyle v}$في المجموعة الفرعية المغلقة، المسافة التقريبية${\displaystyle d(w)}$يجب تحديثها لجميع الرؤوس${\displaystyle w}$في المجموعة الفرعية التي يوجد مسار منها${\displaystyle v}$ل${\displaystyle w}$.
   • التنظيف: تحديد أقصر المسافات إلى كل رأس متبقٍ.

قام هينزينجر وآخرون بتوسيع نطاق فريدريكسون${\displaystyle r}$تقنية التقسيم لخوارزمية أقصر مسار من مصدر واحد في الرسوم البيانية المستوية لأطوال الحواف غير السالبة، واقترحوا خوارزمية زمنية خطية . ^{[ 30 ]} تعمم طريقتهم مفهوم فريدريكسون لتقسيمات الرسوم البيانية بحيث أصبح الآن${\displaystyle (r,s)}$-تقسيم${\displaystyle n}$الرسم البياني ذو العقدة هو تقسيم إلى${\displaystyle O(n/r)}$مناطق، تحتوي كل منها على${\displaystyle r^{O(1)}}$العقد، كل منها يحتوي على الأكثر${\displaystyle s}$عقد الحدود. إذا كان${\displaystyle (r,s)}$يتم تقسيم عملية القسمة بشكل متكرر إلى مناطق أصغر، وهذا ما يسمى بالقسمة المتكررة. تستخدم هذه الخوارزمية ما يقارب${\displaystyle \log ^{*}n}$مستويات التقسيمات، حيث${\displaystyle \log ^{*}}$تشير إلى دالة اللوغاريتم المتكررة . يتم تمثيل القسمة المتكررة بشجرة جذرية يتم تمييز أوراقها بحواف مميزة من${\displaystyle G}$يمثل جذر الشجرة المنطقة التي تتكون من كل${\displaystyle G}$تمثل فروع الجذر المناطق الفرعية التي تنقسم إليها تلك المنطقة، وهكذا. كل ورقة (منطقة ذرية) تمثل منطقة تحتوي على حافة واحدة فقط.

يُعدّ التفكيك المتداخل أحد أساليب التجزئة والتغلب القائمة على الفواصل، وهو شكل مُعدّل من أسلوب الحذف الغاوسي، ويُستخدم لحلّ أنظمة المعادلات الخطية المتناظرة ذات البنية البيانية المستوية، مثل تلك الناتجة عن طريقة العناصر المحدودة . يتضمن هذا الأسلوب إيجاد فاصل للرسم البياني الذي يصف نظام المعادلات، ثم حذف المتغيرات في المسألتين الفرعيتين المفصولتين بهذا الفاصل بشكل متكرر، ثم حذف المتغيرات الموجودة في الفاصل نفسه. ^{[ 31 ]} ويُعرف مُكمِّل هذه الطريقة (عدد المعاملات غير الصفرية في تحليل تشوليسكي الناتج للمصفوفة) بـ${\displaystyle O(n\log n)}$[ ^{32 ] مما يسمح} لهذه الطريقة بأن تكون منافسة للطرق التكرارية لنفس المشكلات. ^{[ 31 ]}

كلاين وموزيس وويمان ^{[ 33 ]} قدموا${\displaystyle O(n\log ^{2}n)}$خوارزمية ذات زمن خطي ومساحة خطية لإيجاد أقصر مسافة مسار من رأس مصدر${\displaystyle s}$إلى جميع الرؤوس الأخرى لرسم بياني مستوٍ موجه ذي أطوال أقواس موجبة وسالبة لا يحتوي على دورات سالبة. تستخدم خوارزميتهم فواصل الرسم البياني المستوي لإيجاد منحنى جوردان${\displaystyle C}$الذي يمر عبر${\displaystyle O({\sqrt {n}})}$العقد (بدون أقواس) بحيث بين${\displaystyle n/3}$و${\displaystyle 2n/3}$العقد محاطة بـ${\displaystyle C}$. العقد التي من خلالها${\displaystyle C}$الممرات هي عقد حدودية . الرسم البياني الأصلي${\displaystyle G}$ينقسم إلى رسمين بيانيين فرعيين${\displaystyle G_{0}}$و${\displaystyle G_{1}}$عن طريق قطع التضمين المستوي على طول${\displaystyle C}$وتكرار عقد الحدود. عقد الحدود في كل رسم بياني${\displaystyle G_{i}}$تقع على حدود وجه واحد${\displaystyle F_{i}}$.

فيما يلي نظرة عامة على نهجهم.

• الاستدعاء المتكرر: المرحلة الأولى تحسب المسافات بشكل متكرر من${\displaystyle r}$داخل كل رسم بياني${\displaystyle G_{i}}$.
• المسافات الحدودية داخل الجزء: لكل رسم بياني${\displaystyle G_{i}}$احسب جميع المسافات في${\displaystyle G_{i}}$بين عقد الحدود. هذا يأخذ${\displaystyle O(n\log n)}$وقت.
• مسافات الحدود بين الأجزاء من مصدر واحد: أقصر مسار في${\displaystyle G}$يمر ذهابًا وإيابًا بين${\displaystyle G_{0}}$و${\displaystyle G_{1}}$لحساب المسافات في${\displaystyle G}$من${\displaystyle r}$إلى جميع عقد الحدود. تستخدم التكرارات المتناوبة جميع مسافات الحدود في${\displaystyle G_{0}}$و${\displaystyle G_{1}}$عدد التكرارات هو${\displaystyle O({\sqrt {n}})}$والوقت الإجمالي لهذه المرحلة هو${\displaystyle O(n\alpha (n))}$أين${\displaystyle \alpha (n)}$هي دالة أكرمان العكسية .
• المسافات بين الأجزاء من مصدر واحد: تُستخدم المسافات المحسوبة في المراحل السابقة، بالإضافة إلى حساب ديكسترا ضمن نسخة معدلة من كل G _i  ، لحساب المسافات في${\displaystyle G}$من${\displaystyle r}$إلى جميع العقد. تستغرق هذه المرحلة${\displaystyle O(n\log n)}$وقت.
• إعادة توجيه المسافات من مصدر واحد: المسافات من${\displaystyle r}$في${\displaystyle G}$يتم تحويلها إلى أطوال غير سالبة، ويتم استخدام خوارزمية ديكسترا مرة أخرى لحساب المسافات من${\displaystyle s}$تتطلب هذه المرحلة${\displaystyle O(n\log n)}$وقت.

يُعد استخدام دوال السعر والأطوال المُختزلة جزءًا مهمًا من هذه الخوارزمية. بالنسبة للرسم البياني الموجه${\displaystyle G}$بأطوال الأقواس${\displaystyle \ell (uv)}$دالة السعر هي دالة${\displaystyle \varphi }$من عقد${\displaystyle G}$إلى الأعداد الحقيقية . لقوس${\displaystyle uv}$، الطول المخفّض بالنسبة إلى${\displaystyle \varphi }$يكون${\displaystyle \ell _{\varphi }(uv)=\ell (uv)+\varphi (u)-\varphi (v)}$دالة السعر الممكنة هي دالة سعر تُنتج أطوالًا مُختزلة غير سالبة على جميع أقواس${\displaystyle G}$. إنه مفيد في تحويل مشكلة أقصر مسار تتضمن أطوالًا موجبة وسالبة إلى مشكلة تتضمن أطوالًا غير سالبة فقط، والتي يمكن حلها بعد ذلك باستخدام خوارزمية ديكسترا.

استُخدم نموذج "فرق تسد" القائم على الفواصل أيضًا لتصميم هياكل البيانات لخوارزميات الرسوم البيانية الديناميكية ^{[ 34 ]} وتحديد مواقع النقاط ^{[ 35 ]} ، وخوارزميات تثليث المضلعات ^{[ 20 ]} ، وأقصر المسارات ^{[ 36 ]} ، وبناء رسوم بيانية لأقرب الجيران ^{[ 37 ]} ، وخوارزميات تقريبية لأكبر مجموعة مستقلة في رسم بياني مستوٍ ^{[ 35 ] .}

باستخدام البرمجة الديناميكية على تجزئة الشجرة أو تجزئة الفروع للرسم البياني المستوي، يمكن حل العديد من مسائل التحسين الصعبة من نوع NP في وقت أسي في${\displaystyle {\sqrt {n}}}$أو${\displaystyle {\sqrt {n}}\log n}$على سبيل المثال، تُعرف حدود من هذا الشكل لإيجاد المجموعات المستقلة القصوى ، وأشجار شتاينر ، ودورات هاميلتون ، ولحل مسألة البائع المتجول على الرسوم البيانية المستوية. ^{[ 38 ]} يمكن استخدام طرق مماثلة تتضمن نظريات الفصل للرسوم البيانية الهندسية لحل مسألة البائع المتجول الإقليدية ومسائل بناء أشجار شتاينر في حدود زمنية من نفس الشكل. ^{[ 39 ]}

بالنسبة للمسائل ذات المعاملات التي تسمح بتقسيم النواة إلى نواة تحافظ على التسطح وتقلل الرسم البياني المدخل إلى نواة ذات حجم خطي في معامل الإدخال، يمكن استخدام هذا النهج لتصميم خوارزميات قابلة للمعالجة ذات معاملات ثابتة، ويعتمد وقت تشغيلها بشكل متعدد الحدود على حجم الرسم البياني المدخل وأُسّيًا على${\displaystyle {\sqrt {k}}}$، أين${\displaystyle k}$يمثل هذا المعامل الخاص بالخوارزمية. على سبيل المثال، تُعرف حدود زمنية من هذا الشكل لإيجاد أغطية الرؤوس والمجموعات المهيمنة ذات الحجم${\displaystyle k}$[ ^{40 ]​}

لاحظ ليبتون وتارجان (1980) أنه يمكن استخدام نظرية الفاصل للحصول على مخططات تقريبية متعددة الحدود لمسائل التحسين الصعبة من نوع NP على الرسوم البيانية المستوية، مثل إيجاد المجموعة المستقلة القصوى . وبالتحديد، من خلال اقتطاع تسلسل هرمي للفواصل عند مستوى مناسب، يمكن إيجاد فاصل بحجم${\displaystyle O(n/{\sqrt {\log n}})}$يؤدي حذف العنصر الذي يقسم الرسم البياني إلى رسوم بيانية فرعية بحجم لا يتجاوز${\displaystyle c\log n}$، لأي ثابت${\displaystyle c}$بحسب نظرية الألوان الأربعة ، توجد مجموعة مستقلة بحجم لا يقل عن${\displaystyle n/4}$وبالتالي، تُشكّل العُقد المُزالة جزءًا ضئيلاً من المجموعة المستقلة القصوى، ويمكن إيجاد المجموعات المستقلة القصوى في الرسوم البيانية الفرعية المتبقية بشكل مستقل في وقت يتناسب أُسّيًا مع حجمها. ومن خلال دمج هذا النهج مع طرق الوقت الخطي اللاحقة لبناء التسلسل الهرمي للفواصل ^{[ 20 ]} ومع البحث في الجداول لمشاركة حساب المجموعات المستقلة بين الرسوم البيانية الفرعية المتماثلة ، يُمكن إنشاء مجموعات مستقلة بحجم ضمن عامل${\displaystyle 1-1/{\sqrt {\log n}}}$من الأمثل، في وقت خطي. ومع ذلك، بالنسبة لنسب التقريب الأقرب إلى واحد من هذا العامل، فإن نهجًا لاحقًا لبيكر (1994) (يعتمد على تجزئة الشجرة وليس على الفواصل المستوية) يوفر مقايضات أفضل بين الوقت وجودة التقريب.

استُخدمت مخططات تقريبية مماثلة تعتمد على الفواصل لتقريب مسائل صعبة أخرى مثل تغطية الرؤوس . ^{[ 41 ]} استخدم أرورا وآخرون (1998) الفواصل بطريقة مختلفة لتقريب مسألة البائع المتجول لمقياس أقصر مسار على الرسوم البيانية المستوية الموزونة؛ تستخدم خوارزميتهم البرمجة الديناميكية لإيجاد أقصر مسار يعبر الفاصل عددًا محدودًا من المرات عند كل مستوى من مستويات التسلسل الهرمي للفواصل، وأظهروا أنه مع زيادة حد العبور، فإن المسارات التي تم إنشاؤها بهذه الطريقة لها أطوال تقارب المسار الأمثل.

تُستخدم الفواصل كجزء من خوارزميات ضغط البيانات لتمثيل الرسوم البيانية المستوية وغيرها من الرسوم البيانية القابلة للفصل باستخدام عدد قليل من البتات. ويتمثل المبدأ الأساسي لهذه الخوارزميات في اختيار عدد من البتات.${\displaystyle k}$وقسّم الرسم البياني المستوي المعطى بشكل متكرر باستخدام الفواصل إلى${\displaystyle O(n/k)}$الرسوم البيانية الفرعية ذات الحجم الأقصى${\displaystyle k}$، مع${\displaystyle O(n/{\sqrt {k}})}$الرؤوس في الفواصل. مع اختيار مناسب لـ${\displaystyle k}$( على الأكثر يتناسب مع لوغاريتم${\displaystyle n}$) عدد غير المتماثل${\displaystyle k}$عدد الرسوم البيانية المستوية الفرعية ذات الرؤوس n أقل بكثير من عدد الرسوم البيانية الفرعية في التفكيك، لذا يمكن ضغط الرسم البياني بإنشاء جدول لجميع الرسوم البيانية الفرعية غير المتماثلة الممكنة، وتمثيل كل رسم بياني فرعي في تفكيك الفاصل بفهرسه في الجدول. يمكن تمثيل الجزء المتبقي من الرسم البياني، المُشكّل من رؤوس الفاصل، بشكل صريح أو باستخدام نسخة تكرارية من نفس بنية البيانات. باستخدام هذه الطريقة، يمكن ترميز الرسوم البيانية المستوية والعديد من عائلات الرسوم البيانية الأكثر تقييدًا باستخدام عدد من البتات الأمثل من الناحية النظرية للمعلومات : إذا كان هناك${\displaystyle P_{n}}$${\displaystyle n}$إذا كانت لدينا رسوم بيانية ذات n رأس في عائلة الرسوم البيانية المراد تمثيلها، فيمكن تمثيل رسم بياني فردي في العائلة باستخدام فقط${\displaystyle (1+o(1))\log _{2}P_{n}}$^{[ 42 ]} من الممكن أيضًا إنشاء تمثيلات من هذا النوع حيث يمكن اختبار التجاور بين الرؤوس، وتحديد درجة الرأس، وسرد جيران الرؤوس في وقت ثابت لكل استعلام، وذلك عن طريق إضافة معلومات جدولية إضافية إلى جدول الرسوم البيانية الفرعية تمثل إجابات الاستعلامات . ^{[ 43 ]}

رسم بياني شامل لعائلة${\displaystyle {\mathcal {F}}}$الرسم البياني هو رسم بياني يحتوي على كل عنصر من عناصر${\displaystyle {\mathcal {F}}}$كرسوم بيانية فرعية. يمكن استخدام الفواصل لإظهار أن${\displaystyle n}$تحتوي الرسوم البيانية المستوية ذات الرؤوس على رسوم بيانية شاملة مع${\displaystyle n}$الرؤوس و${\displaystyle O(n^{3/2})}$الحواف. ^{[ 44 ]}

يتضمن هذا البناء شكلاً مُعززاً لنظرية الفاصل، حيث لا يعتمد حجم المجموعات الفرعية الثلاث من الرؤوس في الفاصل على بنية الرسم البياني: يوجد عدد${\displaystyle c}$، والتي لا يتجاوز حجمها عددًا ثابتًا من المرات${\displaystyle {\sqrt {n}}}$بحيث تكون رؤوس كل${\displaystyle n}$يمكن تقسيم الرسم البياني المستوي ذي الرؤوس إلى مجموعات فرعية${\displaystyle A}$،${\displaystyle S}$، و${\displaystyle B}$بدون حواف من${\displaystyle A}$ل${\displaystyle B}$، مع${\displaystyle |S|=c}$ومع${\displaystyle |A|=|B|=(n-c)/2}$يمكن إثبات ذلك باستخدام الصيغة المعتادة لنظرية الفاصل بشكل متكرر لتقسيم الرسم البياني حتى يمكن ترتيب جميع مكونات التقسيم في مجموعتين فرعيتين أقل من${\displaystyle n/2}$الرؤوس، ثم نقل الرؤوس من هذه المجموعات الفرعية إلى الفاصل حسب الضرورة حتى يصبح حجمه كما هو مطلوب.

بمجرد إثبات نظرية فاصلة من هذا النوع، يمكن استخدامها لإنتاج تسلسل هرمي للفواصل لـ${\displaystyle n}$الرسوم البيانية المستوية ذات الرؤوس التي لا تعتمد مرة أخرى على بنية الرسم البياني: يكون لتفكيك الشجرة المتكون من هذا التسلسل الهرمي عرض${\displaystyle O({\sqrt {n}})}$ويمكن استخدامها لأي رسم بياني مستوٍ. تشكل مجموعة جميع أزواج الرؤوس في هذا التفكيك الشجري، والتي تنتمي إلى عقدة مشتركة في التفكيك الشجري، رسمًا بيانيًا مثاليًا بشكل بديهي .${\displaystyle O(n^{3/2})}$الرؤوس التي تحتوي على كل${\displaystyle n}$الرسم البياني المستوي ذو الرؤوس المحدودة كرسم بياني فرعي. يُظهر بناء مماثل أن الرسوم البيانية المستوية ذات الدرجة المحدودة لها رسوم بيانية شاملة مع${\displaystyle O(n\log n)}$الحواف، حيث يعتمد الثابت المخفي في رمز O على حد الدرجة. يجب أن يحتوي أي رسم بياني شامل للرسوم البيانية المستوية (أو حتى للأشجار ذات الدرجة غير المحدودة) على${\displaystyle \Omega (n\log n)}$الحواف. ^{[ 44 ]}

أعلن إسبيريت، جوريت ومورين (2020) أن${\displaystyle O(n^{3/2})}$يمكن تحسين عملية البناء باستخدام الفواصل، إلى${\displaystyle n^{1+o(1)}}$.