|--------------| |--------------|
| 1 | | 2 |
A----B----C----D------E----F----G----H
\ 3| 4 / \ 5 | 6 /
\ | / \ | /
\ | / 7 \ | /
\|/ \|/
I J
Figure 1
Figure 1 is obviously planar. But does Figure 1 have a "dual"?
Consider Face 7. Its borders are A-I-C-D-E-F-J-H-E-D-A. Note that
edge ED forms two seperate and distinct sections of the border of Face 7.
Is this possible? Does a 'face' need a continuous border to be a face?
The dual needs 15 edges to be a triangulation. There are 6 edges for sure; ie,
13, 14, 34, 23, 25 & 56. There are six more; ie, 17, 27, 37, 47, 57 & 67 for
a total of 12. This not enough for triangulation.
Calculation of the Number of Edges in the Dual;
The cubic is seen as being divided in to three areas; ie Left, Middle & Right
|--------------| |--------------|
| 1 | | 2 |
A----B----C----D------E----F----G----H
\ 3| 4 / \ 5 | 6 /
\ | / \ | /
\ | / 7 \ | /
\|/ \|/
I J
Left Middle Right
Figure 2
Assume that the cubic has n vertices. Then it will have C_f = 0.5*n + 2 faces.
There is one face in the M area. The faces in the L area will combine with the
one face in M to provide 3*(L_f + 1) - 6 = 3*L_f - 3 edges to the dual. The R and M faces also combine to provide another 3*(R_f + 1) - 6 = 3*R_f - 3 edges to the dual. Since L and R do not provide any edges the total number of edges is
E_max = (3*(L_f - 3)+ 3*R_f - 3) = 3*(L_f + R_f) - 6
We know that (L_f + R_f) = 0.5*n + 1. Therefore,
E_max = 3*(0.5*n + 1) - 6 = 1.5*n - 3
Now the number of edges in a triangulation is T_e = 3*C_f - 6. then
T_e = 3*(0.5*n + 2) - 6 = 1.5*n
Let' try an example: Let C_v = n = 22 say. Then C_f = .5*22 + 2 = 13 = T_v
T_e = 3*T_v - 6 = 3*13 - 6 = 33.
Assume that L_f = 3, Then R_f = 9. The number of edges contributed by L_f + M_f
L/M_e = 3*4 - 6 = 6. The number of edges contributed by RL_f + M_f is
R/M_e = 3*10 - 6 24
L/M_e + R/M_e = 30, which is T_e - 3
In Figure 2, there are 3 faces in the L & R areas and 1 face in the middle.
The faces in L and R do not provide any edges in the dual. Only the combination
of faces in L and M and R & M. The maximum number of edges provided by each
combo is
3*(L_f + M_f)-6 and 3*(R_f + M_f) -6
There is one face in M, Therefore L_f = R_f = (0.5*n + 1)/2 faces. Then
3*(L_f + M_f)-6 = 3*(((0.5*n + 1)/2) + 1) - 6, or
3*((0.5*n + 3)/2) - 6 for the left combo and
3*((0.5*n + 3)/2) - 6 for the right combo for a maximum number of edges of
3*(0.5*n +3) -12
1.5*n + 9 -12 = 1.5*n - 12 = maximum number of edges in dual.
The number of edges in a triangulated dual is 3*(F_c) - 6.
(F-c) = 0.5*n + 2.
E_t = 3*(0.5*n +2) - 6 = 1.5*n +6