Proofs: Schnyder drawing algorithm

Schnyder's algorithm draws every planar graph without crossings on the (n-2) by (n-2) grid full

This proof shows: correctness, termination.

Let $\rho$ be a planar rotation system of a simple graph $G$ with $n \ge 3$ vertices. We show that SCHNYDER-DRAWING stops and returns integer points in $\{0, \ldots, n - 2\}^2$ that give a planar straight-line drawing of $G$. Indices of colours are taken mod 3. A plane graph is a graph with a fixed planar rotation system; we use the Jordan curve theorem for the cycles of a plane graph.

Step 1 (line L1 gives a plane triangulation that contains $G$). Each new edge is drawn inside one face, between two corners of that face, so the graph stays plane, and the old edges keep their cyclic order. Joining two components at any corners merges one face of each into one face. In the second phase, the new edge $ab$ sits in the corner of $v$ between $va$ and $vb$. Here $a \ne b$, and $ab$ is not an edge: otherwise $v, a, b$ is a cycle and $va$, $vb$ lie in the same biconnected component, and the union-find structure merges components exactly along such new cycles. After the pass, at every vertex any two consecutive edges, hence all edges, lie in one component, so no vertex is a cut vertex, and $G$ is 2-connected. In a 2-connected plane graph with at least 3 vertices every face is bounded by a cycle (Diestel, Section 4.2). In the third phase, a face cycle $v_0, \ldots, v_{k-1}$ with $k \ge 4$ cannot have both $v_0 v_2$ and $v_1 v_3$ as edges: both would lie outside the face, inside the disc bounded by the face cycle on the other side, with interleaved ends, and they would cross. So L1 adds a new edge each time, splits off a triangle, and stops with every face a triangle on three distinct vertices: a simple plane triangulation.

Step 2 (line L3 never gets stuck). Let $C = c_1 c_2 \cdots c_r$ with $c_1 = a_1$, $c_r = a_2$ be the current path and $G'$ the graph not yet removed. Invariant: $C$ plus the edge $a_2 a_1$ is a cycle bounding the outer face of $G'$, and every other face of $G'$ is a triangle. This holds at the start, with $C = a_1, a_3, a_2$. Suppose $r \ge 3$. If no chord other than $a_1 a_2$ exists, every $c_j$ with $1 < j < r$ is chord-free. Otherwise, take a chord $c_s c_t$ other than $a_1 a_2$ with $t - s \ge 2$ least. A chord from $c_j$, $s < j < t$, to some $c_l$ would be shorter if $s \le l \le t$, and would cross $c_s c_t$ inside the disc bounded by the cycle if $l < s$ or $l > t$. So $c_{s+1}$ is chord-free. Let $z = c_j$ be chord-free. Since the faces around $z$ are triangles, its neighbours in $G'$, counterclockwise from $p = c_{j-1}$ to $q = c_{j+1}$, form a path $p, m_1, \ldots, m_k, q$, and no $m$ is on $C$, because $z$ has no chord. Removing $z$ replaces $z$ on the path by $m_1, \ldots, m_k$; the new path is simple, and the invariant holds. The stack holds every chord-free path vertex: a new path vertex is pushed when its count is 0, and an old path vertex loses a chord only in the case $k = 0$, where it is pushed. So L3 removes $n - 2$ vertices and ends with the path $a_1, a_2$. Read backwards, the removal order $v_1 = a_1$, $v_2 = a_2$, $v_3, \ldots, v_n = a_3$ is a canonical ordering.

Step 3 (two orders). For a vertex $v$, let $\operatorname{idx}(v)$ be its position in the canonical ordering. Line L4 sets $p_1(z), p_2(z)$ to vertices removed later, so of smaller index, and $p_3(m) = z$ for vertices $m$ removed later than $z$, so of larger index. Next, build a list $\Lambda$ of vertices from left to right, going through the canonical order forwards: start with $\Lambda = (a_1, a_2)$, and insert each $v_k$ immediately before its right lower neighbour $q$. Since each $v_k$ is inserted between $p$ and $q$, after all vertices between them, $p$ precedes $v_k$, the vertices $m_j$ precede $v_k$, and $v_k$ precedes $q$. So, writing $u \to w$ for the edge from $u$ to its parent:

