TOPICS
Search

Torus Grid Graph


The torus grid graph T_(m,n) is the graph formed from the graph Cartesian product C_m square C_n of the cycle graphs C_m and C_n. C_m square C_n is isomorphic to C_n square C_m.

TorusGridGraph3DEmbeddings

C_m square C_n can be formed starting with an m×n 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 C_(10) square C_6 and C_6 square C_(10) are illustrated above.

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

 |C_m square C_n|=mn.
(1)
TorusGridGraph

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

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

 cr(C_m square C_n)=(m-2)n
(2)

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

 cr(C_m square C_n)>=(0.8-epsilon)mn
(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 C_m square C_n with m<=n for m=3, 4, 5, 6 are 1, 2, 4, and 6, respectively.

The torus grid graph C_4 square C_n is unit-distance since it is isomorphic to the graph Cartesian product Y_n square K_2, where Y_n is the n-prism graph (which is itself unit-distance).


See also

Graph Cartesian Product, Grid Graph, Toroidal Graph

Explore with Wolfram|Alpha

References

Adamsson, J. and Richter, R. B. "Arrangements, Circular Arrangements and the Crossing Number of C_7×C_n." 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 C_m×C_n: 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.

Cite this as:

Weisstein, Eric W. "Torus Grid Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/TorusGridGraph.html

Subject classifications