Projective Plane Crossing Number

The projective plane crossing number of a graph is the minimal number of crossings with which the graph can be drawn on the real projective plane.

All graphs with graph crossing number 0 or 1 (i.e., planar and singlecross graphs) have projective plane crossing number 0.

A graph with projective plane crossing number equal to 0 may be said to be projective planar. Examples of projective planar graphs with graph crossing number  include the complete graph  and Petersen graph .

Embeddability in the projective plane (i.e., graphs with projective plane crossing number 0) are characterized by a set of exactly 35 forbidden graph minors (Glover et al. 1979; Archdeacon 1981; Hlinenỳ 2010; Shahmirzadi 2012, p. 7, Fig. 1.1). Note that this set includes the graph unions  and , each member of which is embeddable in the projective plane. This means that, unlike planar graphs, disjoint unions of graphs which are embeddable in the projective plane may not themselves be embeddable. As of 2022, the plane and projective plane are the only surfaces for which a complete list of forbidden minors is known (Mohar and Škoda 2020).

Richter and Siran (1996) computed the crossing number of the complete bipartite graph  on an arbitrary surface. Ho (2005) showed that the projective plane crossing number of  is given by

For , 2, ..., the first few values are therefore 0, 0, 0, 2, 4, 6, 10, 14, 18, 24, ... (OEIS A128422).

---

REFERENCES

Archdeacon, D. "A Kuratowski Theorem for the Projective Plane." J. Graph Th. 5, 243-246, 1981.

Glover, H.; Huneke, J. P.; and Wang, C. S. "103 Graphs That Are Irreducible for the Projective Plane." J. Combin. Th. Ser. B 27, 332-370, 1979.

Hlinenỳ, P. "20 Years of Negami's Planar Cover Conjecture." Graphs and Combinatorics 26, 525-536, 2010.

Ho, P. T. "The Crossing Number of  on the Real Projective Plane." Disc. Math. 304, 23-33, 2005.

Mohar, B. and Škoda, P. "Excluded Minors for the Klein Bottle I. Low Connectivity Case." 1 Feb 2020. https://arxiv.org/abs/2002.00258.Richter, R. B. and Širáň, J. "The Crossing Number of  in a Surface." J. Graph Th. 21, 51-54, 1996.

Shahmirzadi, A. S. "Minor-Minimal Non-Projective Planar Graphs with an Internal 3-Separation." Ph.D. thesis. Atlanta, GA: Georgia Institute of Technology. Dec. 2012.

Sloane, N. J. A. Sequence A128422 in "The On-Line Encyclopedia of Integer Sequences."

اخر الاخبار

اخبار العتبة العباسية المقدسة

برعاية العتبة العباسية المقدسة.. جمعية العميد تفتح باب المشاركة في مؤتمر فتاوى الدفاع المقدسة العلمي السابع

قسم التطوير يواصل تقديم دورة أخلاقيات المهنة ضمن البرنامج التأهيلي لمنتسبي العتبة العباسية المقدسة

قسم الشؤون الفكرية يُهدي عددًا من إصداراته الثقافية لمكتبة السيدة زينب (عليها السلام) في النجف

العتبة العباسية المقدسة تشارك في الاجتماع الأول للجنة الوطنية الدائمة لتعزيز ذاكرة الألم في العراق

المزيد

الآخبار الصحية

حالة صحية شائعة قد تُخفي "إنذارا مبكرا" للإصابة بالسرطان !

"أوميغا 3" صديق القلب.. هل يربك سكر الدم؟

بدائل لليمون.. 8 إضافات للماء تعزز فوائده الصحية

دراسة: محاولة متعمدة لنشر الإنفلونزا تنتهي بـ"مفاجأة"

المزيد

الآخبار التكنلوجية

سلامة الأطفال: سبع قواعد ذهبية للركوب الآمن بالسيارة

توقع خطير لماسك: الروبوتات ستتفوق على البشر من حيث العدد

دراسة تكشف عاملا غير متوقع يرتبط بزيادة خطر الإصابة بالتوحد

"ميتا" توقف وصول المراهقين إلى شخصيات الذكاء الاصطناعي ؟

المزيد

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength