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

Previous topic

Linear Extensions of Directed Acyclic Graphs.

Next topic

Graph Plotting

This Page