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)

Bases: object

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 -1 to -2) The third boundary vertex is then determined using the orientation and will be labelled -3.
  • 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,-1),(0,-2),(0,-3),(-1,-2),(-2,-3),
....:  (-3,-1)], format='list_of_edges')
sage: g.set_embedding({-1:[-2,0,-3],-2:[-3,0,-1],
....:  -3:[-1,0,-2],0:[-1,-2,-3]})
sage: newg = minimal_schnyder_wood(g)
sage: newg.edges()
[(0, -3, 'red'), (0, -2, 'blue'), (0, -1, 'green')]
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,-1),(0,2),(0,1),(0,-3),(-1,-3),(-1,2),
....: (-1,-2),(1,2),(1,-3),(2,-2),(1,-2),(-2,-3)], format='list_of_edges')
sage: g.set_embedding({-1:[-2,2,0,-3],-2:[-3,1,2,-1],
....: -3:[-1,0,1,-2],0:[-1,2,1,-3],1:[-2,-3,0,2],2:[-1,-2,1,0]})
sage: newg = minimal_schnyder_wood(g)
sage: sorted(newg.edges(), key=lambda e:(str(e[0]),str(e[1])))
[(0, -1, 'green'),
 (0, -3, 'red'),
 (0, 2, 'blue'),
 (1, -2, 'blue'),
 (1, -3, 'red'),
 (1, 0, 'green'),
 (2, -1, 'green'),
 (2, -2, 'blue'),
 (2, 1, 'red')]
sage: newg2 = minimal_schnyder_wood(g, minimal=False)
sage: sorted(newg2.edges(), key=lambda e:(str(e[0]),str(e[1])))
[(0, -1, 'green'),
 (0, -3, 'red'),
 (0, 1, 'blue'),
 (1, -2, 'blue'),
 (1, -3, 'red'),
 (1, 2, 'green'),
 (2, -1, 'green'),
 (2, -2, 'blue'),
 (2, 0, 'red')]

REFERENCES:

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