Graph Crossing Number

Author

Eric W. Weisstein
February 1, 2024

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

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

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

Sources

https://mathematica.stackexchange.com/questions/189694/mathematica-package-to-calculate-the-graph-crossing-number

https://sites.flinders.edu.au/flinders-hamiltonian-cycle-project/quickcross-crossing-number-problem/

http://crossings.uos.de [internal error as of Jan 2024]

https://ask.sagemath.org/question/63863/the-function-crossing_number-runs-too-slowly/

https://ogdf.uos.de/about/

https://ogdf.github.io/doc/ogdf/classogdf_1_1_crossing_minimization_module.html#a0ae5e91d7668a11b92504f5087192f78

Tallies

Notes:
Exoo RCN tallies are wrong for at least 9 connected graphs listed as RCN = 2 but actually = 1
QuickCross with default embedding scheme -e 3 gives suboptimal crossing numbers for graphs as small as 8 nodes, e.g., {"Queen", {2, 4}}, (though I don't know if it can claim CN = 1 graphs have CN >1)

SetDirectory["/Users/eww/Documents/Mathematica/Paclets/GraphData/Nodes/CrossingNumber"]

Sort[Tally[#]]&/@crossingdata//Column

GraphDataCountTable

<<MathWorld`Graphs`

planarclasses=Select[Cases[MathWorld`Graphs`Private`$NiceClasses,_String],GraphData[#]===GraphData[{#,"Planar"}]&]

rules=Join[Thread[planarclasses->000007],{"Barbell"->302647,"CocktailParty"->033487,"Complete"->028723,"CompleteBipartite"->030179,"Crown"->307182,"PathComplement"->028723,"StackedBook"->128624,"TorusGrid"->005563}];

GraphDataCountTable["CrossingNumber",rules]

Parametrized families

Andrasfai

TextGrid[Table[Prepend[GraphData[{"Andrasfai",n},{"#","V","M","CN"}],n],{n,10}],Alignment->Decimal,Dividers->{{None,True}}]

Dear Eric Weisstein,

we have successfully computed the crossing number of your graph (Wagner graph).
The graph has a crossing number of 1.

Please visit this link for detailed results: http://crossings.uos.de/job/u1Ma_vuHclggaTmdp2fWQQ

Dear Eric Weisstein,

we have successfully computed the crossing number of your graph (4-Andrasfai).
The graph has a crossing number of 5.

Please visit this link for detailed results: http://crossings.uos.de/job/r7BqbS10aVLWSXqoOYPb5A

Dear Eric Weisstein,

we are sorry to report that the requested computation (5-Andrasfai) failed.
Please contact Markus Chimani (http://www-lehre.informatik.uni-osnabrueck.de/theoinf/index/staff/chimani)
if you really need to compute the crossing number of this graph.

Please visit this link for detailed results: http://crossings.uos.de/job/C1Ih6SlD7NSsOgUwzhEI3A

Dear Eric Weisstein,

we are sorry to report that the requested computation (6-Andrasfai) failed.
Please contact Markus Chimani (http://www-lehre.informatik.uni-osnabrueck.de/theoinf/index/staff/chimani)
if you really need to compute the crossing number of this graph.

Please visit this link for detailed results: http://crossings.uos.de/job/qqPxUuYyWMg9uDhZ86YAIA

seq=Table[GraphData[{"Andrasfai",n},"CrossingNumber"],{n,10}]

(seq=Table[CrossingNumber[GraphData[{"Andrasfai",n}],MaxIterations->100],{n,8}])//Timing

(seq=Table[CrossingNumber[GraphData[{"Andrasfai",n}],Method->1,MaxIterations->100],{n,8}])//Timing

(seq=Table[CrossingNumber[GraphData[{"Andrasfai",n}],Method->2,MaxIterations->100],{n,8}])//Timing

(seq=Table[CrossingNumber[GraphData[{"Andrasfai",n}],MaxIterations->200],{n,8}])//Timing

(seq=Table[CrossingNumber[GraphData[{"Andrasfai",n}],MaxIterations->500],{n,8}])//Timing

Antiprism

Entity["Graph",{"Antiprism",n}]["CrossingNumber"]

seq=Table[GraphData[{"Antiprism",n},"CrossingNumber"],{n,3,25}]

Apollonian

seq=Table[GraphData[{"Apollonian",n},"CrossingNumber"],{n,6}]

BananaTree

Block[{m,n},DeleteCases[{#,{m,n}="BananaTree"/.GraphData[#,"NotationRules"];0,GraphData[#,"CrossingNumber"]}&/@GraphData["BananaTree"],{_,x_,x_}]]

Barbell

A302647

seq=Table[GraphData[{"Barbell",n},"CrossingNumber"],{n,3,20}]

FindSequenceFunction[seq,n]//FullSimplify

Table[(1-(((-1))^n)-2 (3+(((-1))^n)) (n^2)+2 (n^4))/64,{n,20}]

coef=FindLinearRecurrence[seq]

Take[seq,Length@coef]

LinearRecurrence[{2,2,-6,0,6,-2,-2,1},{0,0,2,6,18,36,72,120},20]

gf=x FindGeneratingFunction[seq,x]//FullSimplify

SeriesCoefficient[-((2 (x^3) (1+x+(x^2)))/((((-1+x))^5) (((1+x))^3))),{x,0,n}]

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

Bishop n×n

seq=Table[GraphData[{"Bishop",{n,n}},"CrossingNumber"],{n,10}]

BlackBishop n×n

seq=Table[GraphData[{"BlackBishop",{n,n}},"CrossingNumber"],{n,2,10}]

Bruhat

seq=Table[GraphData[{"Bruhat",n},"CrossingNumber"],{n,6}]

Table[CrossingNumber[GraphData[{"Bruhat",n}]],{n,6}]//AbsoluteTiming

Table[CrossingNumber[GraphData[{"Bruhat",n}],MaxIterations->10],{n,6}]//AbsoluteTiming

Table[CrossingNumber[GraphData[{"Bruhat",n}],MaxIterations->100],{n,6}]//AbsoluteTiming

Table[CrossingNumber[GraphData[{"Bruhat",n}],Method->1,MaxIterations->10],{n,6}]//AbsoluteTiming

CocktailParty

A033487

seq=Table[GraphData[{"CocktailParty",n},"CrossingNumber"],{n,20}]

seq={0,0,0,6,30,90,210}

Do[Print[{n,CrossingNumber[GraphData[{"CocktailParty",n}]]//Timing}],{n,10}]

Table[6 Binomial[n,4],{n,10}]

Do[Print[{n,CrossingNumber[GraphData[{"CocktailParty",n}],TimeConstraint->10]//Timing}],{n,10}]

Complete

A000241

Entity["Graph",{"Complete",n}]["CrossingNumber"]

Verified up to n = 12

seq=Table[GraphData[{"Complete",n},"CrossingNumber"],{n,20}]

https://arxiv.org/pdf/1804.09900.pdf, pp. 24-25

For these graphs, we observe that when n was odd, every scheme combination was able to obtain a drawing with H(n) crossings. However, when n was even, each scheme reached a value which was usually very close but not equal to H(n). The average runtime under the best scheme is significantly higher than the other minimisation schemes simply due to the vast amount of additional work required to consider every vertex each iteration.

Overall, the planar initial embedding scheme performed the best in terms of both solution quality and total execution time for these instances.

Default ("Use Planar embedding") embedding scheme: -e 3 and default ("use improvements when found") minimization scheme: -m 2

QC -e 3 -c 1 14 -r 1 -z 10000

Do[Print[{n,CrossingNumber[GraphData[{"Complete",n}],TimeConstraint->10]//AbsoluteTiming}],{n,8,20}]

Do[Print[{n,CrossingNumber[CompleteGraph[n],"UpperBound"->Floor[n/2]Floor[(n-1)/2]Floor[(n-2)/2]Floor[(n-3)/2]/4]//AbsoluteTiming}],{n,30}]

Do[Print[{n,CrossingNumber[CompleteGraph[n],"MinimizationScheme"->3,"UpperBound"->Floor[n/2]Floor[(n-1)/2]Floor[(n-2)/2]Floor[(n-3)/2]/4]//AbsoluteTiming}],{n,30}]

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

Times@@@Table[Floor[(n-k)/2],{n,0,20},{k,0,3}]/4

14

seq[[14]]

<<MathWorld`Graphs`

CrossingNumber[CompleteGraph[14],TimeConstraint->10]//AbsoluteTiming

CrossingNumber[CompleteGraph[14],"MinimizationScheme"->3,"UpperBound"->seq[[14]]]//AbsoluteTiming

18

seq[[18]]

Current best soln: 1011, at seed: 2, current seed: 810000

CrossingNumber[CompleteGraph[18],TimeConstraint->10]//AbsoluteTiming

CrossingNumber[CompleteGraph[18],"MinimizationScheme"->3,"UpperBound"->seq[[18]]]//AbsoluteTiming

CompleteBipartite 3×n

MR1363689 (96i:05054) Reviewed 
Richter, R. Bruce(3-CARL); Širáň, J.(SK-KMSK)
The crossing number of (Subscript[K, 3,n]) in a surface. (English summary) 
J. Graph Theory 21 (1996), no. 1, 51–54.

MR0280403 (43 #6123) Reviewed 
Kleitman, Daniel J.
The crossing number of (Subscript[K, 5,n]). 
J. Combinatorial Theory 9 1970 315–323.

A002620(n-1)

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

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

Table[Ceiling[(n-1)/2]Floor[(n-1)/2],{n,20}]

Table[Floor[(((n-1))^2)/4],{n,20}]

Table[Floor[(n^2)/4],{n,0,20}]

Floor[((Range[0,20])^2)/4]

gf=x FindGeneratingFunction[seq,x]

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

CompleteBipartite 4×n

A007590

MR0280403 (43 #6123) Reviewed 
Kleitman, Daniel J.
The crossing number of (Subscript[K, 5,n]). 
J. Combinatorial Theory 9 1970 315–323.

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

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

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

Floor[((Range[0,20])^2)/2]

With[{m=4},Floor[m/2]Floor[(m-1)/2]]

Table[2Floor[n/2]Floor[(n-1)/2],{n,20}]

CompleteBipartite 5×n

MR0280403 (43 #6123) Reviewed 
Kleitman, Daniel J.
The crossing number of (Subscript[K, 5,n]). 
J. Combinatorial Theory 9 1970 315–323

A137932

Table[GraphData[{"CompleteBipartite",Sort[{5,n}]},"CrossingNumber"],{n,20}]

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

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

2Floor[(((Range[20]-1))^2)/2]

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

FindLinearRecurrence[seq]

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

gf=x FindGeneratingFunction[seq,x]

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

FullSimplify[%,n>0]

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

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

CompleteBipartite 6×n

MR1363689 (96i:05054) Reviewed 
Richter, R. Bruce(3-CARL); Širáň, J.(SK-KMSK)
The crossing number of (Subscript[K, 3,n])
in a surface. (English summary) 
J. Graph Theory 21 (1996), no. 1, 51–54.

MR0280403 (43 #6123) Reviewed 
Kleitman, Daniel J.
The crossing number of (Subscript[K, 5,n]). 
J. Combinatorial Theory 9 1970 315–323

A319127

Table[GraphData[{"CompleteBipartite",Sort[{6,n}]},"CrossingNumber"],{n,20}]

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

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

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

Table[(3/4) (((-1))^n) ((((-1))^n) (1+2 (n-2)n)-1),{n,20}]

FindLinearRecurrence[seq]

LinearRecurrence[{2,0,-2,1},{0,0,6,12},20]

gf=x FindGeneratingFunction[seq,x]

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

FullSimplify[%,n>0]

Table[(3/4) (2 (n^2)-4n+1-(((-1))^n)),{n,20}]

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

CompleteBipartite m×n

A298368

Entity["Graph",{"CompleteBipartite",{m,n}}]["CrossingNumber"]

Table[Floor[(1/2) (-1+m)] Floor[(m/2)] Floor[(1/2) (-1+n)] Floor[(n/2)],{n,10},{m,n}]//Column

Table[Floor[(m-1)/2] Floor[(m/2)] Floor[(n-1)/2] Floor[(n/2)],{n,11},{m,n}]//Flatten

Table[Times@@Floor[{m,m-1,n,n-1}/2],{n,11},{m,n}]//Flatten

seq=Table[GraphData[{"CompleteBipartite",{m,n}},"CrossingNumber"],{n,20},{m,n}]//Column//TraditionalForm

CompleteBipartite n×n

A030179

Conjectured to be crossing number of complete bipartite graph K_{n,n}. Known to be true for n <= 7.

Entity["Graph",{"CompleteBipartite",{n,n}}]["CrossingNumber"]

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"CrossingNumber"],{n,20}]

Table[((Floor[(1/4) (((-1+n))^2)])^2),{n,20}]

CompleteTripartite k×m×n

Entity["Graph",{"CompleteTripartite",{k,m,n}}]["CrossingNumber"]

seq=Table[{GraphData[{"CompleteTripartite",{k,m,n}},"CrossingNumber"],((2^k)-1)((2^m)-1)((2^n)-1)},{n,10},{m,n},{k,m}]

CompleteTripartite n×n×n

Entity["Graph",{"CompleteTripartite",{n,n,n}}]["CrossingNumber"]

seq=Table[GraphData[{"CompleteTripartite",{n,n,n}},"CrossingNumber"],{n,10}]

Table[CrossingNumber[GraphData[{"CompleteTripartite",{n,n,n}}]],{n,10}]//AbsoluteTiming

(seq=Table[CrossingNumber[CompleteGraph[{n,n,n}]],{n,15}])//AbsoluteTiming

(seq=Table[CrossingNumber[CompleteGraph[{n,n,n}],MaxIterations->10],{n,15}])//AbsoluteTiming

(seq=Table[CrossingNumber[CompleteGraph[{n,n,n}],Method->1,MaxIterations->10],{n,15}])//AbsoluteTiming

(seq=Table[CrossingNumber[CompleteGraph[{n,n,n}],MaxIterations->100],{n,15}])//AbsoluteTiming

FindSequenceFunction[Drop[seq,2],n-2]//Head//Timing

FindGeneratingFunction[seq,x]//Head//Timing

FindLinearRecurrence[Drop[seq,3]]//Head//Timing

CrossedPrism

Table[GraphData[{"CrossedPrism",2n}],{n,2,5}]

seq=Table[GraphData[{"CrossedPrism",2n},"CrossingNumber"],{n,2,10}]

Table[CrossingNumber[GraphData[{"CrossedPrism",2n}],MaxIterations->100],{n,2,10}]//AbsoluteTiming

Table[CrossingNumber[GraphData[{"CrossedPrism",2n}],MaxIterations->200],{n,2,10}]//AbsoluteTiming

Crown

Table[GraphData[{"Crown",n}],{n,3,5}]

GraphData[{"Crown",5},"Graph","All"]

A307182

seq=Table[GraphData[{"Crown",n},"CrossingNumber"],{n,3,20}]

StringReplace[ExportString[GraphData[{"Crown",7}],"Graph6"],">>graph6<<"|"\n"->""]//InputForm

ToString[StringReplace[ExportString[GraphData[{"Crown",8}],"Graph6"],">>graph6<<"|"\n"->""]]

(seq=Table[CrossingNumber[GraphData[{"Crown",n}],MaxIterations->10],{n,3,20}])//AbsoluteTiming

Table[CrossingNumber[GraphData[{"Crown",n}],MaxIterations->20],{n,3,20}]//AbsoluteTiming

FullSimplify[FindSequenceFunction[seq,n-2]]

Table[(1/32) (2 (n-4) n (n^2-4n+5)-(2n^2-8n+9)(((-1))^n)+9),{n,80}]

gf=(x^3)FindGeneratingFunction[seq,x]//Factor

SeriesCoefficient[-((4 (x^5) (1+x+(x^2)))/((((-1+x))^5) (((1+x))^3))),{x,0,n}]

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

coef=FindLinearRecurrence[seq]

Take[seq,Length[coef]]

LinearRecurrence[{2,2,-6,0,6,-2,-2,1},{0,0,0,0,4,12,36,72},20]

CubeConnectedCycle

Entity["Graph",{"CubeConnectedCycle",n}]["CrossingNumber"]

seq=Table[GraphData[{"CubeConnectedCycle",n},"CrossingNumber"],{n,3,8}]

Table[Interval[{((4^n)/20)-3(n+1)(2^(n-2)),((4^n)/6)+3(n^2)(2^(n-3))}],{n,3,8}]

N[%]

Do[Print[{n,CrossingNumber[CubeConnectedCycleGraph[n]]//AbsoluteTiming}],{n,3,8}]

Do[Print[{n,CrossingNumber[CubeConnectedCycleGraph[n],TimeConstraint->10]//AbsoluteTiming}],{n,4,8}]

Do[Print[{n,CrossingNumber[CubeConnectedCycleGraph[n],TimeConstraint->60]//AbsoluteTiming}],{n,4,8}]

Do[Print[{n,CrossingNumber[CubeConnectedCycleGraph[n],TimeConstraint->300]//AbsoluteTiming}],{n,4,8}]

Do[Print[{n,CrossingNumber[CubeConnectedCycleGraph[n],TimeConstraint->600]//AbsoluteTiming}],{n,4,8}]

Cycle

Entity["Graph",{"Cycle",n}]["CrossingNumber"]

seq=Table[GraphData[{"Cycle",n},"CrossingNumber"],{n,3,20}]

DiagonalIntersection

Dipyramid

Empty

Entity["Graph",{"Empty",n}]["CrossingNumber"]

seq=Table[GraphData[{"Empty",n},"CrossingNumber"],{n,30}]

FibonacciCube

seq=Table[GraphData[{"FibonacciCube",n},"CrossingNumber"],{n,15}]

Table[GraphData[{"FibonacciCube",n},"Planar"],{n,15}]

(seq=Table[CrossingNumber[GraphData[{"FibonacciCube",n}],MaxIterations->5],{n,8}])//AbsoluteTiming

(seq=Table[CrossingNumber[GraphData[{"FibonacciCube",n}],MaxIterations->10],{n,8}])//AbsoluteTiming

(seq=Table[CrossingNumber[GraphData[{"FibonacciCube",n}],MaxIterations->100],{n,8}])//AbsoluteTiming

FoldedCube

seq=Table[GraphData[{"FoldedCube",n},"CrossingNumber"],{n,2,10}]

Grid m×n

Entity["Graph",{"Grid",{m,n}}]["CrossingNumber"]

Table[GraphData[{"Grid",{m,n}},"CrossingNumber"],{n,10},{m,n}]//Column

Grid n×n

Entity["Graph",{"Grid",{n,n}}]["CrossingNumber"]

seq=Table[GraphData[{"Grid",{n,n}},"CrossingNumber"],{n,10}]

Grid k×m×n

Entity["Graph",{"Grid",{k,m,n}}]["CrossingNumber"]

seq=Table[GraphData[{"Grid",{n,n,n}},"CrossingNumber"],{n,10},{m,n},{k,m}]

Grid n×n×n

Entity["Graph",{"Grid",{n,n,n}}]["CrossingNumber"]

seq=Table[GraphData[{"Grid",{n,n,n}},"CrossingNumber"],{n,10}]

HalvedCube

seq=Table[GraphData[{"HalvedCube",n},"CrossingNumber"],{n,10}]

Hanoi

seq=Table[GraphData[{"Hanoi",n},"CrossingNumber"],{n,5}]

Hypercube

Entity["Graph",{"Hypercube",n}]["CrossingNumber"]

A307813 (conjectured sequence for which cr((Subscript[Q, 7])) < a(7))

This was formerly conjectured (by Erdos and Guy, 1973) to be the crossing number of the n-hypercube graph for n >= 3; cr(Q_n) = 0 for n = 0, 1, 2, 3:

Table[(5/32)(4^n)-Floor[(((n^2)+1)/2)](2^(n-2)),{n,3,10}]

seq=Table[(5/32)(4^n)-Floor[(((n^2)+1)/2)](2^(n-2)),{n,3,10}]

FullSimplify[FindSequenceFunction[seq,n-2],n∈Integers]

Table[(2^(n-5))(5 (2^n)-4(n^2)+2(((-1))^n)-2),{n,3,20}]

FindLinearRecurrence[seq]

LinearRecurrence[{8,-16,-16,80,-64},{0,8,56,352,1760},20]

(x^3)FindGeneratingFunction[seq,x]

SeriesCoefficient[-((8 (x^4) (-1+x-4 (x^2)+4 (x^3)))/((((-1+2 x))^3) (-1+2 x+8 (x^2)))),{x,0,n}]

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

Do[Print[{n,CrossingNumber[HypercubeGraph[n]]//AbsoluteTiming}],{n,0,8}]

Do[Print[{n,CrossingNumber[HypercubeGraph[n],TimeConstraint->10]//AbsoluteTiming}],{n,0,8}]

Do[Print[{n,CrossingNumber[HypercubeGraph[n],TimeConstraint->300]//AbsoluteTiming}],{n,4,6}]

For Q7:

New best found: 1943, at seed: 1
CR : 1943
New best found: 1937, at seed: 4
CR : 1937
New best found: 1894, at seed: 5
CR : 1894
New best found: 1812, at seed: 7
CR : 1812
New best found: 1806, at seed: 70
CR : 1806
New best found: 1804, at seed: 180
CR : 1804
New best found: 1794, at seed: 261
CR : 1794
New best found: 1788, at seed: 606
CR : 1788
New best found: 1784, at seed: 1768
CR : 1784
New best found: 1782, at seed: 1949
CR : 1782
New best found: 1780, at seed: 2541
CR : 1780
New best found: 1777, at seed: 10595
CR : 1777
New best found: 1776, at seed: 32973
CR : 1776
New best found: 1762, at seed: 37885
CR : 1762
Current best soln: 1762, at seed: 37885, current seed: 341000

Embeddings of Q_n with cr(Q_n) = a(n) are known for n = 5 and 6.  However, the Erdos-Guy conjecture is now refuted since cr(Q_7) <= 1744 < a(7) = 1760 (Clancy et al. 2019).

seq=Table[GraphData[{"Hypercube",n},"CrossingNumber"],{n,0,10}]

Bounds

https://arxiv.org/pdf/1901.05155.pdf

Table[(139/896)(4^n)-Floor[(((n^2)+1)/2)](2^(n-2))+(4/7)(2^(3Floor[(n/2)]-n)),{n,5,10}]

CrossingNumber[GraphData[{"Hypercube",10}],TimeConstraint->5 3600]

Keller

Entity["Graph",{"Keller",n}]["CrossingNumber"]

seq=Table[GraphData[{"Keller",n},"CrossingNumber"],{n,5}]

King m×n

Table[GraphData[{"King",{m,n}},"CrossingNumber"],{n,10},{m,n}]//Column

King n×n

seq=Table[GraphData[{"King",{n,n}},"CrossingNumber"],{n,20}]

Knight m×n

Entity["Graph",{"Knight",{m,n}}]["CrossingNumber"]

seq=Table[GraphData[{"Knight",{m,n}},"CrossingNumber"],{n,10},{m,n}]//Column

Knight n×n

Entity["Graph",{"Knight",{n,n}}]["CrossingNumber"]

seq=Table[GraphData[{"Knight",{n,n}},"CrossingNumber"],{n,10}]

Ladder

Entity["Graph",{"Ladder",n}]["CrossingNumber"]

seq=Table[GraphData[{"Ladder",n},"CrossingNumber"],{n,20}]

LadderRung

seq=Table[GraphData[{"LadderRung",n},"CrossingNumber"],{n,20}]

MengerSponge

seq=Table[GraphData[{"MengerSponge",n},"CrossingNumber"],{n,3}]

MoebiusLadder

Entity["Graph",{"MoebiusLadder",n}]["CrossingNumber"]

seq=Table[GraphData[{"MoebiusLadder",n},"CrossingNumber"],{n,3,25}]

Mycielski

Entity["Graph",{"Mycielski",n}]["CrossingNumber"]

seq=Table[GraphData[{"Mycielski",n},"CrossingNumber"],{n,11}]

Odd

Entity["Graph",{"Odd",n}]["CrossingNumber"]

seq=Table[GraphData[{"Odd",n},"CrossingNumber"],{n,7}]

Path

Entity["Graph",{"Path",n}]["CrossingNumber"]

seq=Table[GraphData[{"Path",n},"CrossingNumber"],{n,20}]

PathComplement

Same as Complete?

A000241, A028723

seq=Table[GraphData[{"PathComplement",n},"CrossingNumber"],{n,20}]

Do[Print[{n,CrossingNumber[GraphData[{"PathComplement",n}]]//Timing}],{n,10}]

Do[Print[{n,CrossingNumber[GraphData[{"PathComplement",n}],TimeConstraint->10]//AbsoluteTiming}],{n,8,20}]

seq={0,0,0,0,0,0,1,3,9,18,36,60};

Table[(1/4)Floor[n/2]Floor[(n-1)/2]Floor[(n-2)/2]*Floor[(n-3)/2],{n,0,20}]

Times@@@Table[Floor[(n-k)/2],{n,0,20},{k,0,3}]/4

Prism

Entity["Graph",{"Prism",n}]["CrossingNumber"]

seq=Table[GraphData[{"Prism",n},"CrossingNumber"],{n,3,25}]

Queen n×n

seq=Table[GraphData[{"Queen",{n,n}},"CrossingNumber"],{n,10}]

Rook n×n

seq=Table[GraphData[{"Rook",{n,n}},"CrossingNumber"],{n,10}]

RookComplement n×n

seq=Table[GraphData[{"RookComplement",{n,n}},"CrossingNumber"],{n,10}]

SierpinskiCarpet

seq=Table[GraphData[{"SierpinskiCarpet",n},"CrossingNumber"],{n,4}]

SierpinskiSieve

seq=Table[GraphData[{"SierpinskiSieve",n},"CrossingNumber"],{n,5}]

SierpinskiTetrahedron

seq=Table[GraphData[{"SierpinskiTetrahedron",n},"CrossingNumber"],{n,6}]

Star

Entity["Graph",{"Star",n}]["CrossingNumber"]

seq=Table[GraphData[{"Star",n},"CrossingNumber"],{n,25}]

Tetrahedral

seq=Table[GraphData[{"Tetrahedral",n},"CrossingNumber"],{n,6,10}]

TorusGrid m×n

Table[GraphData[{"TorusGrid",{m,n}},"CrossingNumber"],{n,3,10},{m,3,n}]//Column//TraditionalForm

TorusGrid n×n

seq=Table[GraphData[{"TorusGrid",{n,n}},"CrossingNumber"],{n,3,10}]

Triangular

seq=Table[GraphData[{"Triangular",n},"CrossingNumber"],{n,2,10}]

TriangularGrid

TriangularHoneycombQueen

seq=Table[GraphData[{"TriangularHoneycombQueen",n},"CrossingNumber"],{n,10}]

TriangularHoneycombRook

Computable using (Subscript[K, n])result

seq=Table[GraphData[{"TriangularHoneycombRook",n},"CrossingNumber"],{n,10}]

Transposition

Entity["Graph",{"Transposition",n}]["CrossingNumber"]

seq=Table[GraphData[{"Transposition",n},"CrossingNumber"],{n,6}]

Wheel

Entity["Graph",{"Wheel",n}]["CrossingNumber"]

seq=Table[GraphData[{"Wheel",n},"CrossingNumber"],{n,4,20}]

WhiteBishop n×n

seq=Table[GraphData[{"WhiteBishop",{n,n}},"CrossingNumber"],{n,2,10}]

QuickCross

SetDirectory["/Users/eww/src/quickcross/eww"]

CoxeterGraph [crash]

eww% ../QC -e 5 -g coxeter.g6 -q coxeter_coords.txt 
Segmentation fault

eww% ../QC -e 5 -g franklin.g6 -q franklin_coords.txt 
CR : 0

{"Queen", {2, 4}} [-e 3 never finds optimal embedding]

Export["queen-2-4.g6",StringReplace[ExportString[GraphData[{"Queen",{2,4}}],"Graph6"],">>graph6<<"->""],"String"]

StringReplace[ExportString[GraphData[{"Queen",{2,4}}],"Graph6"],{">>graph6<<"->"","\n"->""}]//InputForm

GraphData[{"Queen",{2,4}},{"V","M","CN"}]

GraphData[{"Queen",{2,4}},"Graph","All"]

CrossingNumber[GraphData[{"Queen",{2,4}}],RandomSeed->10]

CrossingNumber[GraphData[{"Queen",{2,4}}],MaxIterations->100]

eww% ./QC -r 1 -z 1000 -g "G~l|Y{"
...
Current best soln: 5, at seed: 3, current seed: 500000 
^C

eww% ./QC -e 1 -r 1 -z 10000 -g "G~l|Y{"
New best found: 4, at seed: 1
CR : 4
^C

eww% ./QC -e 2 -r 1 -z 10000 -g "G~l|Y{"
New best found: 5, at seed: 1
CR : 5
New best found: 4, at seed: 3
CR : 4

ExooIsmailescuGraph21Core

Export["exooismail.g6",StringReplace[ExportString[GraphData["ExooIsmailescuGraph21Core"],"Graph6"],">>graph6<<"->""],"String"]

GraphData["ExooIsmailescuGraph21Core",{"V","M"}]

GraphData["ExooIsmailescuGraph21Core","Graph","All"]

CrossingNumber[GraphData["ExooIsmailescuGraph21Core"],RandomSeed->10]

GraphData["ExooIsmailescuGraph21Core","Edges"]

MinimalCrossingGraph[GraphData["ExooIsmailescuGraph21Core"],RandomSeed->10]

GraphPlot[MinimalCrossingGraph[GraphData["ExooIsmailescuGraph21Core"],RandomSeed->10],VertexLabels->None]

FranklinGraph

Export["franklin.g6",StringReplace[ExportString[GraphData["FranklinGraph"],"Graph6"],">>graph6<<"->""],"String"]

eww% ../QC -e 5 -g franklin.g6 -q franklin_coords.txt 
CR : 0

but:

eww% ../QC -r 1 -z 1000 -g franklin.g6 
New best found: 3, at seed: 1
CR : 3
New best found: 2, at seed: 2
CR : 2

GraphData["FranklinGraph","Graph","MinimalRectilinearCrossing"]

Export["franklin_coords.txt",ExportString[GraphData["FranklinGraph","Embeddings","MinimalRectilinearCrossing"][[1]]/.n_?NumericQ:>NumberForm[N@n,{4,3}],"Table","FieldSeparators"->"  "],"String"]

GraphData["FranklinGraph","V"]

GraphPlot[g=MinimalCrossingGraph[GraphData["FranklinGraph"]]]

Checks

10 its, vertex count <=100, method 1

run 1

(bad={};
Monitor[If[(newcn=CrossingNumber[GraphData[g=#],"Cutoff"->110,Method->1,MaxIterations->100])<(cn=GraphData[#,"CN"]),AppendTo[bad,g->Min[cn,newcn]];Print[{#,cn,newcn}]]&/@SortBy[Select[GraphData["Nonplanar",;;100],IntegerQ[cn=GraphData[#,"CN"]]&&cn>1&],GraphData[#,"V"]&],g];bad)//Timing

rules=bad

10 its, vertex count <=100, method 2

run 1

(bad={};
Monitor[If[(newcn=CrossingNumber[GraphData[g=#],"Cutoff"->110,Method->2,MaxIterations->100])<(cn=GraphData[#,"CN"]),AppendTo[bad,g->Min[cn,newcn]];Print[{#,cn,newcn}]]&/@SortBy[Select[GraphData["Nonplanar",;;100],IntegerQ[cn=GraphData[#,"CN"]]&&cn>1&],GraphData[#,"V"]&],g];bad)//Timing

rules=bad

100 its, vertex count <=100, method 3

(bad={};
Monitor[If[(newcn=CrossingNumber[GraphData[g=#],"Cutoff"->110,MaxIterations->100])<(cn=GraphData[#,"CN"]),AppendTo[bad,g->Min[cn,newcn]];Print[{#,cn,newcn}]]&/@SortBy[Select[GraphData["Nonplanar",;;100],IntegerQ[cn=GraphData[#,"CN"]]&&cn>1&],GraphData[#,"V"]&],g];bad)//AbsoluteTiming

500 its, vertex count <=100, method 3

(g="";rules={};
Monitor[If[(newcn=CrossingNumber[GraphData[g=#],"Cutoff"->110,MaxIterations->500])<(cn=GraphData[#,"CN"]),AppendTo[rules,g->Min[cn,newcn]];Print[{#,cn,newcn}]]&/@SortBy[Select[GraphData["Nonplanar",;;100],IntegerQ[cn=GraphData[#,"CN"]]&&cn>1&],GraphData[#,"V"]&],g];rules)//AbsoluteTiming

Algorithms

StackExchange (doesn't work in V12.2)

https://mathematica.stackexchange.com/questions/223842/detect-if-any-edges-cross-in-a-graph-with-a-specified-layout

Graphics`Mesh`MeshInit[]

Clear[g]

EdgeIntersections[g_System`Graph]:=Complement[Graphics`Mesh`FindIntersections[Show@g],N@GraphEmbedding[g]]&;

symbols=Table[Unique[],8];
v=Flatten[MapAt[Reverse,Table[{a,s},{s,symbols},{a,{-3,3}}],{;;;;2}],1];
e=BlockMap[Apply@UndirectedEdge,v,2,1]~Drop~{Length@symbols};
curv=GraphElementData[{"CurvedArc","Curvature"->(#[[1]][[2]]-#[[2]][[2]])/#[[2]][[1]]}]&;
g[order_]:=With[{rules=Thread[symbols->order]},Graph[e,VertexCoordinates->Thread[v->(v/.rules)],EdgeShapeFunction->Thread[e->(curv/@e/.rules)]]]

g1=g[{8,3,2,1,5,4,6,7}]
g2=g[{8,6,5,1,7,3,2,4}]

EdgeIntersections[g1]

EdgeIntersections[g2]

Show[g2,Graphics[{Red,PointSize[Large],Point@EdgeIntersections[g2]}]]

Missing minimal rcn embedding

DateString[]

Missing

data={#[[1,1]],#[[All,-1]]}&/@SplitBy[Sort[Cases[{GraphData[#,"CN"],GraphData[#,"V"],#,FreeQ[GraphData[#,"EmbeddingClasses"],"MinimalCrossing"]}&/@GraphData[All],{g_,cn_,n_,True}:>{g,cn,n}]],First];

All up to rcn = 3

TextGrid[Take[data,3],Dividers->All]

Special up to rcn = 10

TextGrid[Take[data/.{"Cubic"|"Quartic"|"Quintic"|"Snark",_}->Nothing,10],Dividers->All]

Compute connected

{"Circulant", {9, {1, 2, 3}}}

GraphData[r={"Circulant",{9,{1,2,3}}},"Graph","All"]

GraphData[r,"EmbeddingClasses"]

GraphPlot[GraphData[r,"EdgeList"]]

rcn=GraphData[r,"RCN"]

I think actually RCN > CN

GraphPlot[g=MinimalCrossingGraph[GraphData[r],"CrossingNumber"->rcn,VertexLabels->None]]

v={#,2#2}&@@@{{-1/2,0},{3/2,0},{1/2,1},{1/2,1/2},{1/5,1/4},{2/5-1/10,1/4},{3/5,1/4},{3/5,1/2},{3/5+2/10,1/2},{(3/5),(3/8)},{(3/5)+(1/10),(3/8)},{(3/5)+(2/10),(3/8)}};
g=Graph[Range[Length[v]],UndirectedEdge@@@{{1,3},{2,3},{1,5},{4,5},{1,4},{3,5},{3,4},{5,6},{6,7},{2,6},{1,7},{4,8},{8,9},{8,10},{7,10},{6,10},{2,7},{2,10},{2,12},{2,9},{10,11},{11,12},{9,12},{3,12},{3,9},{4,10},{4,11},{8,11}},VertexCoordinates->v,VertexLabels->"Name"]

RecognizeGraph[g]

RectilinearCrossingCount[g]

{"King", {3, 6}}

GraphData[r={"King",{3,6}},"Graph","All"]

GraphData[r,"EmbeddingClasses"]

GraphPlot[GraphData[r,"EdgeList"]]

rcn=GraphData[r,"RCN"]

GraphPlot[g=MinimalCrossingGraph[GraphData[r],"CrossingNumber"->rcn,VertexLabels->None]]

v={#,2#2}&@@@{{-1/2,0},{3/2,0},{1/2,1},{1/2,1/2},{1/5,1/4},{2/5-1/10,1/4},{3/5,1/4},{3/5,1/2},{3/5+2/10,1/2},{(3/5),(3/8)},{(3/5)+(1/10),(3/8)},{(3/5)+(2/10),(3/8)}};
g=Graph[Range[Length[v]],UndirectedEdge@@@{{1,3},{2,3},{1,5},{4,5},{1,4},{3,5},{3,4},{5,6},{6,7},{2,6},{1,7},{4,8},{8,9},{8,10},{7,10},{6,10},{2,7},{2,10},{2,12},{2,9},{10,11},{11,12},{9,12},{3,12},{3,9},{4,10},{4,11},{8,11}},VertexCoordinates->v,VertexLabels->"Name"]

RecognizeGraph[g]

RectilinearCrossingCount[g]

{"QuasiQuintic", {9, 3}}

GraphData[r={"QuasiQuintic",{9,3}},"Graph","All"]

GraphData[r,"EmbeddingClasses"]

GraphPlot[GraphData[r,"EdgeList"]]

rcn=GraphData[r,"RCN"]

GraphPlot[g=MinimalCrossingGraph[GraphData[r],"CrossingNumber"->rcn,VertexLabels->None]]

v={#,2#2}&@@@{{-1/2,0},{3/2,0},{1/2,1},{1/2,1/2},{1/5,1/4},{2/5-1/10,1/4},{3/5,1/4},{3/5,1/2},{3/5+2/10,1/2},{(3/5),(3/8)},{(3/5)+(1/10),(3/8)},{(3/5)+(2/10),(3/8)}};
g=Graph[Range[Length[v]],UndirectedEdge@@@{{1,3},{2,3},{1,5},{4,5},{1,4},{3,5},{3,4},{5,6},{6,7},{2,6},{1,7},{4,8},{8,9},{8,10},{7,10},{6,10},{2,7},{2,10},{2,12},{2,9},{10,11},{11,12},{9,12},{3,12},{3,9},{4,10},{4,11},{8,11}},VertexCoordinates->v,VertexLabels->"Name"]

RecognizeGraph[g]

RectilinearCrossingCount[g]

{"QuasiQuintic", {9, 19}}

GraphData[r={"QuasiQuintic",{9,19}},"Graph","All"]

GraphData[r,"EmbeddingClasses"]

GraphPlot[GraphData[r,"EdgeList"]]

rcn=GraphData[r,"RCN"]

GraphPlot[g=MinimalCrossingGraph[GraphData[r],"CrossingNumber"->rcn,VertexLabels->None]]

v={#,2#2}&@@@{{-1/2,0},{3/2,0},{1/2,1},{1/2,1/2},{1/5,1/4},{2/5-1/10,1/4},{3/5,1/4},{3/5,1/2},{3/5+2/10,1/2},{(3/5),(3/8)},{(3/5)+(1/10),(3/8)},{(3/5)+(2/10),(3/8)}};
g=Graph[Range[Length[v]],UndirectedEdge@@@{{1,3},{2,3},{1,5},{4,5},{1,4},{3,5},{3,4},{5,6},{6,7},{2,6},{1,7},{4,8},{8,9},{8,10},{7,10},{6,10},{2,7},{2,10},{2,12},{2,9},{10,11},{11,12},{9,12},{3,12},{3,9},{4,10},{4,11},{8,11}},VertexCoordinates->v,VertexLabels->"Name"]

RecognizeGraph[g]

RectilinearCrossingCount[g]

{"RegularNonplanarDiameter", {3, 3, 16, 6}}

GraphData[{"RegularNonplanarDiameter",{3,3,16,6}},"Graph","All"]

CrossingNumber[GraphData[{"RegularNonplanarDiameter",{3,3,16,6}}],MaxIterations->100]

g=MinimalCrossingGraph[GraphData[{"RegularNonplanarDiameter",{3,3,16,6}}],"CrossingNumber"->2]

v=Join[CirclePoints[{1,π/2},6],{{-1,-1},{1,-1},{1,0},{1,1},{-1,1},{-1,0}}/2,CirclePoints[{1/4,π/2},4]]

g=Graph[Range[Length[v]],UndirectedEdge@@@Join[Partition[Range[6],2,1,1],Partition[Range[7,12],2,1,1],Partition[Range[13,16],2,1,1],{{12,14},{9,16},{1,13},{4,15},{2,11},{6,10},{3,7},{5,8}}],VertexCoordinates->v,VertexLabels->"Name"]

RecognizeGraph[g]

RectilinearCrossingCount[g]

{"RegularNonplanarDiameter", {4, 2, 12, 4}}

GraphData[gn={"RegularNonplanarDiameter",{4,2,12,4}},"Graph","All"]

cn=GraphData[gn,"CN"]

g=MinimalCrossingGraph[GraphData[gn],"CrossingNumber"->cn]

v=Join[CirclePoints[{1,π/2},6],{{-1,-1},{1,-1},{1,0},{1,1},{-1,1},{-1,0}}/2,CirclePoints[{1/4,π/2},4]]

g=Graph[Range[Length[v]],UndirectedEdge@@@Join[Partition[Range[6],2,1,1],Partition[Range[7,12],2,1,1],Partition[Range[13,16],2,1,1],{{12,14},{9,16},{1,13},{4,15},{2,11},{6,10},{3,7},{5,8}}],VertexCoordinates->v,VertexLabels->"Name"]

RecognizeGraph[g]

RectilinearCrossingCount[g]

{"WhiteBishop", {5, 5}}

GraphData[r,"EmbeddingClasses"]

GraphData[r={"WhiteBishop",{5,5}},"Graph","All"]

GraphPlot[GraphData[r,"EdgeList"]]

GraphPlot[g=MinimalCrossingGraph[GraphData[r],"CrossingNumber"->4,VertexLabels->None]]

Rotate[,π/2]

Mean[v[[{7,8}]]]

v={#,2#2}&@@@{{-1/2,0},{3/2,0},{1/2,1},{1/2,1/2},{1/5,1/4},{2/5-1/10,1/4},{3/5,1/4},{3/5,1/2},{3/5+2/10,1/2},{(3/5),(3/8)},{(3/5)+(1/10),(3/8)},{(3/5)+(2/10),(3/8)}};
g=Graph[Range[Length[v]],UndirectedEdge@@@{{1,3},{2,3},{1,5},{4,5},{1,4},{3,5},{3,4},{5,6},{6,7},{2,6},{1,7},{4,8},{8,9},{8,10},{7,10},{6,10},{2,7},{2,10},{2,12},{2,9},{10,11},{11,12},{9,12},{3,12},{3,9},{4,10},{4,11},{8,11}},VertexCoordinates->v,VertexLabels->"Name"]

RecognizeGraph[g]

RectilinearCrossingCount[g]

Compute disconnected

Sort[(GraphData[#1,{"RCN","V","#"}]&)/@Select[GraphData["Disconnected"],IntegerQ[GraphData[#1,"RCN"]]&&FreeQ[GraphData[#1,"EmbeddingClasses"],"MinimalRectilinearCrossing"]&]]

"2K3,3,3"

GraphData["2K3,3,3","Graph","All"]

GraphData["K3,3,3","RectilinearCrossingNumber"]

GraphData["K3,3,3","Graph","MinimalRectilinearCrossing"]

"2K5,5"

GraphData["2K5,5","Graph","All"]

GraphData["K5,5","Graph","MinimalRectilinearCrossing"]

GraphData["K5,5","RectilinearCrossingNumber"]

GraphData["K5,5","Graph","All"]

{"Bishop", {4, 8}}

GraphData[{"Bishop",{4,8}},"Graph","All"]

GraphData[{"Bishop",{4,8}},"ConnectedComponents","Name"]

GraphData[{"BlackBishop",{4,8}},"Graph","All"]

GraphData[{"BlackBishop",{4,8}}]

GraphData[{"BlackBishop",{4,8}},"Graph","MinimalCrossing"]

g=MyGraphUnion[GraphData[{"BlackBishop",{4,8}}],2]

RectilinearCrossingCount[g]

l2

l2={{{"Bishop",{4,8}},{0,{{"Degenerate","DegenerateEdgeEdge","DegenerateEdgeVertex","Grid","IntegerCoordinates"},{"MinimalCrossing","MinimalRectilinearCrossing","Primary"}}}}}

{"BracedSquare", {21, 2}}

GraphData[{"BracedSquare",{21,2}},"Graph","MinimalRectilinearCrossing"]

GraphData[{"BracedSquare",{21,2}},"Graph","All"]

GraphData[{"BracedSquare",{21,2}},"EmbeddingClasses"]

RectilinearCrossingCount/@GraphData[{"BracedSquare",{21,2}},"Graph","MinimalRectilinearCrossing"]

GraphData[{"BracedSquare",{21,2}},"RCN"]

l={{{"BracedSquare",{21,2}},{0,{{"BracedPolygon","Integral","MinimalIntegral","Primary","Rigid","UnitDistance"},{"MinimalCrossing","MinimalRectilinearCrossing"},{"Circular"}}}}}

PropertyReplace[l,"EmbeddingClasses","12.4"]

RenameGraphFiles[]

"GQ2,1"

GraphData["2GQ2,1","Graph","All"]

gs=GraphData["GQ2,1","Graph","All"][[{5,6}]]

gs=MyGraphUnion[#,2]&/@gs

{"Circulant", {20, {2, 4, 6}}}} [rcn = 18]

gns=GraphData[gn={"Circulant",{18,{2,4,6}}},"ConnectedComponents","Name"]

GraphData[gn,"Graph","All"]

GraphData[gn,"EmbeddingClasses"]

GraphData[gn,"RCN"]

GraphData[gns[[1]],"EmbeddingClasses"]

GraphData[gns[[1]],"Graph","MinimalRectilinearCrossing"]

{"Circulant", {20, {2, 8, 10}}}}

gns=GraphData[gn={"Circulant",{20,{2,8,10}}},"ConnectedComponents","Name"]

GraphData[gn,"Graph","All"]

GraphData[gn,"EmbeddingClasses"]

GraphData[gn,"RCN"]

K8+K1

GraphData["K8","EmbeddingClasses"]

GraphData["K8","Graph","MinimalRectilinearCrossing"]

?MyGraphUnion

MyGraphUnion[GraphData["K8","Graph","MinimalRectilinearCrossing"][[1]],Graph[{1},{}],"Layout"->Row]

g0=GraphData["K8","Graph",{"Labeled","MinimalRectilinearCrossing"}][[1]]

g=Graph[Range[9],EdgeList[g0],VertexCoordinates->Append[emb=GraphEmbedding[g0],emb[[1]]-{0,.1}]]

K9+K1

GraphData["K9","EmbeddingClasses"]

GraphData["K9","Graph","MinimalRectilinearCrossing"]

MyGraphUnion[GraphData["K9","Graph","MinimalRectilinearCrossing"][[1]],Graph[{1},{}],"Layout"->Row]

g0=GraphData["K9","Graph",{"Labeled","MinimalRectilinearCrossing"}][[1]]

g=Graph[Range[VertexCount[g0]+1],EdgeList[g0],VertexCoordinates->Append[emb=GraphEmbedding[g0],emb[[1]]-{0,.1}]]

K10+K1

GraphData["K10","EmbeddingClasses"]

GraphData["K10","Graph","MinimalRectilinearCrossing"]

Show[g0=GraphData["K10","Graph",{"Labeled","MinimalRectilinearCrossing"}][[1]],Axes->True]

g=Graph[Range[11],EdgeList[g0],VertexCoordinates->Append[emb=GraphEmbedding[g0],emb[[8]]-{0,55000}],VertexSize->{"Scaled",.02}]

{"TriangularHoneycombRook", 10}

gns=GraphData[gn={"TriangularHoneycombRook",10},"ConnectedComponents","Name"]

GraphData[gn,"Graph","All"]

GraphData[#,"Graph","MinimalCrossing"][[1]]&/@gns

GraphData[gn,"EmbeddingClasses"]

GraphData[gn,"RCN"]

"Two5Crowns"

GraphData["Two5Crowns","Graph","All"]

gns=GraphData[gn="Two5Crowns","ConnectedComponents","Name"]

GraphData[{"Crown",5}]

GraphData[gn,"Graph","All"]

gs=GraphData[gns[[1]],"Graph","All"]

g=MyGraphUnion[gs[[2]],2]

RectilinearCrossingCount[g]

l2

l2={{{"Bishop",{4,8}},{0,{{"Degenerate","DegenerateEdgeEdge","DegenerateEdgeVertex","Grid","IntegerCoordinates"},{"MinimalCrossing","MinimalRectilinearCrossing","Primary"}}}}}

Compute

Decrementally by VertexCount

Length[todo=Reverse@SortBy[
Select[
GraphData["Nonplanar"],MatchQ[GraphData[#,"CN"],_Integer?(GreaterThan[99])|_Missing]&
],
GraphData[#,{"CrossingNumber","V"}]&]
]

5 hours

dt=5 3600;  
Do[
gn=todo[[i]];
cn=GraphData[gn,"CN"];
Print[{i,gn,cn}];
newcn=CrossingNumber[GraphData[gn],TimeConstraint->dt,"Preprocess"->False];
If[newcn<cn||(MissingQ[cn]&&IntegerQ[newcn]),Print[{gn,cn,newcn}]],
{i,p,Length[todo]}
];

p=FirstPosition[todo,"PGammaU35OnNonisotropicPoints",{0}][[1]]+1

dt=5 3600;  
Do[
gn=todo[[i]];
cn=GraphData[gn,"CN"];
Print[{i,gn,cn}];
newcn=CrossingNumber[GraphData[gn],TimeConstraint->dt,"Preprocess"->False];
If[newcn<cn||(MissingQ[cn]&&IntegerQ[newcn]),Print[{gn,cn,newcn}]],
{i,p,Length[todo]}
];

Missing incrementally by VertexCount

Length[missing=Sort[{GraphData[#,"V"],#}&/@GraphData["CrossingNumber","Missing"]]]

5 hours

dt=5 3600;  
p=1;
Do[
gn=missing[[i,2]];
cn=GraphData[gn,"CN"];
Print[{i,gn,cn}];
newcn=CrossingNumber[GraphData[gn],TimeConstraint->dt,"Preprocess"->False];
If[newcn<cn||(MissingQ[cn]&&IntegerQ[newcn]),Print[{gn,cn,newcn}]],
{i,p,Length[missing]}
];

1 day

dt=86400;  
Do[
gn=missing[[i,2]];
cn=GraphData[gn,"CN"];
Print[{i,gn,cn}];
newcn=CrossingNumber[GraphData[gn],TimeConstraint->dt,"Preprocess"->False];
If[newcn<cn||(MissingQ[cn]&&IntegerQ[newcn]),Print[{gn,cn,newcn}]],
{i,p,Length[missing]}
];

p=FirstPosition[missing,"McLaughlinGraphSubconstituent2",{0}][[1]]+1

dt=86400;  
Do[
gn=missing[[i,2]];
cn=GraphData[gn,"CN"];
Print[{i,gn,cn}];
newcn=CrossingNumber[GraphData[gn],TimeConstraint->dt,"Preprocess"->False];
If[newcn<cn||(MissingQ[cn]&&IntegerQ[newcn]),Print[{gn,cn,newcn}]],
{i,p,Length[missing]}
];