Consider four diagrams of the same graph \(G\) below.

The AVL of this graph is

{0:[2,3], 1:[3,4], 2:[0,4], 3:[0,1], 4:[1,2]} # canonical or standard AVL

or

{2:[0,4], 0:[2,3], 1:[3,4], 4:[1,2], 3:[0,1]} # w/o ordering vertices

or

{2:[4,0], 0:[2,3], 1:[3,4], 4:[2,1], 3:[0,1]} # w/o ordering adjacency lists

Even though the three AVLs above represent the same graph, we select a form of the AVL that represents all the other possible AVLs, and use it consistently. An object that represents all the objects in set is usually called a canonical or standard object. In our case, the one standard AVL is the one in which the vertices are sorted in ascending order, and in which the adjacency lists of each vertex are also sorted in ascending order. The standarization of AVLs facilitates the comparison of graphs via the comparison of their AVLs.

Our webpages focus on visual explanations and, thus, we want to standarize the diagrams of graphs, so that we can compare graphs via the comparison of a standard or canonical diagram that represents all the possible diagrams of the graph. There is no rule as to how to draw a graph, but it is common practice, specially when trying to highlight the symmetries of a graph, to place the vertices in a circular fashion, leading to diagrams that resemble crystals, flowers or snowflakes.

Let’s define the Canonical Diagram, a.k.a. CanD, of a labeled graph as the diagram that has its vertices sorted along a circle centered at an origin and spread at an equal angle. The main axis of the coordinate frame is given by the position of its 0 label, while its handedness is given by the order of the labels; this practice is similar to that of any coordinate plane. CanDs are a tool that I made up to make concepts clear; we will not find them in material outside of these web pages. The following is the CanD of the given labeled pentagram graph above, oriented in various directions and with different handedness.

To compare two CanDs, we ensure that their coordinate frames have the same orientation and handedness. CanDs are a standarization of a representation of a labeled graph, in same way that our sorted-by-keys AVLs are a standarization of an AVL. If the CanDs of two labeled graphs are equal, their other representations, like AVLs and AVMs, will also be equal; if their CanDs are different, their AVLs and AVMs will be different.

All layouts of the same labeled graph have the same CanD, but it is perfectly possible for different labelings of the same graph to have different CanDs. For example, below, on the top row, we have two different labelings of the same pentagram graph, while on the bottom row we have their CanDs, which are not equal.

A graph of order \(n\) has \(n!\) different labelings; for some graphs, all the \(n!\) labelings share the same CanD, while for other graphs, each of the \(n!\) labelings has a different CanD, and yet for others, the \(n!\) labelings divide themselves in groups that share a single CanD.

First published on Mar. 1/2026