Morphing Schnyder Drawings of Planar Triangulations - Graph Drawing - page 297

2. Any interior edge of T

| C remains with the same orientation and changes
colour from i to i +1. See edges incident to b in Figure 4.

Other edges are unchanged. The reverse operation is a counterclockwise flip ,
which Brehm calls a flop . Brehm [5, p. 44] proves that a flip yields another
Schnyder wood. Consider the graph with a vertex for each Schnyder wood of T
and a directed edge ( S, S ) when S can be obtained from S by a clockwise flip.
This graph forms a distributive lattice [5], [11], [14]. Ignoring edge directions, the
distance between two Schnyder woods in this graph is called their flip distance .

Lemma 2 (Brehm (see the long version)). In a planar triangulation on n
vertices the flip distance between any two Schnyder woods is O ( n 2 ) ,andaflip
sequence of that length can be found in linear time per flip.

3M inR sut

Theorem 3. Let T be a planar triangulation and let S and S be two Schnyder
woods of T .Let ʓ and ʓ be weighted Schnyder drawings of T obtained from
S and S together with some weight distributions. There exists a sequence of
straight-line planar drawings of Tʓ = ʓ 0 ,...,ʓ k +1 = ʓ such that k is O ( n 2 ) ,
the linear morph ʓ i ,ʓ i +1 is planar, 0 ≤ i ≤ k , and the vertices of each ʓ i ,

1 ≤ i ≤ k , lie in a (6 n − 15) × (6 n − 15) grid. Furthermore, these drawings can

be obtained in polynomial time.

We now describe how the results in the upcoming sections prove the theorem.
Lemma4(Section4)provesthatifweperform a linear morph between two
weighted Schnyder drawings that differ only in their weight distribution then
planarity is preserved. Thus, we may take ʓ 1 and ʓ k to be the drawings obtained
from the uniform weight distribution on S and S respectively. By Schnyder's
Theorem 1 these drawings lie on a (2 n− 5) × (2 n− 5) grid and we can scale them
up to our larger grid. By Lemma 2 (Section 2) there is a sequence of k flips,
k O ( n 2 ),thatconverts S to S . Therefore it suces to show that each flip in

the sequence can be realized via a planar morph composed of a constant number
of linear morphs. In Theorem 7 (Section 5) we prove that if we perform a linear
morph between two weighted Schnyder drawings that differ only by a flip of a
face then planarity is preserved. In Theorem 11 (Section 6) we prove that if two
Schnyder drawings with the same uniform weight distribution differ by a flip of a
separating triangle then there is a planar morph between them composed of three
linear morphs. The intermediate drawings involve altered weight distributions
(here Lemma 4 is used again), and lie on a grid of the required size. Putting
these results together gives the final sequence ʓ 0 ,...,ʓ k +1 .Alltheintermediate
drawings lie in a (6 n

∈

15) grid and each of them can be obtained in
O ( n ) time from the previous one. This completes the proof of Theorem 3 modulo
the proofs in the following sections.

− 15) × (6 n −