Every embedding can be described by an embedding adjacency matrix. In every part of it, the first vertex is followed by a sequence of its adjacent vertices given in the same (left or right) cyclic order. For the ending points, only the cyclic permutation corresponding to them is important, and not their particular position in the permutation. For example, a planar embedding of the octahedron graph

O = {{1,2},{1,3},{1,5},{1,6},{2,3},{2,4},{2,6},{3,4},{3,5},{4,5},{4,6},{5,6}}

is 

{{1,2,6,5,3},{2,3,4,6,1},{3,1,5,4,2},{4,3,5,6,2},{5,3,1,6,4},{6,2,4,5,1}}.
(1)

igure

After drawing the first vertex 1, we draw its incident edges in the right cyclic order: {1,2}, {1,6}, {1,5}, {1,3}, then we continue with the vertex 2 and its adjacent edges in the same right cyclic order: {2,3}, {2,4}, {2,6}, {2,1}, having in mind that {2,1} is already drawn as {1,2}, etc., till exhausting the graph. 

The LinKnot function fPlanarEmbGraph (webMathematica fPlanarEmbGraph) gives the planar embedding of a 3-connected planar graph given by a list of unordered pairs. The output is a list that consists of the input graph, its planar embedding, and the faces of the planar embedded graph. The basis of this program is the external program planarity.exe written by J.M. Boyer (Boyer and Myrvold, 2004). The LinKnot function DrawPlanarEmbGraph (webMathematica DrawPlanarEmbGraph) draws a planar embedding of a graph given by a list of unordered pairs, and the function Draw PlanarEmbKL draws a planar embedding of a KL without showing double edges. The basis of those functions is the program 3-Dimensional Convex Drawings of 3-Connected Planar Graphs by M.Ochiai, N.Imafuji and N.Morimura. 
 
 

PreviousContentsNext