In particular each $T_i$ is acyclic, and following parents of colour $i$ from an inner vertex ends at a vertex with no parent of colour $i$. Such a vertex is outer. It is $a_i$: every inner edge at $a_1$ is labelled $u \to a_1$ of colour 1, since $a_1$ stays the leftmost path vertex and can only be the left neighbour $p$; likewise $a_2$ only receives colour 2, and the inner neighbours of $a_3$ are exactly the vertices below $a_3$ at the first step, which receive colour 3. So $T_i$ is a tree rooted at $a_i$, and $P_i(v)$ is well defined. Every inner edge $uv$, with $v$ earlier than $u$, is labelled exactly once, when $u$ is removed and $v$ is one of $p$, $q$ or below $u$; the edges $a_1 a_2$, $a_1 a_3$, $a_2 a_3$ get no label.

Lemma 1. For an inner vertex $v$, the paths $P_1(v)$, $P_2(v)$, $P_3(v)$ pairwise meet only in $v$.

Proof. Along $P_3(v)$ the index increases and along $P_1(v)$ and $P_2(v)$ it decreases, so $P_3(v)$ meets the others only at $v$. Along $P_1(v)$ the position in $\Lambda$ decreases and along $P_2(v)$ it increases, so they meet only at $v$. $\square$

Step 4 (the local rule). Fix an inner vertex $v = v_k$. Draw the path at the time $v$ is added as running from left to right, with the part already built below it. Counterclockwise around $v$, starting at $p$, come the vertices below $v$, then $q$, then the neighbours added later, from right to left. A later neighbour $z$ uses $v$ as its left neighbour $p$ while $v$ is on the path and $z$ is to the right of $v$, as its right neighbour $q$ when $z$ is to the left, and as a vertex below $z$ exactly once, for the vertex $z_c$ that removes $v$ from the path. Each new edge $vz$ with $z$ to the right is inserted in the rotation at $v$ next to the current edge to the right path neighbour, on the upper side, and similarly on the left. So counterclockwise around $v$ we see: the outgoing edge of colour 1 (to $p$), incoming edges of colour 3 (from the vertices below $v$), the outgoing edge of colour 2 (to $q$), incoming edges of colour 1 (later neighbours on the right), the outgoing edge of colour 3 (to $z_c$), and incoming edges of colour 2 (later neighbours on the left). This is the rule of a Schnyder wood. Rotating the colour names, at every inner vertex, counterclockwise:

Step 5 (regions). For an inner vertex $v$, the cycle $P_{i+1}(v) \cup P_{i-1}(v) \cup a_{i+1} a_{i-1}$ is simple by Lemma 1. Let $R_i(v)$ be the closed disc that it bounds inside the outer triangle; we also write $R_i(v)$ for the set of vertices in it. Near $v$, the disc is one of the two wedges between $\text{out}_{i+1}(v)$ and $\text{out}_{i-1}(v)$. It is the wedge that does not contain $\text{out}_i(v)$, because $P_i(v)$ leaves $v$ through that edge, never meets the cycle again (Lemma 1, and $a_i$ is not on the cycle), and ends at the outer vertex $a_i$, outside the disc. By (1) this wedge contains the incoming edges of colour $i$ at $v$ and no incoming edges of colours $i \pm 1$. Along $P_{i-1}(v)$, the disc stays on one side. At a vertex $w \ne v$ of $P_{i-1}(v)$, the path enters through an incoming edge of colour $i - 1$ and leaves through $\text{out}_{i-1}(w)$, and by (1) the side of the disc contains $\text{in}_i^{*}$ and $\text{out}_{i+1}(w)$, but no incoming edge of colour $i + 1$, since those lie on the other side, between $\text{out}_{i-1}(w)$ and $\text{out}_i(w)$. Symmetrically, at a vertex $w \ne v$ of $P_{i+1}(v)$, the side of the disc contains $\text{in}_i^{*}$ and $\text{out}_{i-1}(w)$, and no incoming edge of colour $i - 1$. At $a_{i+1}$ and $a_{i-1}$ no edge of colour $i \mp 1$ enters. We record:

(A) No edge of colour $i + 1$ enters a vertex of $P_{i-1}(v)$ from inside $R_i(v)$, and no edge of colour $i - 1$ enters a vertex of $P_{i+1}(v)$ from inside $R_i(v)$. Every edge of colour $i$ that enters a boundary vertex comes from inside, and every outgoing edge of colour $i$ at a boundary vertex points outside.

