TABLE OF CONTENTS In this section we describe the realizer method by Schnyder for finding a straight line grid drawing of a plane graph on an ( n ?2) ( n ?2) grid.
Schnyder used a barycentric representation of a plane graph, which is obtained from a realizer of a triangulated plane graph G. A realizer is a kind of partition of the inner edges of G into three sets, each inducing a tree in G. Defining a labeling of a triangulated plane graph, he showed that every triangulated plane graph has a realizer. We present a barycentric representation in Section 5.3.1, a labeling in Section 5.3.2, and a realizer in Section 5.3.3, and a drawing algorithm in Section 5.3.4.
A barycentric representation of a graph G is an injective function f: v ? V(G) ?( v 1 , v 2 , v 3) ? R 3 satisfying the following two conditions:
v 1+ v 2+ v 3 =1 for all vertices v; and
for each edge (x, y) and each vertex z 
{x, y}, there is some index k ?{1, 2, 3} such that x k< z k and y k< z k .
One can view v 1 , v 2 and v 3 as barycentric coordinates of vertex v. Condition (1) means that each vertex v of G is...
