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 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
'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