The Barycentric Algorithm of Schnyder

 In the same year, Schnyder described an algorithm for solving the same task in time O(n) using a grid of size 58#58 (Schnyder, 1990). This algorithm computes three coordinates for each vertex in the sequence given by the same canonical ordering used by de Fraysseix, Pach and Pollack. In a second step, it computes the actual grid coordinates for the vertices using the barycentric coordinates.

The vertex positions are defined using a barycentric representation of the input graph G.

Definition 3122 (barycentric representation)

A barycentric representation of G is an injective function

59#59

satisfying the following conditions:

1.

v₁+v₂+v₃ = 1 for all vertices v.

2.

For each edge 60#60 and each vertex 61#61 there is some 62#62 such that u_k<w_k and v_k < w_k.

A barycentric representation of the input graph is computed by first constructing a normal labeling of the angles of the faces of the input graph. Since the input graph is triangulated, every face has exactly three angles. The angles of each face are numbered 1, 2 and 3 so that the numbers appear in counterclockwise order around the face and for each interior vertex, the angles around it in counterclockwise order form a nonempty sequence of 1's followed by a nonempty sequence of 2's followed by a nonempty sequence of 3's. Such a labeling can be constructed in linear time.

For each normal labeling, every edge has two different labels on one end while the labels on both sides of the other end are the same. We call the repeated label the label of the edge. Thus, each normal labeling defines a realizer of the graph.

Definition 3140 (realizer)

A realizer of a triangular graph G is a partition of the interior edges of G into three sets T₁, T₂ and T₃ of directed edges so that for each interior vertex v the following conditions are satisfied:

1.

The vertex v has outdegree 1 in T₁, T₂ and T₃.

2.

The counterclockwise order of the edges around v is: leaving in T₁, entering in T₃, leaving in T₂, entering in T₁, leaving in T₃, entering in T₂.

Every normal labeling has the following property: For each number in 63#63 there is exactly one vertex on the outer face where every adjacent angle is labeled i. For each interior vertex, there is exactly one path leaving the vertex where all edges are labeled i for 64#64. This path ends in the vertex of the outer face where all adjacent edges are labeled i. These 3 paths leaving each interior vertex define 3 regions of the graph and the number of faces in each of these regions are the 3 barycentric coordinates of the vertex.

If we have 3 arbitrary noncolinear points 65#65 and 66#66 in the plane and vertex v has the barycentric coordinates (v₁,v₂,v₃), then drawing every vertex v at position 67#67 will result in a planar straight-line embedding of the graph.