The three discs $R_1(v)$, $R_2(v)$, $R_3(v)$ cover the outer triangle and overlap only on the three paths, since the three paths cut the triangle into three parts.

Lemma 2. Let $v$ be inner and $u \in R_i(v)$ an inner vertex, $u \ne v$. Then $R_i(u) \subseteq R_i(v)$. If $u \notin P_{i-1}(v)$, then $P_{i+1}(u)$ does not meet $P_{i-1}(v)$; if $u \in P_{i-1}(v)$, then $P_{i+1}(u)$ meets $P_{i-1}(v)$ only in $u$.

Proof. Follow $P_{i+1}(u)$. It can leave the disc only through a boundary vertex. If it reaches a vertex of $P_{i+1}(v)$, it continues along $P_{i+1}(v)$, since both follow the parents in $T_{i+1}$, and stays on the boundary. By (A) it cannot enter a vertex of $P_{i-1}(v)$ from inside; and if it starts at $u \in P_{i-1}(v)$, then $\text{out}_{i+1}(u)$ points into the disc, as shown in Step 5. So $P_{i+1}(u)$ stays in $R_i(v)$ and meets $P_{i-1}(v)$ at most in its start. Symmetrically, $P_{i-1}(u)$ stays in $R_i(v)$. The cycle bounding $R_i(u)$ therefore lies in the disc $R_i(v)$, and so does the disc it bounds. $\square$

Lemma 3. Let $v$ be inner and $u \in R_i(v)$ an inner vertex, $u \ne v$. Then $x_i(u) \le x_i(v)$, with equality only if $u \in P_{i-1}(v)$.

Proof. Let $R = R_i(v)$ and $R' = R_i(u) \subseteq R$. A vertex of $P_{i-1}(v)$ that lies in $R'$ is on the boundary of $R$, hence on the boundary of $R'$, so it lies on $P_{i+1}(u)$ or $P_{i-1}(u)$.

If $u \notin P_{i-1}(v)$, let $w$ be the first vertex of $P_{i-1}(u)$ on $P_{i-1}(v)$; it exists because both end at $a_{i-1}$, and from $w$ on the two paths coincide. The vertices of $P_{i-1}(v)$ before $w$ are not on $P_{i-1}(u)$, and not on $P_{i+1}(u)$ by Lemma 2, so they are in $R \setminus R'$. Hence

If $u \in P_{i-1}(v)$, then $P_{i-1}(u)$ is the part of $P_{i-1}(v)$ from $u$ on, and the vertices before $u$ are not on $P_{i+1}(u)$ by Lemma 2, so they are in $R \setminus R'$, and the same computation gives $x_i(v) - x_i(u) \ge 0$. $\square$

Step 6 (lines L5 to L7 compute $|R_i(v)|$). Let $u$ be strictly inside $R_i(v)$. $P_i(u)$ ends at $a_i \notin R_i(v)$, so it reaches a first boundary vertex $x$; $x$ is inner, since no edge of colour $i$ enters $a_{i \pm 1}$. Conversely, by (A), the children in $T_i$ of a boundary vertex lie strictly inside, and a path in $T_i$ that touches the boundary leaves the disc through an outgoing edge of colour $i$ and can never re-enter it, since edges of colour $i$ enter the boundary only from inside. So the vertices strictly inside $R_i(v)$ are the disjoint union, over the inner vertices $x$ of $P_{i+1}(v) \cup P_{i-1}(v)$, of the subtrees of $x$ in $T_i$ without $x$. Counting $v$ once,

which is line L7. Line L6 computes $\lvert P_j(v) \rvert = \lvert P_j(p_j(v)) \rvert + 1$ and $\Sigma_j^i(v) = \Sigma_j^i(p_j(v)) + D_i(v) - 1$ from the root of $T_j$ down.

Step 7 (coordinates). Every vertex lies in exactly one region, except the vertices of $P_j(v) \setminus \{v\}$, which lie in two, and $v$, which lies in three. So

