x y z Embedding

Author

Eric W. Weisstein
December 11, 2020

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

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

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

Sources

http://11011110.livejournal.com/120326.html
http://11011110.livejournal.com/120899.html
http://11011110.livejournal.com/56492.html
http://arxiv.org/abs/0709.4087

2(n^2)

gs=Monitor[Table[{n,XYZGraph[n],RecognizeGraph[XYZGraph[n]]},{n,2,25}],n];//Timing;

TextGrid[gs,Dividers->All]

GraphicsGrid[{Show[#,PlotLabel->TextCell[GraphData[RecognizeGraph[ToCombinatoricaGraph[#]],"Name"]]]&/@Take[gs,4]},ImageSize->400,BaseStyle->Italic,Spacings->-70]

Search

Algorithm

BipartiteMatching[g]

c=ExtractCycles[g=Graph["PappusGraph"]]

Show[{GraphData["PappusGraph","LabeledImage"],Graphics[MapIndexed[{Thickness[.02],{Red,Blue}[[#2[[1]]]],Line[Partition[Vertices[g][[#1]],2,1,1]]}&,c]]}]

c=Most/@ExtractCycles[g=Graph["PappusGraph"]]

rules=Rule@@@Flatten[Function[f,MapIndexed[{#,#2[[1]]}&,f]]/@c,1]

Edges[g]/.rules

Most/@ExtractCycles[Graph["DyckGraph"]]

Cube

tup=Tuples[Range[2],3]

g=MakeGraph[tup,Count[Equal@@@Transpose[{#1,#2}],True]==2&,Type->Undirected]

GraphPlot3D[Rule@@@Edges[g],VertexCoordinateRules->MapIndexed[#2[[1]]->#&,tup],Boxed->False]

Hamming

tup=Tuples[Range[3],3]

g=MakeGraph[tup,Count[Equal@@@Transpose[{#1,#2}],True]==2&,Type->Undirected]

Degrees[g]

GraphPlot3D[Rule@@@Edges[g],VertexCoordinateRules->MapIndexed[#2[[1]]->#&,tup],Boxed->False]

ShowGraph[%]

RecognizeGraph[%159]

Select[Subsets[tup,{2}],Count[Equal@@@Transpose[#],True]==2&]