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 ofself
children
– a list of TreeNode children ofself
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