Summary: 
Sam Sanjabi, Rachel Potvin  
Original Paper: 
Ramaswami, Ramos, and Toussaint 
INPUT :  T, a triangulated polygon 
OUTPUT :  Q, a quadrangulated polygon 
 
Figure 1:  Example of simplest construction of a quadrangulation from a triangulated polygon 
INPUT :  T, a triangulated polygon with n vertices 
OUTPUT :  Q, a quadrangulated polygon 
(a)  (b)  
(c)  (d)  
Figure 2: Quadrangulation via Hamiltonian triangulation. (a) Original triangulated polygon. (b) Geometrical dual tree inserted with each node of the tree connected to the three vertices of its correspondin g triangle. (c) Original diagonals removed. (d) A resulting quadrangualtion with a single triangle remaining, where an outer Steiner point is inserted. 
Theorem 1: 
Floor(n/3) outer Steiner points are always sufficient, and sometimes necessary, to quadrangulate a triangulated simple polygon of n vertices. Furthermore, these Steiner points may be located in O(n) time. 
MATCHING EDGE  :  edge, e, in a matching, M, of an undirected graph G=(V,E) 
FREE EDGE  :  edge, e, an element of G=(V,E) but not of the matching, M 
MATCHED NODE  :  a node on a matching edge of G=(V,E) 
FREE NODE  :  a node not on a matching edge of G=(V,E) 
MATE(u), where u,v are elements of V(G)  :  v = mate(u) AND u = mate(v) iff edge(u,v) is an element of the matching, M 
ALTERNATING PATH  :  An alternating path is a simple path in G whose edges are alternately matching and free. 
AUGMENTING PATH  :  An alternating path such that both of its enpoints are unmatched nodes. 
Lemma 1: 
M is a maximum matching of a graph G=(V,E) iff G has no augmenting path with respect to M. 
h  = 
level(u)  = 
v_{h}  = 
CASE[0]  :  degree(par(v)) = 1 => T consists of two nodes and an edge, match v and par(v) 
CASE[1]  :  degree(par(v)) = 2 => match v and par(v) 
CASE[2]  :  degree(par(v)) = 3 => AND v is the left child of par(v) => match v and par(v) 
CASE[3]  :  degree(par(v)) = 3 => AND v is the right child of par(v) => leave v unmatched 
Theorem 2: 
The matching, M, found by the above algorithm for the tree, T, cannot have any augmenting paths with respect to M. 
Lemma 2: 
There exists a maximum matching for a tree, T, such that all its unmatched nodes are leaves of T. 

Theorem 3: 
The PercolateUP and DOWN algorithm quadrangulates a triangulated simple ngon using a minimmum number of outer Steiner points. This algorithm runs in O(n) time. 