Schnyder’s Algorithm for straight-line planar embeddings

A module for computing the (x,y) coordinates for a straight-line planar embedding of any connected planar graph with at least three vertices. Uses Walter Schnyder’s Algorithm.

AUTHORS:

  • Jonathan Bober, Emily Kirkman (2008-02-09) – initial version

REFERENCE:

[1]Schnyder, Walter. Embedding Planar Graphs on the Grid. Proc. 1st Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco (1994), pp. 138-147.
class sage.graphs.schnyder.TreeNode(parent=None, children=None, label=None)

A class to represent each node in the trees used by _realizer and _compute_coordinates when finding a planar geometric embedding in the grid.

Each tree node is doubly linked to its parent and children.

INPUT:

  • parent – the parent TreeNode of self
  • children – a list of TreeNode children of self
  • label – the associated realizer vertex label

EXAMPLES:

sage: from sage.graphs.schnyder import TreeNode
sage: tn = TreeNode(label=5)
sage: tn2 = TreeNode(label=2,parent=tn)
sage: tn3 = TreeNode(label=3)
sage: tn.append_child(tn3)
sage: tn.compute_number_of_descendants()
2
sage: tn.number_of_descendants
2
sage: tn3.number_of_descendants
1
sage: tn.compute_depth_of_self_and_children()
sage: tn3.depth
2
append_child(child)

Add a child to list of children.

EXAMPLES:

sage: from sage.graphs.schnyder import TreeNode
sage: tn = TreeNode(label=5)
sage: tn2 = TreeNode(label=2,parent=tn)
sage: tn3 = TreeNode(label=3)
sage: tn.append_child(tn3)
sage: tn.compute_number_of_descendants()
2
sage: tn.number_of_descendants
2
sage: tn3.number_of_descendants
1
sage: tn.compute_depth_of_self_and_children()
sage: tn3.depth
2
compute_depth_of_self_and_children()

Computes the depth of self and all descendants.

For each TreeNode, sets result as attribute self.depth

EXAMPLES:

sage: from sage.graphs.schnyder import TreeNode
sage: tn = TreeNode(label=5)
sage: tn2 = TreeNode(label=2,parent=tn)
sage: tn3 = TreeNode(label=3)
sage: tn.append_child(tn3)
sage: tn.compute_number_of_descendants()
2
sage: tn.number_of_descendants
2
sage: tn3.number_of_descendants
1
sage: tn.compute_depth_of_self_and_children()
sage: tn3.depth
2
compute_number_of_descendants()

Computes the number of descendants of self and all descendants.

For each TreeNode, sets result as attribute self.number_of_descendants

EXAMPLES:

sage: from sage.graphs.schnyder import TreeNode
sage: tn = TreeNode(label=5)
sage: tn2 = TreeNode(label=2,parent=tn)
sage: tn3 = TreeNode(label=3)
sage: tn.append_child(tn3)
sage: tn.compute_number_of_descendants()
2
sage: tn.number_of_descendants
2
sage: tn3.number_of_descendants
1
sage: tn.compute_depth_of_self_and_children()
sage: tn3.depth
2
sage.graphs.schnyder.minimal_schnyder_wood(graph, root_edge=None, minimal=True, check=True)

Return the minimal Schnyder wood of a planar rooted triangulation.

INPUT:

  • graph – a planar triangulation, given by a graph with an embedding.
  • root_edge – a pair of vertices (default is from 'a' to 'b') The third boundary vertex is then determined using the orientation and will be labelled 'c'.
  • minimal – boolean (default True), whether to return a minimal or a maximal Schnyder wood.
  • check – boolean (default True), whether to check if the input is a planar triangulation

OUTPUT:

a planar graph, with edges oriented and colored. The three outer edges of the initial graph are removed.

The algorithm is taken from [Brehm2000] (section 4.2).

EXAMPLES:

sage: from sage.graphs.schnyder import minimal_schnyder_wood
sage: g = Graph([(0,'a'),(0,'b'),(0,'c'),('a','b'),('b','c'),
....:  ('c','a')], format='list_of_edges')
sage: g.set_embedding({'a':['b',0,'c'],'b':['c',0,'a'],
....:  'c':['a',0,'b'],0:['a','b','c']})
sage: newg = minimal_schnyder_wood(g)
sage: newg.edges()
[(0, 'a', 'green'), (0, 'b', 'blue'), (0, 'c', 'red')]
sage: newg.plot(color_by_label={'red':'red','blue':'blue',
....:  'green':'green',None:'black'})
Graphics object consisting of 8 graphics primitives

A larger example:

sage: g = Graph([(0,'a'),(0,2),(0,1),(0,'c'),('a','c'),('a',2),
....: ('a','b'),(1,2),(1,'c'),(2,'b'),(1,'b'),('b','c')], format='list_of_edges')
sage: g.set_embedding({'a':['b',2,0,'c'],'b':['c',1,2,'a'],
....: 'c':['a',0,1,'b'],0:['a',2,1,'c'],1:['b','c',0,2],2:['a','b',1,0]})
sage: newg = minimal_schnyder_wood(g)
sage: sorted(newg.edges(), key=lambda e:(str(e[0]),str(e[1])))
[(0, 2, 'blue'),
 (0, 'a', 'green'),
 (0, 'c', 'red'),
 (1, 0, 'green'),
 (1, 'b', 'blue'),
 (1, 'c', 'red'),
 (2, 1, 'red'),
 (2, 'a', 'green'),
 (2, 'b', 'blue')]
sage: newg2 = minimal_schnyder_wood(g, minimal=False)
sage: sorted(newg2.edges(), key=lambda e:(str(e[0]),str(e[1])))
[(0, 1, 'blue'),
 (0, 'a', 'green'),
 (0, 'c', 'red'),
 (1, 2, 'green'),
 (1, 'b', 'blue'),
 (1, 'c', 'red'),
 (2, 0, 'red'),
 (2, 'a', 'green'),
 (2, 'b', 'blue')]

TESTS:

sage: minimal_schnyder_wood(graphs.RandomTriangulation(5))
Digraph on 5 vertices
sage: minimal_schnyder_wood(graphs.CompleteGraph(5))
Traceback (most recent call last):
...
ValueError: not a planar graph
sage: minimal_schnyder_wood(graphs.WheelGraph(5))
Traceback (most recent call last):
...
ValueError: not a triangulation
sage: minimal_schnyder_wood(graphs.OctahedralGraph(),root_edge=(0,5))
Traceback (most recent call last):
...
ValueError: not a valid root edge

REFERENCES:

[Brehm2000]Enno Brehm, 3-Orientations and Schnyder 3-Tree-Decompositions, 2000