مخطط مستوي

في المخططات، المخطط المستوي هو المخطط الذي يقبل تمثيلا في المستوى، بحيث لا يتقاطع أي ارتباطين من المخطط.

فهرست

حسب Kuratowski يكون المخطط مستويا إذا لم يتضمن زمرة من الرتبة 5، أو مخطط ثنائي كامل من الرتبة 3 (انظر الصور).

مخطط ثنائي كامل من الرتبة 3

زمرة من الرتبة 5

ليكن G مخطط مستوي، الوجه F هو أكبر منطقة من المستوى محددة بمجموعة ارتباطات G و لا تتضمن أيا منها.

ليكن G مخطط مستوي، و a عدد ارتباطات G. إذن : $\sum_{F}^{} deg (F) = 2a$

المسار ذو الطول r هو سلسلة $(S 0,..., S r)$ من القمم المرتبطة مع $S 0$ أصل السبيل و $S r$ طرفه.
يكون المخطط متصلا إذا وُجد مسار بين كل قمتين من G.
المسار المغلق هو حالة $S 0 = S r$ .
الشجرة هي مخطط متصل بدون أي مسار مغلق.

كل مخطط متصل يمكن الحصول عليه بإضافة عدة قمم لشجرة (لها نفس عدد القمم).

ليكن G مخطط مستوي متصل. ليكن n عدد قمم a, G عدد ارتباطاته و f عدد وجوهه. إذن: n − a + f = 2

تحديد المعايير التي تمكن من معرفة ان كان مخطط ما مستويا. ليكن G مخطط مستوي متصل. ليكن n عدد قمم a, G عدد ارتباطاته:

Edge Addition Planarity Algorithm Source Code — Free C source code for reference implementation of Boyer-Myrvold planarity algorithm, which provides both a combinatorial planar embedder and Kuratowski subgraph isolator.
Public Implementation of a Graph Algorithm Library and Editor — GPL graph algorithm library including planarity testing, planarity embedder and Kuratowski subgraph exhibition in linear time.
3 Utilities Puzzle and Planar Graphs
Planarity — A puzzle game created by John Tantalo.
Mindgames nTangle Freeware nTangle puzzle program with 20,000puzzles