
18.3. GRAPH-CLASSES AND THEIR HIERARCHY 581
(a) (b)
Figure 18.9 (a) Drawing dug1 and (b) drawing dug2, computed with the code of Fig-
ure 18.8. The two drawings have the same shape but different geometry. The drawing in
(b) is much more compact, both in terms of area and in terms of total edge length.
drawings in Figures 18.10 (a)-(b) are obtained by executing a linear-time drawing algorithm,
while the drawings in Figures 18.10 (c)-(d) are obtained by applying an O(n
2
log n)-time
compaction algorithm that reduces the total edge length.
(a) (b) (c) (d)
Figure 18.10 Two visibility drawings and two polyline drawings of the same embedded
planar graph. The