-
Notifications
You must be signed in to change notification settings - Fork 4
Rotation Systems
A rotation system is a combinatorial representation of an embedding of a graph on a surface. Specifically, we associate with each vertex of a simple graph a circular ordering of its neighbors.
This is implemented in the SimpleGraphs module as a dictionary mapping vertices to a
RingList of its
neighbors. The rotation system of a graph is held in the graph's cache: G.cache[:RotationSystem].
The function set_rot is used to attach a rotation system to a graph. If G is an UndirectedGraph{T} then
the rotation system is a Dict{T,RingList{T}}. Use set_rot(G) to attach a default rotation system or
set_rot(G,d) to attach a rotation system d to the graph.
The function check_rot(G,d) may be used to check if d is a valid rotation system for the graph G.
A random rotation system can be attached to a graph using rand_rot(G).
Some constructors automatically give their output graph a rotation system. These include the five Platonic graphs
(Tetrahedron, Octahedron, Icosahedron, Dodecahedron, and Cube(n) for n≤3),
as well as Path, Cycle, Wheel, Buckyball, Petersen, and Grid.
Some functions (such as euler_char or faces) requires the graph to have a rotation system. If the graph does not have a rotation system, a default one is assigned and an alert is issued.
julia> T = RandomTree(10)
Random tree (n=10, m=9)
julia> euler_char(T)
[ Info: Giving this graph, Random tree (n=10, m=9), a default rotation system
2
The function get_rot(G) returns (a copy of) the rotation system associated with the graph. Use get_rot(G,v) to get
the RingList of neighbors of G.
julia> using RingLists
julia> G = Spindle()
Moser Spindle (n=7, m=11)
julia> set_rot(G)
julia> get_rot(G)
Dict{Int64,RingList{Int64}} with 7 entries:
7 => [ 4 → 5 → 6 → 4 ]
4 => [ 2 → 3 → 7 → 2 ]
2 => [ 1 → 3 → 4 → 1 ]
3 => [ 1 → 2 → 4 → 1 ]
5 => [ 1 → 6 → 7 → 1 ]
6 => [ 1 → 5 → 7 → 1 ]
1 => [ 2 → 3 → 5 → 6 → 2 ]
Once a rotation system is attached to a graph, one can get the set of faces of graph using the faces function. Each
face is represented as a RingList of (directed) edges that bound the face.
The function euler_char returns the Euler characteristic of the embedding. Note that the rotation system corresponds
to a planar embedding exactly wnen the Euler characteristic is 2.
The faces function will give an incorrect result if the graph is not connected. This is because there will be
a face that is not a 2-cell and therefore not bounded by a cyclic list of (directed) edges.
julia> G = Path(8);
julia> delete!(G,4,5);
julia> components(G)
{{1,2,3,4},{5,6,7,8}}
julia> set_rot(G)
julia> collect(faces(G))
2-element Array{RingList{Tuple{Int64,Int64}},1}:
[ (1, 2) → (2, 3) → (3, 4) → (4, 3) → (3, 2) → (2, 1) → (1, 2) ]
[ (5, 6) → (6, 7) → (7, 8) → (8, 7) → (7, 6) → (6, 5) → (5, 6) ]
Likewise, if the graph has no edges, faces cannot find any faces.
julia> G = IntGraph(3)
SimpleGraph{Int64} (n=3, m=0)
julia> faces(G)
Ø
julia> G = Complete(0)
Complete graph K(0) (n=0, m=0)
julia> faces(G)
Ø
Given a graph G, the function dual(G) returns a new graph whose vertices are the faces of G in which
two faces (vertices of the new graph) are adjacent if they share a common edge. The dual of G depends on
its rotation system.
julia> G = Octahedron()
Octahedron graph (n=6, m=12)
julia> H = dual(Cube(3))
Dual of Cube graph Q(3) (n=6, m=12)
julia> char_poly(G)
-16*x^3 - 12*x^4 + x^6
julia> char_poly(H)
-16*x^3 - 12*x^4 + x^6
Faces, as returned by the faces function, are RingList objects containing a cyclic sequence of (directed) edges:
julia> G = Octahedron()
Octahedron graph (n=6, m=12)
julia> first(faces(G))
[ (2, 6) → (6, 4) → (4, 2) → (2, 6) ]
However, to simplify matters a bit, the vertices of the dual of a graph are reduced to just a list of the vertices
on that face boundary. So the face reported above becomes the vertex [2, 6, 4] of dual(G):
julia> H = dual(G)
Dual of Octahedron graph (n=8, m=12)
julia> [2,6,4] ∈ H.V
true
Changing a graph's embedding does not change its rotation system. Conversely, changing a graph's rotation system does not change its embedding.
- To use the graph's embedding to change the rotation system use
embed_rot(G). - To use the graph's rotation system to change its embedding use
embed(G,:tutte)orembed(G,:tutte,outside=F)whereFis a list of vertices specifying the outside face.
In this example we consider a wheel graph with five vertices. This is a graph consisting of a four-cycle (vertices 1,2,3,4) and another vertex, 5, adjacent to all vertices on that cycle.
We begin by simply using the default rotation system:
julia> G = Wheel(5)
Wheel graph with 5 vertices (n=5, m=8)
julia> set_rot(G) # overwrite the automatic rotation system given to Wheel graphs with a default one
julia> collect(faces(G))
3-element Array{RingLists.RingList{Tuple{Int64,Int64}},1}:
[ (1, 2) → (2, 5) → (5, 1) → (1, 4) → (4, 5) → (5, 3) → (3, 4) → (4, 1) → (1, 2) ]
[ (1, 5) → (5, 4) → (4, 3) → (3, 2) → (2, 1) → (1, 5) ]
[ (2, 3) → (3, 5) → (5, 2) → (2, 3) ]
julia> euler_char(G)
0
Now let's attach a rotation system based on a planar embedding.
julia> using RingLists
julia> d = Dict{Int,RingList{Int}}()
Dict{Int64,RingList{Int64}}()
julia> d[1] = RingList(2,5,4);
julia> d[2] = RingList(1,3,5);
julia> d[3] = RingList(2,4,5);
julia> d[4] = RingList(1,5,3);
julia> d[5] = RingList(1,2,3,4);
julia> set_rot(G,d)Dict{Int64,RingList{Int64}}()
And now get the faces and Euler characteristic:
julia> collect(faces(G))
5-element Array{RingList{Tuple{Int64,Int64}},1}:
[ (1, 2) → (2, 5) → (5, 1) → (1, 2) ]
[ (1, 4) → (4, 3) → (3, 2) → (2, 1) → (1, 4) ]
[ (3, 4) → (4, 5) → (5, 3) → (3, 4) ]
[ (2, 3) → (3, 5) → (5, 2) → (2, 3) ]
[ (1, 5) → (5, 4) → (4, 1) → (1, 5) ]
julia> euler_char(G)
2
As noted, a face of a graph is represented as a RingList of pairs of vertices that are (directed) edges bounding the face.
To convert this to a list of vertices bounding the face, one may do this:
julia> F = first(faces(G))
[ (1, 2) → (2, 5) → (5, 1) → (1, 2) ]
julia> first.(F)
3-element Array{Int64,1}:
1
2
5