Section 3.4 Planarity
Asking if a graph is planar is equivalent to asking for an arrangement of the vertices in the plane so that edges may be drawn without crossing, what is known as a planar embedding. As one of the Platonic solids we know the skeleton of a cube is a planar graph.
Every graph in Sage carries an assignment of the vertices to locations (coordinates) in the plane. This is known as the position dictionary. A particular embedding is also sometimes known as a layout in Sage. First we create a circular layout for the cube graph, which is a Python dictionary (function) associating vertices (bit strings) to ordered pairs (coordinates).
Python dictionarys do not have a guaranteed order on successive computations and the sines and cosines used to produce these coordinates may behave slightly different on different computers. Do you see those numbers that are very close to zero above? So we can test the output, and keep this tract reliable, we will scale onto a circle of radius \(1000\) and round the values of the coordinates in circle to integers and package up the results as a predictable list of triples. This has the by-product of demonstrating how to access the key-value pairs in a dictionary. (The use of RDF() converts the Python float data type into Sage's 53-bit precision floating point numbers.)
Many of the named graphs in Sage come with “nice” embeddings by default, and so it is with the cube graph. Although in search of greater generality, the default layout places two vertices simultaneously at the center.
To demonstrate working with embeddings, we will install the circular layout we just computed.
Now we compute a planar layout for the cube graph, and install it into the graph, replacing the circular layout.
A planar graph can also have a combinatorial embedding where each vertex has a list of its neighbors in order (clockwise in Sage). Sometimes this is sufficient or useful in some contexts. This embedding can be computed and stored along with the graph via the is_planar() method, and can then be retrieved with the .get_embedding() method. In teh first line, the method will return True. But we do not care so much about that right now. So we supress it by assigning it to the customary Python throwaway variable, _. As above, the embedding is a dictionary, but we will convert to a list for testing purposes.
What happens when a graph is not planar? Sage can find the subgraph guaranteed by Kuratowski's Theorem, which will be homeomorphic to \(K_5\) or \(K_{3,3}\text{.}\) This example uses the 4-dimensional cube, which is not planar.
Graphs have a .genus() method to determine the topological invariant of the minimal surface where the graph can be embedded. However, it seems to be so slow as to be not of much value.