Torioidal Crossing Number

Author

Eric W. Weisstein
September 11, 2018

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/ToroidalCrossingNumber.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/ToroidalCrossingNumber.html.

©2018 Wolfram Research, Inc. except for portions noted otherwise

Special cases

Duals on the torus

((Subscript[K, 7]), Heawood) , (Dyck, Shrikhande)

Map[GraphData[#,"ToroidalCrossingNumber"]&,{{"K7","HeawoodGraph"},{"DyckGraph","ShrikhandeGraph"}},{2}]

Parametrized families

Complete

A014543

Table[GraphData[{"Complete",n},"ToroidalCrossingNumber"],{n,20}]

CompleteBipartite 3×n

Richter and Siran 1996

ϵ==2g

A008724

Table[GraphData[{"CompleteBipartite",Sort[{3,n}]},"ToroidalCrossingNumber"],{n,20}]

Table[Floor[(n/6)](n-3(1+Floor[(n/6)])),{n,20}]

Table[Floor[(n-3)^2/12],{n,20}]

Table[Floor[n^2/12],{n,20}]

Series[((x^4)/((((1-x))^2)(((1-x))^6))),{x,0,10}]

FullSimplify[SeriesCoefficient[((x^4)/((((1-x))^2)(1-(x^6)))),{x,0,n}],n∈Integers&&n>0]

Table[(1/72) (-19+6 (n^2)+(((-1))^n) (3-8 Cos[((n π)/3)]+24 Cos[((2 n π)/3)])),{n,20}]

FullSimplify[RSolve[{a[n]==a[n-6]+n+1,a[0]==1,a[1]==2,a[2]==3,a[3]==4,a[4]==5,a[5]==6},a[n],n],n∈Integers&&n>0]

expr=-(1/144) (((-1))^(5/6)) (E^(-(2/3) I n π)) (8 I (1-3 (((-1))^n))-4 (-1+3 (((-1))^n)) (-I+(Sqrt[3])) (E^(-(2/3) I n π))+(I+(Sqrt[3])) (E^((2 I n π)/3)) (77+3 (((-1))^n)+6 n (8+n)));

FullSimplify[expr,n∈Integers&&n>0]

FullSimplify[ExpToTrig[expr],n∈Integers&&n>0]

Table[expr,{n,20}]//FullSimplify

FullSimplify[RSolve[{a[n]==a[n-6]+n-3,a[1]==0,a[2]==0,a[3]==0,a[4]==1,a[5]==2,a[6]==3},a[n],n],n∈Integers&&n>0]

Table[(1/(27 (I+(Sqrt[3]))))((2^(-3-n)) (E^(-(2/3) I n π)) (4 (I+(Sqrt[3])) (9 (((-2))^n)-3 (2^n)+193710241 (((-1-I (Sqrt[3])))^n))-12 (((-1+I (Sqrt[3])))^n) (-4 I+6 (Sqrt[3])+(-I+3 (Sqrt[3])) n)-4 (E^((I n π)/3)) ((2^n) (-9+193710244 (((-1))^n)) (I+(Sqrt[3]))+2 (((1+I (Sqrt[3])))^n) (-290565369 I+96855128 (Sqrt[3])+3 (Sqrt[3]) n))+(2^n) (E^((2 I n π)/3)) (-2324523057 I+774841039 (Sqrt[3])+9 (((-1))^n) (I+(Sqrt[3]))+6 n (-2 I+10 (Sqrt[3])+3 (I+(Sqrt[3])) n)))),{n,20}]//FullSimplify

Table[-(1/144) (((-1))^(5/6)) (E^(-(2/3) I n π)) (8 I (1-3 (((-1))^n))-4 (-1+3 (((-1))^n)) (-I+(Sqrt[3])) (E^(-(2/3) I n π))+(I+(Sqrt[3])) (E^((2 I n π)/3)) (77+3 (((-1))^n)+6 n (8+n))),{n,0,20}]//FullSimplify

expr1=(1/72) (-19+6 (n^2)+(((-1))^n) (3-8 Cos[((n π)/3)]+24 Cos[((2 n π)/3)]));
expr2=(1/72) (77+3 (((-1))^n)+2 I (-1+3 (((-1))^n)) (E^(-(4/3) I n π)) (I+(Sqrt[3])-(-I+(Sqrt[3])) (E^((2 I n π)/3)))+6 n (8+n))/.n->n-1;

FullSimplify[expr1-expr2,n∈Integers]

Table[(1/12) (-9+(((-1))^n)-6 n+8 Cos[((n π)/3)]),{n,4}]

CompleteBipartite 4×n

MR2526742 (2010i:05088) Reviewed 
Ho, Pak Tung(1-PURD)
The toroidal crossing number of (Subscript[K, 4,n])
Discrete Math. 309 (2009), no. 10, 3238–3248.

Table[GraphData[{"CompleteBipartite",Sort[{4,n}]},"ToroidalCrossingNumber"],{n,20}]

A182568

seq=Table[2Floor[n/4](n-2(1+Floor[n/4])),{n,100}]

FullSimplify[FindSequenceFunction[seq,n],n∈Integers&&n>0]

Table[(5-(((-1))^n)+2 (n-4) n-4 Cos[((n π)/2)])/8,{n,20}]

FindLinearRecurrence[seq]

LinearRecurrence[{2,-1,0,1,-2,1},{0,0,0,0,2,4},20]

gf=x FindGeneratingFunction[seq,x]

CoefficientList[Series[-((2 x^4)/((((-1+x))^3) (1+x+(x^2)+(x^3)))),{x,0,20}],x]

SeriesCoefficient[gf,{x,0,n}]

FullSimplify[%,n>0&&n∈Integers]

Table[(5-(((-1))^n)-2 (((-I))^n)-2 (I^n)-8 n+2 (n^2))/8,{n,20}]

CompleteTripartite 1×3×n

MR2526742 (2010i:05088) Reviewed 
Ho, Pak Tung(1-PURD)
The toroidal crossing number of (Subscript[K, 4,n])
Discrete Math. 309 (2009), no. 10, 3238–3248.

Table[GraphData[{"CompleteTripartite",Sort[{1,3,n}]},"ToroidalCrossingNumber"],{n,10}]

A182568

seq=Table[2Floor[n/4](n-2(1+Floor[n/4])),{n,100}]

CompleteTripartite 2×2×n

MR2526742 (2010i:05088) Reviewed 
Ho, Pak Tung(1-PURD)
The toroidal crossing number of (Subscript[K, 4,n])
Discrete Math. 309 (2009), no. 10, 3238–3248.

Table[GraphData[{"CompleteTripartite",Sort[{2,2,n}]},"ToroidalCrossingNumber"],{n,10}]

A182568

seq=Table[2Floor[n/4](n-2(1+Floor[n/4])),{n,100}]

Nonplanar connected graphs for which removal of exactly 1 edge (and no others) gives planarity

list=Monitor[Select[GraphData[{"Nonplanar","Connected"},;;20],Function[g,Count[PlanarGraphQ[EdgeDelete[GraphData[gg=g],#]]&/@EdgeList[GraphData[g]],True]===1]],gg];//Timing

Length[list]

SortBy[list,GraphData[#,"V"]&]

data=Function[g,{g,SelectFirst[EdgeList[GraphData[g]],PlanarGraphQ[EdgeDelete[GraphData[g],#]]&]}]/@list

{#1,HighlightGraph[GraphData[#1],#2],PlanarGraph[EdgeList[d=EdgeDelete[GraphData[#1],#2]]],RecognizeGraph[d]}&@@@data

Testing

A graph has TCN == 0 if RCN < 2

A graph has TCN == 0 if removal of a single edge makes it planar

ToroidalCrossingNumber[g_System`Graph]:=Module[{i=1,m=EdgeCount[g],e=EdgeList[g]},
If[PlanarGraphQ[g],Return[0]];
While[i≤m&&!PlanarGraphQ[EdgeDelete[g,e[[i]]]],i++];
If[i>m,Missing["NotAvailable"],0]
]

DeleteCases[{#,GraphData[#,"ToroidalCrossingNumber"],GraphData[#,"Skewness"]}&/@GraphData[;;10],{_,0,0|1}|{_,_,_?(GreaterThan[1])}|{_,_,_Missing}]