FPP_PlanarCoords ( G )
Algorithm:
1. Triangulate orginal graph
2. Canonical order all vertices
3. Initialize x,y coordinates and M for V1,V2, and V3
v1.M={v1,v2,v3}
v2.M={v2}
v3.M={v2,v3}
4. In the canonical order, for each vertex
1. find the vertices on the outface in order
2. shift vertices in the subset M of Wp+1 and Wq
3. calculate the x,y coordinates of Vk+1
4. updating M for all the outface vertices
wi.M=wi.M+{vk+1} for i<=p
vk+1.M=wp+1.M+{vk+1}
wj.M=wj.M for j>=q
|
Schnyder_PlanarCoords ( G )
Algorithm:
1. Triangulate orginal graph
2. Canonical order all vertices
3. Normal label interior edges of G to i->Ti (i=1,2,3)
4. Calculate for each interior vertex v
pathi : vertices on the i-path from v to v1, v2, or vn
pn : number of vertices on the i-path starting at v
ti : number of vertices in the subtree of Ti rooted at v
ri : number of vertices in region Ri(v) for v
5. Calculate barycentric representation for each v: vi'=ri - pi-1
v->(v1',v2',v3')/(n-1)
A barycentric representation of a graph G is
an injective function v->(v1,v2,v3) that satisfies:
a.) v1+v2+v3=1 for all v
b.) for each edge (x,y) and each vertex z not x or y,
there is some k (k=1,2 or 3) such that xk < zk and yk < zk
|