get_canonical_ordering(embedding, outer_face)
The canonical ordering of nodes (v1, ..., vn) must fulfill the following conditions: (See Lemma 1 in )
For the subgraph G_k of the input graph induced by v1, ..., vk it holds:
2-connected
internally triangulated
the edge (v1, v2) is part of the outer face
For a node v(k+1) the following holds:
The node v(k+1) is part of the outer face of G_k
It has at least two neighbors in G_k
All neighbors of v(k+1) in G_k lie consecutively on the outer face of G_k (excluding the edge (v1, v2)).
The algorithm used here starts with G_n (containing all nodes). It first selects the nodes v1 and v2. And then tries to find the order of the other nodes by checking which node can be removed in order to fulfill the conditions mentioned above. This is done by calculating the number of chords of nodes on the outer face. For more information see .
The embedding must be triangulated
The nodes on the outer face of the graph
A list of tuples :None:None:`(vk, wp_wq)`. Here :None:None:`vk` is the node at this position in the canonical ordering. The element :None:None:`wp_wq` is a list of nodes that make up the outer face of G_k.
Returns a canonical ordering of the nodes
Hover to see nodes names; edges to Self not shown, Caped at 50 nodes.
Using a canvas is more power efficient and can get hundred of nodes ; but does not allow hyperlinks; , arrows or text (beyond on hover)
SVG is more flexible but power hungry; and does not scale well to 50 + nodes.
All aboves nodes referred to, (or are referred from) current nodes; Edges from Self to other have been omitted (or all nodes would be connected to the central node "self" which is not useful). Nodes are colored by the library they belong to, and scaled with the number of references pointing them