TOPICS
Search

Toroidal Crossing Number


The toroidal crossing number cr_(1)(G) of a graph G is the minimum number of crossings with which G 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 G with graph skewness mu(G)<2) also has toroidal crossing number 0. However, there exist graphs with cr_(1)(G)=0 all of whose edge-removed subgraphs are nonplanar, so this condition is sufficient but not necessary.

If a graph G on m>1 edges has toroidal crossing number cr_(1)(G)=0, then cr(G)<(e; 2) (Pach and Tóth 2005), where (n; k) denotes the binomial coefficient. Furthermore, if G is a graph on n vertices with maximum vertex degree Delta which has toroidal crossing number cr_(1)(G)=0, then

 cr(G)<=cDeltan,
(1)

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

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

The crossing number of K_(3,n) on the torus is given by

 nu_t(K_(3,n))=|_((n-3)^2)/(12)_|
(2)

(Guy and Jenkyns 1969, Ho 2005). The first values for n=1, 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 K_(4,n) on the torus is given by

 nu_t(K_(4,n))=1/2|_n/4_|[n-2(1+|_n/4_|)]
(3)

(Ho 2009). The first values for n=1, 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 K_(1,3,n), K_(2,2,n), K_(1,1,2,n), and K_(1,1,1,1,n).

The toroidal crossing numbers for a complete bipartite graph K_(m,n) are summarized in the following table.

m\n123456
1000000
200000
30000
4024
558
612

See also

Graph Crossing Number, Graph Genus, Graph Skewness, Klein Bottle Crossing Number, Nonplanar Graph, Planar Graph, Projective Plane Crossing Number, Rectilinear Crossing Number, Toroidal Graph, Torus

Explore with Wolfram|Alpha

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 K_(m,n)." 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 K_(4,n) on the Real Projective Plane." Disc. Math. 304, 23-33, 2005.Ho, P. T. "The Toroidal Crossing Number of K_(4,n)." 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.

Referenced on Wolfram|Alpha

Toroidal Crossing Number

Cite this as:

Weisstein, Eric W. "Toroidal Crossing Number." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/ToroidalCrossingNumber.html

Subject classifications