House Graph

Author

Eric W. Weisstein
April 10, 2024

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

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

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

Embeddings

<<MathWorld`Graphs`

"HouseGraph"

Names

GraphData["HouseGraph","StandardName"]

GraphData["HouseGraph","StandardNames"]

Primary

GraphData["HouseGraph"]//StyleGraphs[#,ImageSize->Small]&

All

GraphData["HouseGraph","Graph","All"]//StyleGraphs

Inexact

Select[GraphData["HouseGraph","Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData["HouseGraph","EdgeList"]]

Default embedding

g=Graph[GraphData["HouseGraph","Edges"],GraphLayout->"LayeredEmbedding"]

DegenerateGraphEmbeddingTypes@g

RotateGraph[,-Pi/4]

v={{0,0},{1,0},{2,0},{1,1},{2,1}};
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,2,3,5,4,1],{2,4}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

Degenerate

GraphData["HouseGraph","Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData["HouseGraph","Graph","Degenerate"]

Configuration

GraphData["HouseGraph","Configuration"]

GraphData["HouseGraph","Graph","Configuration"]//StyleGraphs

Perspective

GraphData["HouseGraph","Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData["HouseGraph","Polyhedron"]

HoneycombToroidal construction

GraphData["HouseGraph","NotationRules","HoneycombToroidal"]

GeneralizedPetersen

GraphData["HouseGraph","Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData["HouseGraph","Graph","IGraph"]//StyleGraphs

Bilateral

GraphData["HouseGraph","Graph","Bilateral"]//StyleGraphs

Circular

GraphData["HouseGraph","Graph","Circular"]//StyleGraphs

Circular construction

GraphData["HouseGraph","Hamiltonian"]

GraphData["HouseGraph","HamiltonianCycleCount"]

Length[hc=FindHamiltonianCycle[GraphData["HouseGraph"],All][[All,All,1]]]

circ=CircularEmbeddingFromHamiltonianCycle[GraphData["HouseGraph"],#]&/@hc

Length[bilat=DeleteDuplicatesBy[
DeleteMissing[BilaterallyRotatedGraph/@circ],
CircularCanonicalGraphEmbedding]]//Timing//Quiet

gs=bilat

Length[quad=DeleteDuplicatesBy[Union@Select[bilat,BilateralGraphEmbeddingQ[#,Axis->"X"]&],CircularCanonicalGraphEmbedding[#,4]&]]

Planar

GraphData["HouseGraph","Planar"]

GraphData["HouseGraph","Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData["HouseGraph",{"RCN","CN"}]

GraphData["HouseGraph","Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData["HouseGraph"],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData["HouseGraph"],TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData["HouseGraph"],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData["HouseGraph"],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData["HouseGraph"],TimeConstraint->5 3600])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData["HouseGraph"],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

IGLayoutTutte[g,"OuterFace"->#]&/@faces

Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData["HouseGraph"],"CrossingNumber"->cn,RandomSeed->n]],{n,50}],Max[OuterFace[#]]<=GraphData["HouseGraph","V"]&]]//Timing

Table[MinimalCrossingGraph[GraphData["HouseGraph"],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union//Timing

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData["HouseGraph","Circulant"]

GraphData["HouseGraph","Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData["HouseGraph","NotationRules","Circulant"]

(ci=CirculantIndices[GraphData["HouseGraph"]])//Timing

CirculantGraph1@@@ci

Cases[GraphData["HouseGraph","StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData["HouseGraph","ComplementGraph","Name"]

GraphData[compl,"Graph","All"]

gs=GraphComplement/@%

Line graph

GraphData["HouseGraph","Line"]

LineGraphQ[GraphData["HouseGraph"]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== "HouseGraph"&]

RootGraph[GraphData["HouseGraph"]]

RecognizeGraph[%]

GraphData[roots[[1]],"Graph","All"]

gs=LineGraph/@%

Halin

GraphData["HouseGraph","Halin"]

GraphData["HouseGraph","Graph","Halin"]//StyleGraphs

Rigid

GraphData["HouseGraph","Rigid"]

GraphData["HouseGraph","Graph","Rigid"]//StyleGraphs

Flexible

GraphData["HouseGraph","Flexible"]

GraphData["HouseGraph","Graph","Flexible"]//StyleGraphs

LCF

GraphData["HouseGraph","LCF"]

GraphData["HouseGraph","HamiltonianCycleCount"]

GraphData["HouseGraph","LCFSignature"]

GraphData["HouseGraph","LCFNotations"]

GraphData["HouseGraph","Graph","LCF"]//StyleGraphs

Tally[LCFNotation[#][[2]]&/@%]

UnitDistance

GraphData["HouseGraph","UnitDistance"]

UnitDistanceGraphQ[GraphData["HouseGraph"],Debug->True]//Timing

GraphData["HouseGraph","Graph","UnitDistance"]//StyleGraphs

Select[%,!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&]

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData["HouseGraph","VertexList"],GraphData["HouseGraph","EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

UnitDistanceEmbeddingRefine[Annotate[#,VertexCoordinates->N[GraphEmbedding[#]]],MaxIterations->500]&/@Complement@@(GraphData["HouseGraph","Graph",#]&/@{"All","UnitDistance"})

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData["HouseGraph"],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData["HouseGraph"],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

{"HouseGraph",l=FindSubgraphUnitDistanceEmbedding[GraphData["HouseGraph"],TimeConstraint->300,"Results"->All]//Timing}

gs=SortBy[UniqueEmbeddings[l],Replace[RectilinearCrossingCount[#],Infinity->0]&]

UnitDistance construction

v={{0,0},{1,0},{1,1},{0,1},{1/2,Sqrt[3]/2}};
g=Graph[Range@Length@v,UnitEdges[v],VertexCoordinates->v,VertexLabels->Automatic]

RotateGraph[,-30Degree]

v={{0,0},{1,0},{1/2,Sqrt[3]/2},{-1,0},{-1/2,Sqrt[3]/2}};
g=Graph[Range@Length@v,DeleteCases[UnitEdges[v],1\[UndirectedEdge]5],VertexCoordinates->v,VertexLabels->Automatic]

gs=UnlabelGraph/@{,,}

gs={,,};

RecognizeGraph/@gs

Matchstick

GraphData["HouseGraph","Matchstick"]

GraphData["HouseGraph","Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData["HouseGraph","Edges"]]

3D All

GraphData["HouseGraph","Graph",{"3D","All"}]

3D UnitDistance

GraphData["HouseGraph","Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData["HouseGraph","Polyhedral"]

GraphData["HouseGraph","Graph",{"3D","Polyhedron"}]

3D Canonical

GraphData["HouseGraph","Graph",{"3D","Canonical"}]

"HouseXGraph"

Names

GraphData["HouseXGraph","StandardName"]

GraphData["HouseXGraph","StandardNames"]

Primary

GraphData["HouseXGraph"]//StyleGraphs[#,ImageSize->Small]&

All

GraphData["HouseXGraph","Graph","All"]//StyleGraphs

Inexact

Select[GraphData["HouseXGraph","Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData["HouseXGraph","EdgeList"]]

Default embedding

GraphPlot@GraphData["HouseXGraph","Edges"]

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

Degenerate

GraphData["HouseXGraph","Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData["HouseXGraph","Graph","Degenerate"]

Configuration

GraphData["HouseXGraph","Configuration"]

GraphData["HouseXGraph","Graph","Configuration"]//StyleGraphs

Perspective

GraphData["HouseXGraph","Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData["HouseXGraph","Polyhedron"]

HoneycombToroidal construction

GraphData["HouseXGraph","NotationRules","HoneycombToroidal"]

GeneralizedPetersen

GraphData["HouseXGraph","Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData["HouseXGraph","Graph","IGraph"]//StyleGraphs

Bilateral

GraphData["HouseXGraph","Graph","Bilateral"]//StyleGraphs

Circular

GraphData["HouseXGraph","Graph","Circular"]//StyleGraphs

Circular construction

GraphData["HouseXGraph","Hamiltonian"]

GraphData["HouseXGraph","HamiltonianCycleCount"]

Length[hc=FindHamiltonianCycle[GraphData["HouseXGraph"],All][[All,All,1]]]

circ=CircularEmbeddingFromHamiltonianCycle[GraphData["HouseXGraph"],#]&/@hc

Length[bilat=DeleteDuplicatesBy[
DeleteMissing[BilaterallyRotatedGraph/@circ],
CircularCanonicalGraphEmbedding]]//Timing//Quiet

gs=bilat

Length[quad=DeleteDuplicatesBy[Union@Select[bilat,BilateralGraphEmbeddingQ[#,Axis->"X"]&],CircularCanonicalGraphEmbedding[#,4]&]]

Planar

GraphData["HouseXGraph","Planar"]

GraphData["HouseXGraph","Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData["HouseXGraph",{"RCN","CN"}]

GraphData["HouseXGraph","Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData["HouseXGraph"],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData["HouseXGraph"],TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData["HouseXGraph"],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData["HouseXGraph"],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData["HouseXGraph"],TimeConstraint->5 3600])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData["HouseXGraph"],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

IGLayoutTutte[g,"OuterFace"->#]&/@faces

Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData["HouseXGraph"],"CrossingNumber"->cn,RandomSeed->n]],{n,50}],Max[OuterFace[#]]<=GraphData["HouseXGraph","V"]&]]//Timing

Table[MinimalCrossingGraph[GraphData["HouseXGraph"],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union//Timing

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData["HouseXGraph","Circulant"]

GraphData["HouseXGraph","Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData["HouseXGraph","NotationRules","Circulant"]

(ci=CirculantIndices[GraphData["HouseXGraph"]])//Timing

CirculantGraph1@@@ci

Cases[GraphData["HouseXGraph","StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData["HouseXGraph","ComplementGraph","Name"]

GraphData[compl,"Graph","All"]

gs=GraphComplement/@%

Line graph

GraphData["HouseXGraph","Line"]

LineGraphQ[GraphData["HouseXGraph"]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== "HouseXGraph"&]

RootGraph[GraphData["HouseXGraph"]]

RecognizeGraph[%]

GraphData[roots[[1]],"Graph","All"]

gs=LineGraph/@%

DegenerateGraphEmbeddingTypes/@%

v={{-1,0},{1,0},{0,Sqrt[3]}};
v=Join[v,Mean[v[[{3,#}]]]&/@{1,2}];
g=Graph[Range@Length@v,UndirectedEdge@@@{e[1,2,5,3,4,1,5,4,2]},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph@g

Halin

GraphData["HouseXGraph","Halin"]

GraphData["HouseXGraph","Graph","Halin"]//StyleGraphs

Rigid

GraphData["HouseXGraph","Rigid"]

GraphData["HouseXGraph","Graph","Rigid"]//StyleGraphs

Flexible

GraphData["HouseXGraph","Flexible"]

GraphData["HouseXGraph","Graph","Flexible"]//StyleGraphs

LCF

GraphData["HouseXGraph","LCF"]

GraphData["HouseXGraph","HamiltonianCycleCount"]

GraphData["HouseXGraph","LCFSignature"]

GraphData["HouseXGraph","LCFNotations"]

GraphData["HouseXGraph","Graph","LCF"]//StyleGraphs

Tally[LCFNotation[#][[2]]&/@%]

UnitDistance

GraphData["HouseXGraph","UnitDistance"]

UnitDistanceGraphQ[GraphData["HouseXGraph"],Debug->True]//Timing

GraphData["HouseXGraph","Graph","UnitDistance"]//StyleGraphs

Select[%,!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&]

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData["HouseXGraph","VertexList"],GraphData["HouseXGraph","EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

UnitDistanceEmbeddingRefine[Annotate[#,VertexCoordinates->N[GraphEmbedding[#]]],MaxIterations->500]&/@Complement@@(GraphData["HouseXGraph","Graph",#]&/@{"All","UnitDistance"})

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData["HouseXGraph"],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData["HouseXGraph"],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData["HouseXGraph","Matchstick"]

GraphData["HouseXGraph","Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData["HouseXGraph","Edges"]]

3D All

GraphData["HouseXGraph","Graph",{"3D","All"}]

3D UnitDistance

GraphData["HouseXGraph","Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData["HouseXGraph","Polyhedral"]

GraphData["HouseXGraph","Graph",{"3D","Polyhedron"}]

GraphData["HouseXGraph","Graph",{"3D","Canonical"}]

GraphData

GraphDataClassString

GraphDataClassString[{"HouseGraph","HouseXGraph"}]