and the corners of L8 sum to $n - 1$ too. Since $R_i(v) \supseteq P_{i+1}(v) \cup P_{i-1}(v)$ and $\lvert P_{i+1}(v) \rvert \ge 2$, every coordinate of an inner vertex is at least 1, hence at most $n - 3$. So all output points lie in $\{0, \ldots, n - 2\}^2$.

For $i \in \{1, 2, 3\}$ write $u \prec_i v$ if $(x_i(u), x_{i+1}(u))$ is lexicographically smaller than $(x_i(v), x_{i+1}(v))$. Claim: for every edge $uw$ and every vertex $v \notin \{u, w\}$, there is an $i$ with $u \prec_i v$ and $w \prec_i v$.

If $v = a_i$, take this $i$: every other vertex has $x_i \le \max(1, n - 3) < n - 2$ when $n \ge 4$; for $n = 3$ the graph is a triangle and there is nothing to prove. If $v$ is inner, the edge $uw$ does not cross the three paths of $v$, so both ends lie in one region $R_i(v)$. Take an end $u$. If $u$ is inner, Lemma 3 gives $x_i(u) < x_i(v)$, or $x_i(u) = x_i(v)$ and $u \in P_{i-1}(v) \setminus \{v\}$. In the second case $u$ lies on the boundary path $P_{(i+1)+1}(v)$ of $R_{i+1}(v)$ and, by Lemma 1, not on $P_i(v)$, so Lemma 3 for colour $i + 1$ gives $x_{i+1}(u) < x_{i+1}(v)$. Either way $u \prec_i v$. If $u$ is a corner in $R_i(v)$, it is $a_{i+1}$, with $x_i = 0 < x_i(v)$, or $a_{i-1}$, with $x_i = 1 \le x_i(v)$ and $x_{i+1} = 0 < x_{i+1}(v)$. This proves the claim.

Step 8 (no crossings). All points lie in the plane $x_1 + x_2 + x_3 = n - 1$, and L9 projects it to the first two coordinates by an affine bijection. For a small $\varepsilon > 0$, the linear function $\varphi_i = x_i + \varepsilon x_{i+1}$ orders the integer points as $\prec_i$ does. Distinct vertices get distinct points: if $x(u) = x(v)$, pick an edge $uw$ with $w \ne v$, which exists since every vertex of a triangulation with $n \ge 4$ has degree at least 3; the claim gives $u \prec_i v$, a contradiction. A vertex $v$ does not lie on an edge $uw$ with $v \notin \{u, w\}$, because $\varphi_i(v) > \max(\varphi_i(u), \varphi_i(w))$. Two edges with a common end overlap only if one contains the other end, which was just excluded. Suppose edges $uw$ and $st$ with four distinct ends intersect. By the claim there are $i$ with $\varphi_i(s) > \varphi_i(u), \varphi_i(w)$ and $j$ with $\varphi_j(t) > \varphi_j(u), \varphi_j(w)$. If $i = j$, both $s$ and $t$, and the whole segment $st$, lie in the open half-plane $\varphi_i > \max(\varphi_i(u), \varphi_i(w))$, which misses the segment $uw$. So $i \ne j$, and likewise there are $k \ne l$ with $u$ beating $st$ in $\varphi_k$ and $w$ in $\varphi_l$. Two 2-element subsets of $\{1, 2, 3\}$ meet, say $i = k$. Then $\varphi_i(s) > \varphi_i(u)$ and $\varphi_i(u) > \varphi_i(s)$, a contradiction. So the drawing of the triangulation is planar, and so is the drawing of its subgraph $G$.

Step 9 (orientation). For $n \ge 4$ the triangulation is 3-connected, so its planar embeddings are $\rho$ and its mirror image, and the drawing realizes one of them. The corners $(n - 2, 1)$, $(0, n - 2)$, $(1, 0)$ are in counterclockwise order, since $(-(n - 2))(-1) - (n - 3)(3 - n) = (n - 2) + (n - 3)^2 > 0$, and in $\rho$ the outer face lists $a_1, a_2, a_3$ counterclockwise too. So the drawing realizes $\rho$, not its mirror image, and the edges of $G$ keep their order. For $n = 3$ this is immediate.

Termination. Every loop runs over a finite set: L1 adds at most $3n - 6$ edges, L3 removes each vertex at most once and pops each pushed vertex once, and L5 to L7 pass over each tree a constant number of times. $\blacksquare$