Toroidal Crossing Number

The toroidal crossing number  of a graph  is the minimum number of crossings with which  can be drawn on a torus.

A planar graph has toroidal crossing number 0, and a nonplanar graph with toroidal crossing number 0 is called a toroidal graph. A nonplanar graph with toroidal crossing number 0 has graph genus 1 since it can be embedded on a torus (but not in the plane) with no crossings.

A graph having graph crossing number or rectilinear crossing number less than 2 has toroidal crossing number 0. More generally, a graph that becomes planar after the removal of a single edge (in other words, a graph  with graph skewness ) also has toroidal crossing number 0. However, there exist graphs with  all of whose edge-removed subgraphs are nonplanar, so this condition is sufficient bit not necessary.

If a graph  on  edges has toroidal crossing number , then  (Pach and Tóth 2005), where  denotes the binomial coefficient. Furthermore, if  is a graph on  vertices with maximum vertex degree  which has toroidal crossing number , then

(1)

where  is a positive constant (Pach and Tóth 2005).

The toroidal crossing numbers for a complete graph  for , 2, ... are 0, 0, 0, 0, 0, 0, 0, 4, 9, 23, 42, 70, 105, 154, 226, 326, ... (OEIS A014543).

The crossing number of  on the torus is given by

(2)

(Guy and Jenkyns 1969, Ho 2005). The first values for , 2, ... are therefore 0, 0, 0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 8, 10, 12, 14, 16, ... (OEIS A008724).

The crossing number of  on the torus is given by

(3)

(Ho 2009). The first values for , 2, ... are therefore 0, 0, 0, 0, 2, 4, 6, 8, 12, 16, 20, 24, 30, 36, ... (OEIS A182568). Interestingly, the same result holds for , , , and .

The toroidal crossing numbers for a complete bipartite graph  are summarized in the following table.

	1	2	3	4	5	6
1	0	0	0	0	0	0
2		0	0	0	0	0
3			0	0	0	0
4				0	2	4
5					5	8
6						12

---

REFERENCES

Altshuler, A. "Construction and Enumeration of Regular Maps on the Torus." Disc. Math. 4, 201-217, 1973.

Gardner, M. "Crossing Numbers." Ch. 11 in Knotted Doughnuts and Other Mathematical Entertainments. New York: W. H. Freeman, pp. 133-144, 1986.

Guy, R. K. and Jenkyns, T. "The Toroidal Crossing Number of ." J. Combin. Th. 6, 235-250, 1969.

Guy, R. K.; Jenkyns, T.; and Schaer, J. "Toroidal Crossing Number of the Complete Graph." J. Combin. Th. 4, 376-390, 1968.

Harary, F. and Palmer, E. M. "A Survey of Graph Enumeration Problems." In A Survey of Combinatorial Theory (Ed. J. N. Srivastava). Amsterdam: North-Holland, pp. 259-275, 1973.

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

Ho, P. T. "The Toroidal Crossing Number of ." Disc. Math. 309, 3238-3248, 2009.

Pach, J. and Tóth, G. "Thirteen Problems on Crossing Numbers." Geocombin. 9, 195-207, 2000.

Pach, J. and Tóth, G. "Crossing Number of Toroidal Graphs." In International Symposium on Graph Drawing (Ed. P. Healy and N. S. Nikolov). Berlin, Heidelberg: Springer-Verlag: pp. 334-342, 2005.

Riskin, A. "On the Nonembeddability and Crossing Numbers of Some Toroidal Graphs on the Klein Bottle." Disc. Math. 234, 77-88, 2001.

Sloane, N. J. A. Sequences A008724, A014543, and A182568 in "The On-Line Encyclopedia of Integer Sequences."Thomassen, C. "Tilings of the Torus and the Klein Bottle and Vertex-Transitive Graphs on a Fixed Surface." Trans. Amer. Math. Soc. 323, 605-635, 1991.

اخر الاخبار

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

شعبة مدارس الكفيل تنظم ورشة عن التمكين الإرشادي ومهارات التعامل مع الأطفال واليافعين

العتبة العباسية المقدسة تستقبل وفود المؤتمر العلمي الدولي للسيد المجاهد (قدس سره)

قسم شؤون المعارف يقيم ندوة تعريفية عن مؤتمر التراث البصري في جامعة بابل

شعبة التوجيه الديني النسوي تقيم مجلس عزاء بذكرى وفاة السيدة زينب (عليها السلام)

المزيد

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

طبيب يكشف أفضل مكمل غذائي لتحسين المزاج ودعم الصحة النفسية

دراسة جديدة تكشف أضرار الأطعمة الجاهزة على القلب ؟

6 أطعمة طبيعية تهدئ الزكام دون أدوية.. تعرف عليهم

ماذا يحدث لأعراض الزكام عند تناول الثوم بانتظام؟

المزيد

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

ابتكار ثوري في بطاريات السيارات الكهربائية.. سعة أعلى 4 مرات

ماذا يحدث لجسمك عند شرب الماء الساخن يوميا؟

7 فوائد "خفية" لشرب شاي الكركديه كل يوم

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

المزيد

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

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