Local Crossing Number

Author

Eric W. Weisstein
July 2, 2024

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

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

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

Figure

GraphData[#,"CN"]&/@{"HeawoodGraph","K6"}

GraphicsRow[Show[StyleGraphs[GraphData[#,"Graph","MinimalLocalCrossing"][[1]]],PlotLabel->Style[GraphData[#,"Name"],Directive[FontFamily->"Times",Black,Italic,16]]]&/@{"HeawoodGraph","K6"},Alignment->Top]

LocalCrossingCount[GraphData[#,"Graph","MinimalLocalCrossing"][[1]]]&/@{"HeawoodGraph","K6"}

GraphDataCountTable

GraphDataCountTable["LocalCrossingNumber"]

By lcr

lcr == 1

SortBy[Select[GraphData["Connected"],GraphData[#,"LocalCrossingNumber"]==1&],GraphData[#,"V"]&]

small=SortBy[Select[GraphData["Connected",;;6],GraphData[#,"LocalCrossingNumber"]==1&],GraphData[#,"V"]&]

GraphData[#,"Graph","MinimalLocalCrossing"][[1]]&/@small

Parametrized families

<<MathWorld`Graphs`

Alkane

seq=Table[GraphData[{"Alkane",n},"LocalCrossingNumber"],{n,10}]

AlternatingGroupGraph

seq=Table[GraphData[{"AlternatingGroupGraph",n},"LocalCrossingNumber"],{n,2,6}]

Andrasfai

seq=Table[GraphData[{"Andrasfai",n},"LocalCrossingNumber"],{n,20}]

Table[GraphData[{"Andrasfai",n},"Graph","MinimalLocalCrossing"]/.(l_List/;Length[l]>0):>l[[1]],{n,20}]

Antelope n×n

seq=Table[GraphData[{"Antelope",{n,n}},"LocalCrossingNumber"],{n,20}]

Antiprism

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

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

Apollonian

seq=Table[GraphData[{"Apollonian",n},"LocalCrossingNumber"],{n,5}]

Barbell

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

BlackBishop n×n

seq=Table[GraphData[{"BlackBishop",{n,n}},"LocalCrossingNumber"],{n,20}]

Bishop n×n

seq=Table[GraphData[{"Bishop",{n,n}},"LocalCrossingNumber"],{n,20}]

Book

seq=Table[GraphData[{"Book",n},"LocalCrossingNumber"],{n,20}]

Bruhat

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

Camel n×n

seq=Table[GraphData[{"Camel",{n,n}},"LocalCrossingNumber"],{n,20}]

Centipede

seq=Table[GraphData[{"Centipede",n},"LocalCrossingNumber"],{n,10}]

CocktailParty

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

Table[GraphData[{"CocktailParty",n},"Graph","MinimalLocalCrossing"],{n,20}]

Complete

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

seq=Table[GraphData[{"Complete",n},"LocalCrossingNumber"],{n,30}]

Table[GraphData[{"Complete",n},"Graph","MinimalLocalCrossing"]/.(l_List/;Length[l]>0):>l[[1]],{n,20}]

CompleteBipartite n×n

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

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

Table[GraphData[{"CompleteBipartite",{n,n}},"Graph","MinimalLocalCrossing"]/.(l_List/;Length[l]>0):>l[[1]],{n,20}]

CompleteBipartite m×n

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

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"CompleteBipartite",{m,n}},"LocalCrossingNumber"],
XXX
},{n,10},{m,n}],1],{_,x_,x_}]

CompleteKPartite

Czap, Július; Hudák, Dávid (2012), "1-planarity of complete multipartite graphs", Discrete Applied Mathematics, 160 (4–5): 505–512, doi:10.1016/j.dam.2011.11.014, MR 2876333.

new=DeleteCases[
Cases[
{
#,
GraphData[#,"NotationRules","CompleteKPartite"],
GraphData[#,"LocalCrossingNumber"]}&/@Complement[GraphData["CompleteKPartite"],GraphData["Planar"]],
{
_,
Alternatives[
(* k=2 *) {1,_}|{2,_?(GreaterEqualThan[2])}|{3,_?(3≤#≤6&)}|{4,4},
(* k=3 *) {1,1,_}|{1,2,_?(2≤#≤6&)}|{2,2,_?(2≤#≤4&)}|{1,3,3},
(* k=4 *) {1,1,1,_?(#≤6&)}|{1,1,2,_?(2≤#≤3&)}|{1,2,2,2}|{2,2,2,2},
(* k=5 *) {1,1,1,1,_?(1≤#≤2)&}|{1,1,1,2,2},
(* k=6 *) {1,1,1,1,1}
],
_
}
],
{_,_,1}]

l={#,{0,1}}&@@@new

https://en.wikipedia.org/wiki/1-planar_graph#Complete_multipartite_graphs

K6

Length[gs=DeleteDuplicatesBy[
Select[Graph/@Subsets[EdgeList[CompleteGraph[6]]],ConnectedGraphQ[#]&&!PlanarGraphQ[#]&],
CanonicalGraph]]//Timing

rec=DeleteCases[RecognizeGraph[#,"Cache"->"InternalOnly"]&/@gs,{}]

new=DeleteCases[{#,GraphData[#,"LocalCrossingNumber"]}&/@rec,{_,1}]

l={#,{0,1}}&@@@new

K1,1,1,6

EdgeCount@CompleteGraph[{1,1,1,6}]

Length[gs=Select[
DeleteDuplicatesBy[Graph/@Subsets[EdgeList[CompleteGraph[{1,1,1,6}]]],CanonicalGraph],ConnectedGraphQ[#]&&!PlanarGraphQ[#]&]]//Timing

Length[gs1=Select[
DeleteDuplicatesBy[Graph/@Subsets[EdgeList[CompleteGraph[{1,1,1,6}]]],CanonicalGraph],!PlanarGraphQ[#]&&ConnectedGraphQ[#]&]]//Timing

Length[gs2=DeleteDuplicatesBy[
Select[Graph/@Subsets[EdgeList[CompleteGraph[{1,1,1,6}]]],ConnectedGraphQ[#]&&!PlanarGraphQ[#]&],
CanonicalGraph]]//Timing

gs===gs1===gs2

rec=DeleteCases[RecognizeGraph[#,"Cache"->"InternalOnly"]&/@gs,{}]

new=DeleteCases[{#,GraphData[#,"LocalCrossingNumber"]}&/@rec,{_,1}]

l={#,{0,1}}&@@@new

K1,1,2,3

EdgeCount@CompleteGraph[{1,1,2,3}]

Length[gs=DeleteDuplicatesBy[
Select[Graph/@Subsets[EdgeList[CompleteGraph[{1,1,2,3}]]],ConnectedGraphQ[#]&&!PlanarGraphQ[#]&],
CanonicalGraph]]//Timing

rec=DeleteCases[RecognizeGraph[#,"Cache"->"InternalOnly"]&/@gs,{}]

new=DeleteCases[{#,GraphData[#,"LocalCrossingNumber"]}&/@rec,{_,1}]

l={#,{0,1}}&@@@new

K2,2,2,2

EdgeCount@CompleteGraph[{2,2,2,2}]

Length[gs=DeleteDuplicatesBy[
Select[Graph/@Subsets[EdgeList[CompleteGraph[{2,2,2,2}]]],ConnectedGraphQ[#]&&!PlanarGraphQ[#]&],
CanonicalGraph]]//Timing

MaxMemoryUsed[]/10^9. GB

Tally[Head/@gs]

Export["~/graphs.m",gs]

Quit

$Version

Length[gs=Get["~/graphs.m"]]

(rec=DeleteCases[RecognizeGraph[#,"Cache"->"InternalOnly"]&/@gs,{}])//Timing

new=DeleteCases[{#,GraphData[#,"LocalCrossingNumber"]}&/@Union[rec],{_,1}]

l={#,{0,1}}&@@@new

K1,1,1,1,2,2

EdgeCount@CompleteGraph[{1,1,1,2,2}]

Length[gs=DeleteDuplicatesBy[
Select[Graph/@Subsets[EdgeList[CompleteGraph[{1,1,1,2,2}]]],ConnectedGraphQ[#]&&!PlanarGraphQ[#]&],
CanonicalGraph]]//Timing

rec=DeleteCases[RecognizeGraph[#,"Cache"->"InternalOnly"]&/@gs,{}]

new=DeleteCases[{#,GraphData[#,"LocalCrossingNumber"]}&/@rec,{_,1}]

l={#,{0,1}}&@@@new

CompleteTripartite n×n×n

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

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

CompleteTripartite k×m×n

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

DeleteCases[Flatten[Table[{
{k,m,n},
GraphData[{"CompleteTripartite",{k,m,n}},"LocalCrossingNumber"],
3Max[k,m,n]/2
},{n,10},{m,n},{k,m}],2],{_,x_,x_}]

CrossedPrism

seq=Table[GraphData[{"CrossedPrism",2n},"LocalCrossingNumber"],{n,2,12}]

Table[GraphData[{"CrossedPrism",n},"Graph","MinimalLocalCrossing"]/.(l_List/;Length[l]>0):>l[[1]],{n,4,25,2}]

Crown

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

CubeConnectedCycle

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

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

Cycle

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

seq=Table[GraphData[{"Cycle",n},"LocalCrossingNumber"],{n,3,30}]

CycleComplement

seq=Table[GraphData[{"CycleComplement",n},"LocalCrossingNumber"],{n,3,20}]

Table[GraphData[{"CycleComplement",n},"Graph","MinimalLocalCrossing"]/.(l_List/;Length[l]>0):>l[[1]],{n,3,20}]

DiagonalIntersection

seq=Table[GraphData[{"DiagonalIntersection",n},"LocalCrossingNumber"],{n,3,14}]

Dipyramid

seq=Table[GraphData[{"Dipyramid",n},"LocalCrossingNumber"],{n,3,20}]

DorogovtsevGoltsevMendes

seq=Table[GraphData[{"DorogovtsevGoltsevMendes",n},"LocalCrossingNumber"],{n,0,7}]

DoubleCone

seq=Table[GraphData[{"DoubleCone",n},"LocalCrossingNumber"],{n,3,20}]

Empty

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

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

FibonacciCube

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

Fiveleaper n×n

seq=Table[GraphData[{"Fiveleaper",{n,n}},"LocalCrossingNumber"],{n,20}]

Flower

seq=Table[GraphData[{"Flower",n},"LocalCrossingNumber"],{n,5,20}]

FoldedCube

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

Gear

seq=Table[GraphData[{"Gear",n},"LocalCrossingNumber"],{n,3,20}]

Giraffe n×n

seq=Table[GraphData[{"Giraffe",{n,n}},"LocalCrossingNumber"],{n,20}]

Goldberg

seq=Table[GraphData[{"Goldberg",n},"LocalCrossingNumber"],{n,3,20}]

Grid n×n

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

seq=Table[GraphData[{"Grid",{n,n}},"LocalCrossingNumber"],{n,20}]

Grid m×n

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

Sort@DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"Grid",{m,n}},"LocalCrossingNumber"],
0
},{n,10},{m,n}],1],{_,x_,x_}]

Grid n×n×n

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

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

Grid k×m×n

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

Sort@DeleteCases[Flatten[Table[{
{k,m,n},
GraphData[{"Grid",{k,m,n}},"LocalCrossingNumber"],
XXX
},{n,5},{m,n},{k,m}],2],{_,x_,x_}]

HalvedCube

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

Hanoi

seq=Table[GraphData[{"Hanoi",n},"LocalCrossingNumber"],{n,6}]

Helm

seq=Table[GraphData[{"Helm",n},"LocalCrossingNumber"],{n,3,20}]

Hypercube

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

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

Keller

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

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

King n×n

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

Table[GraphData[{"King",{n,n}},"Graph","MinimalLocalCrossing"]/.(l_List/;Length[l]>0):>l[[1]],{n,20}]

King m×n

Entity["Graph",{"King",{m,n}}]["LocalCrossingNumber"]

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"King",{m,n}},"LocalCrossingNumber"],
If[GraphData[{"King",{m,n}},"Planar"],0,1]
},{n,10},{m,n}],1],{_,x_,x_}]

Knight n×n

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

seq=Table[GraphData[{"Knight",{n,n}},"LocalCrossingNumber"],{n,20}]

Table[GraphData[{"Knight",{n,n}},"Graph","MinimalLocalCrossing"]/.(l_List/;Length[l]>0):>l[[1]],{n,20}]

Knight m×n

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

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"Knight",{m,n}},"LocalCrossingNumber"],
XXX
},{n,10},{m,n}],1],{_,x_,x_}]

Ladder

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

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

LadderRung

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

LucasCube

seq=Table[GraphData[{"LucasCube",n},"LocalCrossingNumber"],{n,15}]

MengerSponge

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

MoebiusLadder

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

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

Mycielski

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

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

Odd

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

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

Pan

seq=Table[GraphData[{"Pan",n},"LocalCrossingNumber"],{n,3,20}]

Path

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

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

PathComplement

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

Table[GraphData[{"PathComplement",n},"Graph","MinimalLocalCrossing"]/.(l_List/;Length[l]>0):>l[[1]],{n,20}]

Pell

seq=Table[GraphData[{"Pell",n},"LocalCrossingNumber"],{n,9}]

Prism

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

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

Queen n×n

seq=Table[GraphData[{"Queen",{n,n}},"LocalCrossingNumber"],{n,20}]

Rook n×n

seq=Table[GraphData[{"Rook",{n,n}},"LocalCrossingNumber"],{n,20}]

RookComplement n×n

seq=Table[GraphData[{"RookComplement",{n,n}},"LocalCrossingNumber"],{n,20}]

SierpinskiCarpet

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

SierpinskiGasket

seq=Table[GraphData[{"SierpinskiGasket",n},"LocalCrossingNumber"],{n,7}]

SierpinskiTetrahedron

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

Spoke n×n

seq=Table[GraphData[{"Spoke",{n,n}},"LocalCrossingNumber"],{n,5}]

StackedBook

seq=Table[GraphData[{"StackedBook",{n,n}},"LocalCrossingNumber"],{n,10}]

StackedPrism

seq=Table[GraphData[{"StackedPrism",{n,n}},"LocalCrossingNumber"],{n,3,5}]

Star

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

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

Sun

seq=Table[GraphData[{"Sun",n},"LocalCrossingNumber"],{n,3,20}]

Table[GraphData[{"Sun",n},"Graph","MinimalLocalCrossing"]/.(l_List/;Length[l]>0):>l[[1]],{n,3,20}]

Sunlet

seq=Table[GraphData[{"Sunlet",n},"LocalCrossingNumber"],{n,3,20}]

TorusGrid n×n

seq=Table[GraphData[{"TorusGrid",{n,n}},"LocalCrossingNumber"],{n,3,20}]

Table[GraphData[{"TorusGrid",{n,n}},"Graph","MinimalLocalCrossing"]/.(l_List/;Length[l]>0):>l[[1]],{n,3,20}]

Transposition

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

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

Table[GraphData[{"Transposition",n},"Graph","MinimalLocalCrossing"]/.(l_List/;Length[l]>0):>l[[1]],{n,6}]

Trapezohedron

Entity["Graph",{"Trapezohedron",n}]["LocalCrossingNumber"]

seq=Table[GraphData[{"Trapezohedron",n},"LocalCrossingNumber"],{n,3,20}]

Triangular

seq=Table[GraphData[{"Triangular",n},"LocalCrossingNumber"],{n,2,20}]

TriangularGrid

seq=Table[GraphData[{"TriangularGrid",n},"LocalCrossingNumber"],{n,0,20}]

TriangularHoneycombAcuteKnight

seq=Table[GraphData[{"TriangularHoneycombAcuteKnight",n},"LocalCrossingNumber"],{n,20}]

TriangularHoneycombBishop

seq=Table[GraphData[{"TriangularHoneycombBishop",n},"LocalCrossingNumber"],{n,20}]

TriangularHoneycombObtuseKnight

seq=Table[GraphData[{"TriangularHoneycombObtuseKnight",n},"LocalCrossingNumber"],{n,20}]

TriangularHoneycombQueen

seq=Table[GraphData[{"TriangularHoneycombQueen",n},"LocalCrossingNumber"],{n,20}]

TriangularHoneycombRook

seq=Table[GraphData[{"TriangularHoneycombRook",n},"LocalCrossingNumber"],{n,20}]

TriangularSnake

seq=Table[GraphData[{"TriangularSnake",n},"LocalCrossingNumber"],{n,1,20,2}]

Web

seq=Table[GraphData[{"Web",n},"LocalCrossingNumber"],{n,3,20}]

Wheel

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

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

WheelComplement

seq=Table[GraphData[{"WheelComplement",n},"LocalCrossingNumber"],{n,4,20}]

Table[GraphData[{"WheelComplement",n},"Graph","MinimalLocalCrossing"]/.(l_List/;Length[l]>0):>l[[1]],{n,4,20}]

WhiteBishop n×n

seq=Table[GraphData[{"WhiteBishop",{n,n}},"LocalCrossingNumber"],{n,2,20}]

Zebra n×n

seq=Table[GraphData[{"Zebra",{n,n}},"LocalCrossingNumber"],{n,20}]

Inequality from Brooks' theorem

https://en.wikipedia.org/wiki/1-planar_graph#Generalizations_and_related_concepts

Cases[
GraphData[#,{"#","Thickness","LocalCrossingNumber"}]&/@GraphData[All],
{_,n1_Integer,n2_Integer}/;n1>n2+1
]

Missing

TextGrid[DeleteCases[
Table[{n,Select[GraphData["Connected",n],MissingQ[GraphData[#,"LocalCrossingNumber"]]&]},{n,8}],
{_,{}}
],Dividers->All]

Search

lcr == 1 but no MinimalLocalCrossing embedding

Select[GraphData[All],GraphData[#,"LocalCrossingNumber"]===1&&FreeQ[GraphData[#,"EmbeddingClasses"],"MinimalLocalCrossing"]&]

Find new lcr == 1 from subgraphs

NonplanarSubgraphStep[g_Graph]:=Module[{m=EdgeCount[g]},
DeleteDuplicates[CanonicalGraph/@Select[Graph/@Subsets[EdgeList[g],{10,m-1}],(!PlanarGraphQ[#])&]]
]

LocalCrossingNumber1Graphs[g_Graph,n_:Infinity,opts___?OptionQ]:=Rest[FixedPoint[Union[Flatten[{#,NonplanarSubgraphStep/@#}]]&,{CanonicalGraph[g]},n]]

<18 edges

small=Select[
GraphData[{"Nonplanar","Connected"}],
GraphData[#,"M"]<18&&GraphData[#,"LocalCrossingNumber"]===1&
]

Length[gs=DeleteDuplicates@Flatten[Monitor[LocalCrossingNumber1Graphs[GraphData[gn=#]]&/@small,gn]]]//Timing

new=DeleteCases[RecognizeGraph[#,"Cache"->"InternalOnly"]&/@gs,{}]

DeleteCases[{#,GraphData[#,"LocalCrossingNumber"]}&/@new,{_,1}]

<20 edges

small=Select[
GraphData[{"Nonplanar","Connected"}],
GraphData[#,"M"]<20&&GraphData[#,"LocalCrossingNumber"]===1&
]

Length[gs=DeleteDuplicates@Flatten[Monitor[LocalCrossingNumber1Graphs[GraphData[gn=#]]&/@small,gn]]]//Timing

new=DeleteCases[RecognizeGraph[#,"Cache"->"InternalOnly"]&/@gs,{}]

DeleteCases[{#,GraphData[#,"LocalCrossingNumber"]}&/@new,{_,1}]

<22 edges

small=SortBy[Select[
GraphData[{"Nonplanar","Connected"}],
GraphData[#,"M"]<22&&GraphData[#,"LocalCrossingNumber"]===1&
],GraphData[#,"M"]&]

Length[small]

gs={};
Monitor[
Do[
gs=Union[gs,LocalCrossingNumber1Graphs[GraphData[gn=small[[i]]]]],
{i,Length[small]}
],
Row[{"indx: ",i,", cnt: ",Length[gs],", graph: ",gn}]];//Timing

Length[gs]

MaxMemoryUsed[]/10^9.GB

new=DeleteCases[RecognizeGraph[#,"Cache"->"InternalOnly"]&/@gs,{}]

DeleteCases[{#,GraphData[#,"LocalCrossingNumber"]}&/@new,{_,1}]

Small cn graphs that have missing lcr

TextGrid[Take[Prepend[Sort[{#,#3,#/#3//N,#2,#5}&@@@Cases[GraphData[#,{"CrossingNumber","V","M","LocalCrossingNumber","#"}]&/@GraphData["Nonplanar"],{_Integer,_,_,_Missing,_}]],
Thread[Style[{"CN","M","CN/M","V","graph"},Bold]]],50],Dividers->All,Alignment->{{{Decimal},Left}}]

Disconnected

Select[DeleteCases[{#,#2,cn=GraphData[#,"LocalCrossingNumber"]&/@#2,Max[cn],GraphData[#,"LocalCrossingNumber"]}&@@@Select[{#,GraphData[#,"ConnectedComponents","Name"]}&/@GraphData["Disconnected"],AllTrue[#[[2]],DataPaclets`GraphDataDump`MyGraphQ]&],{_,_,_,x_,x_}],FreeQ[#[[-2]],Missing]&]