
198 CHAPTER 6. PLANAR STRAIGHT-LINE DRAWING ALGORITHMS
Initially, the vertices of the external face are placed at the vertices of a strictly convex
polygon, P . We refer to the vertices not on the external face as internal vertices.
For a vertex v, let N(v) be the set of neighbors of v and d(v) the degree of v, i.e.,
d(v) = |N(v)|. The position of an internal vertex v is determined by the following linear
equations:
x(v) =
1
d(v)
X
w∈N (v)
x(w) (6.4)
y(v) =
1
d(v)
X
w∈N (v)
y(w) (6.5)
Tutte showed that the above system of linear equations admits a unique solution that
corresponds to a strict convex drawing of the graph. An example of a drawing constructed
with ...