Torus Grid Graph

The torus grid graph  is the graph formed from the graph Cartesian product  of the cycle graphs  and .  is isomorphic to .

 can be formed starting with an  grid graph and connecting corresponding left/right and top/bottom vertex pairs with edges. While such an embedding has overlapping edges in the plane, it can naturally be placed on the surface of a torus with no edge intersections or overlaps. Torus grid graphs are therefore toroidal graphs. The isomorphic torus grid graphs  and  are illustrated above.

The torus grid graphs are quartic and Hamiltonian and have vertex count

(1)

Torus grid graphs are circulant graphs iff  and  are relatively prime, i.e., . In such cases,  is isomorphic to . Special cases are summarized in the following table and illustrated above in attractive (but non-toroidal) embddings.

	graph
	circulant graph
	generalized quadrangle
	quartic vertex-transitive graph Qt65
	tesseract graph

Harary et al. (1973) conjectured that the graph crossing number is given by

(2)

for all  satisfying  (Clancy et al. 2019). The conjecture is now known to hold for  (Adamsson and Richter 2004 and earlier work cited therein). An asymptotic lower bound of

(3)

was given by Salazar and Ugalde (2004). Clancy et al. (2019) summarize additional results and details.

Riskin (2001) showed that the Klein bottle crossing numbers of  with  for , 4, 5, 6 are 1, 2, 4, and 6, respectively.

The torus grid graph  is unit-distance since it is isomorphic to the graph Cartesian product , where  is the -prism graph (which is itself unit-distance).

---

REFERENCES

Adamsson, J. and Richter, R. B. "Arrangements, Circular Arrangements and the Crossing Number of ." J. Combin. Theory 90, 21-39, 2004.

Harary, F.; Kainen, P. C.; and Schwenk, A. J. "Toroidal Graphs with Arbitrarily High Crossing Numbers." Nanta Math. 6, 58-67, 1973.

Clancy, K.; Haythorpe, M.; and Newcombe, A. §3.1.1 in "A Survey of Graphs with Known or Bounded Crossing Numbers." 15 Feb 2019.

 https://arxiv.org/abs/1901.05155.Lawrencenko, S. and Negami, S. "Constructing the Graphs That Triangulate Both the Torus and the Klein Bottle." J. Combin. Theory Ser. B 77, 211-2218, 1999.

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.

Salazar, G. and Ugalde, E. "An Improved Bound for the Crossing Number of : A Self-Contained Proof Using Mostly Combinatorial Arguments." Graphs Combin. 20, 247-253, 2004.

Stewart, I. Fig. 41 in How to Cut a Cake: And Other Mathematical Conundrums. Oxford, England: Oxford University Press, 2006.

اخر الاخبار

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

بمشاركة الأمين العام للعتبة العبّاسية المقدّسة.. موكب عزاء السادة الخَدَم يحيي ليلة عاشوراء

صحفيّون يشيدون بالتسهيلات الإعلامية التي تقدّمها العتبة العباسية المقدّسة خلال زيارة عاشوراء

أهالي كربلاء ينظّمون مسيرة الشموع الحسينية إحياءً لليلة العاشر من شهر المحرّم

عبر مجلس عزاء.. العتبة العباسية المقدّسة تحيي ليلة اليوم العاشر من المحرّم

المزيد

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

لهذا السبب.. إغلاق 25 مركزًا لعلاج الإدمان في مصر ؟

خلافا للاعتقاد الشائع.. علماء يكشفون أسرار بذور البطيخ ؟!

هذا ما يحدث لجسمك عند تناولك الطماطم بانتظام !

تعرف على أطعمة تسرّع "تعافي الجسم" من حروق الشمس

المزيد

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

الثلوج تغطي الصحراء الأكثر جفافا في العالم!

بتلسكوب "ألما".. التقاط صورا غير مسبوقة لبدايات الكون !

هل هاتفك مراقب؟.. 5 علامات خطيرة تكشف التجسس عليك

دبي تطلق أول رحلة تجريبية للتاكسي الجوي

المزيد

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

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