A substantial effort was put into Graph Theory for Maple 2020, including significant advances in visualization, flexible graph manipulation options, powerful analysis tools, and support for over 20 new special graphs and graph properties.
Centrality
Maple 2020 offers eight new functions for calculating the centrality of vertices in a graph. These are:








Here is an example of a simple social graph where the graph centrality measures social influence.
> 
> 
> 
> 
> 
> 
> 
Graph Styling Improvements
The stylesheet option to DrawGraph is now fully supported for animations and all options except the ones controlling the shapes of vertices and arrows are supported for threedimensional graphs.
> 
> 
The animate option to DrawGraph can now be set to a positive integer to control the number of frames generated.
> 
> 
A few new ways to style graphs were also added. A new arrowshape style was added for directed edges allowing any shape supported by plottools. As well, the arrowpos directive has been greatly improved to be more accurate. Vertex borders can now be given a color including several special dynamic coloring options "_contrast", "_blend", and "_match" which are also supported for vertex font colors, edge color, and edge font colors.
New commands have been introduced for adding styles to graph components that are independent of the concept of "highlighting". These are StyleVertex, StyleEdge, and StyleSubgraph and have basically the same calling sequences as their Highlight equivalents. They differ from their Highlight versions in that when called multiple times, they add to the existing style rather than replace it and they build on the base default style rather than the base "highlighted" style.
> 
> 
> 
> 
Style Vertices and Edges by Properties
You can now visually style graph vertices and edges with respect to properties, such as centrality or weight. For example, given its centrality, the color of a vertex can be chosen from a gradient of colorsthis lets you emphasize the more important vertices in a graph. Similarly, those edges with greater weight can be assigned greater thickness.
In this example, given the
> 
> 
In this example, we demonstrate the valuesplit styling option that styles with a discrete set of values rather than a gradient or range:
> 

> 
Graph Layout Methods
Maple 2020 offers a number of new ways to layout plots of graphs. The style option from previous version has been renamed layout to better clarify the difference between stylesheets and the layout of the vertices. (The old option name style will continue to be supported as an alias for layout however). A new option layoutoptions has been added to pass in options to layout methods to further customize them.
> 
> 
There is a new interactive method to layout graphs manually starting from a selected layout. A plot component is created where vertices can either be dragged or selected and moved to new positions. The new position will be stored as the 'user' layout, and will be the default layout for future calls to DrawGraph.
> 
> 
> 
There are a few new layout methods, most notably, a new spectral two and threedimensional layout method.
> 
> 
> 
The grid and random layout methods are also new in Maple 2020 and support two and three dimensions.
SelfLoops
The core routines of the GraphTheory package have been extended to support graphs with selfloops. Graphs with selfloops may be directed or undirected, and weighted or unweighted.
The number of selfloops in a graph is displayed in the graph description along with the vertex and edge count:
> 
Several new commands have been added to work with selfloops:
The HasSelfLoop and NumberOfSelfLoops commands permit querying graphs for the existence and number of selfloops, respectively, while SelfLoops returns the set of vertices with selfloops.
> 
> 
> 
Directed Graphs with SelfLoops
The support for selfloops extends to both directed and undirected graphs. Here is a directed graph with a selfloop at vertex 1:
> 
> 
> 
The Edges command now returns selfloops in its list of edges. If only edges between distinct vertices are desired, the option selfloops=false can be specified:
> 
> 
The indegree and outdegree of a vertex are each increased by one when it receives a selfloop:
> 
> 
Undirected Graphs with SelfLoops
We can produce a copy of G1 which discards the directionality of its edges while preserving selfloops by calling UnderlyingGraph with the selfloops option:
> 
> 
By convention, the degree of a vertex is increased by 2 when it receives a selfloop:
> 
In a simple graph the smallest possible girth (length of the shortest cycle) is 3. In a graph with a selfloop, the length of the shortest cycle is 1:
> 
By definition, any graph with a selfloop cannot be colored with any number of colors. The chromatic polynomial therefore is identically zero:
> 
Removing selfloops
We can generate a copy of a graph with the selfloops removed simply by calling UnderlyingGraph without specifying the selfloops option:
> 
> 
> 
> 
> 
Geometric Graphs
A new Maple 2020 function in RandomGraphs subpackage generates a random geometric graph.
> 
> 
Maple 2020 contains a new subpackage, GeometricGraphs, for generating graphs from geometric data, such as a set of 2D or 3D points. This subpackage includes the following new commands:












> 
> 
The Euclidean minimum spanning tree, the Delaunay graph, the Gabriel graph, the relative neighborhood graph, and the Urquhart graph are all derived from a Delaunay triangulation of the point data.
These graphs have a hierarchical relationship:
Euclidean Minimum Spanning Tree 
Relative Neighborhood Graph 
Urquhart Graph 
Gabriel Graph 
Delaunay Graph 






Note that we can also build spanning trees for this point data using norms other than the Euclidean norm, for example the 1norm; the result is similar but not identical to the Euclidean spanning tree.
NearestNeighborGraph and FarthestNeighborGraph return a nearest and farthest neighbor graph for a point set. You can also build knearest neighbor and kfarthest neighbor graphs for specified k.
Nearest Neighbor Graph 
Farthest Neighbor Graph 
2Nearest Neighbor 
2Farthest Neighbor 





The UnitDiskGraph command returns a graph in which two points are connected if their distance falls below a specified threshold.
> 
For a set of points, SphereOfInfluenceGraph draws a circle around each point with radius equal to the distance to its nearest neighbor. The sphere of influence graph is the graph whose vertices correspond to these points in which an edge between two points exists if the corresponding circles intersect at more than one point.
> 
Most of these graphs commands are not limited to two dimensions, and can be used to analyze and visualize relationships with higherdimensional data as well.
Split Graphs
IsSplitGraph returns true if a graph is can be partitioned into a clique and an independent set.
> 
> 
> 
> 
ContractSubgraph
The ContractSubgraph command returns a new graph with all the vertices in S merged into a single vertex. The neighborhood of the new vertex will be the union of the neighborhoods of all of merged vertices.
> 
> 
SpecialGraphs
Maple 2020 provides support for 18 additional Special Graphs, bringing the total to 97.
> 
BarnetteBosàkLederberg Graph 
Berlekampvan LintSeidel Graph 
BiggsSmith Graph 
BrouwerHaemers Graph 






De Bruijn Graph 
Gewirtz Graph 
Golomb Graph 
Harr Graph 






Harborth Graph 
HigmanSims Graph 
M22 Graph 
McLaughlin Graph 






Meredith Graph 
Perkel Graph 
Rooks Graph 
Schläfli Graph 






Wells Graph 
WienerAraya Graph 






