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