Progress in Graphs & Networks

Jaebum Jung, Wolfram Research

(RowDefault[, (Spacer1), , (Spacer1), ])  #WolframTechConf

ABSTRACT

New Graphs and Networks features in Version 13 include subgraph isomorphisms, graph colorings, planar graphs and control flow graphs.  The performance of graph isomorphism functionality has significantly improved.

New Functions

Subgraph Isomorphisms

IsomorphicSubgraphQ

FindSubgraphIsomorphism

FindIsomorphicSubgraph

Graph Coloring

FindVertexColoring

FindEdgeColoring

VertexChromaticNumber

EdgeChromaticNumber

Planar Graphs

PlanarFaceList

DualPlanarGraph

FindPlanarColoring

Control-flow Graphs

DominatorVertexList

DominatorTreeGraph

Subgraph Isomorphisms

Subgraph Isomorphisms

Map :  \[LeftAssociation]”a”->1,”b”->3,”c”->5,”d”->7\[RightAssociation]

Subgraph Isomorphisms

IsomorphicSubgraphQ

test whether a graph is a subgraph after vertex renaming

h=;g=;

IsomorphicSubgraphQ[h, g]

Subgraph Isomorphisms

FindSubgraphIsomorphism

find the subgraph isomorphism

h=;g=;

FindSubgraphIsomorphism[h, g]

Subgraph Isomorphisms

FindIsomorphicSubgraph

find the isomorphic subgraph

h=;g=;

FindIsomorphicSubgraph[h, g]

Graph Coloring

FindVertexColoring

finds a coloring with minimal size for the vertices in the graph

Graph Coloring

FindVertexColoring

g=;

FindVertexColoring[g]

FindVertexColoring[g,ColorData[106,"ColorList"]]

Graph[g,{VertexStyle->Thread[VertexList[g]->%]}]

Graph Coloring

FindEdgeColoring

find an edge coloring for a graph

Graph Coloring

FindEdgeColoring

g=;

FindEdgeColoring[g]

FindEdgeColoring[g,ColorData[106,"ColorList"]]

Graph[g,{EdgeStyle->Thread[EdgeList[g]->%]}]

Graph Coloring

VertexChromaticNumber

gives the chromatic number for the vertices of the graph g.

g=PetersenGraph[]

VertexChromaticNumber[g]

Graph Coloring

EdgeChromaticNumber

gives the chromatic number for the edges of the graph g.

g=PetersenGraph[]

EdgeChromaticNumber[g]

Planar Graphs

PlanarFaceList

gives the list of faces of the planar graph g.

({{, , }})

Planar Graphs

PlanarFaceList

g=WheelGraph[4, PlotTheme->"NameLabeled"]

PlanarFaceList[g]

Planar Graphs

PlanarFaceList

PlanarFaceList[g]

Planar Graphs

DualPlanarGraph

gives the dual of the planar graph g.

Planar Graphs

DualPlanarGraph

g=;

DualPlanarGraph[g]

Planar Graphs

FindPlanarColoring

finds a coloring with minimal size for the faces of the planar graph g.

({{, , }})

Planar Graphs

FindPlanarColoring

g=;

FindPlanarColoring[g,ColorData[106,"ColorList"]]

Graphics[GraphicsComplex[GraphEmbedding[g],Reverse@Thread[{%, Polygon/@PlanarFaceList[g]}]]]

Control-flow Graphs

DominatorVertexList

gives the list of immediate dominators of the directed graph g from the root vertex v.

g=;

DominatorVertexList[g,1]

Control-flow Graphs

DominatorVertexList

DominatorVertexList[g,1]

Control-flow Graphs

DominatorTreeGraph

gives the dominator tree of the directed graph g from the root vertex v.

g=;

DominatorTreeGraph[g, 1, VertexLabels->Automatic]

Control-flow Graphs

DominatorTreeGraph

DominatorTreeGraph[g, 1, VertexLabels->Automatic]

Updated Functions

Graph Isomorphisms

CanonicalGraph

IsomorphicGraphQ

GraphAutomorphismGroup

FindGraphIsomorphism

Graph Extensions

Graph

GraphPlot, GraphDistance, FindShortestPath, ...

CreateDataStructure

BinaryTree, AVLTree, KDTree, CSGTree, …

Graph Isomorphisms

CanonicalGraph

Graph Isomorphisms

IsomorphicGraphQ

Graph Isomorphisms

GraphAutomorphismGroup

Graph Isomorphisms

FindGraphIsomorphism

Graph Extensions

Graph

construct graph objects from Molecule and Tree expressions, BinaryTree, AVLTree, KDTree, CSGTree.

GraphPlot, GraphDistance, FindShortestPath, ...

work on Tree expressions

CreateDataStructure

construct BinaryTree, AVLTree, KDTree, CSGTree from graph objects.

BinaryTree, AVLTree, KDTree, CSGTree, …

generate Graph object with a new operation “Graph” .

What’s New in Geometry      
Thursday 9:00 AM CDT

Physically Based Rendering in 3D Graphics      
Friday 11:00 AM CDT

Constructive Solid Geometry
Friday 12:00 AM CDT

Office Hour: Geometry
Friday 1:00 PM CDT

Office Hour: Graphs & Networks
Friday 2:00 PM CDT

(RowDefault[, (Spacer1), , (Spacer1), ])  #WolframTechConf