
310 CHAPTER 9. CIRCULAR DRAWING ALGORITHMS
Figure 9.30 A DFS tree with the edges of the longest path d es ignate d by thick lines.
Figure taken from [ST99, ST06].
embedding circle. As noted in the time complexity analysis of Algorit h m CIRCULAR-
Postprocessing, the order is dominated by the time required for counting the number of
crossings. Therefore, it is vitally important to the time efficiency of th e implementation of
this algorithm that the number of crossings be counted in an effective manner. In order to
lower t he average time cost of counting cross in gs in the drawing, we ignore all edges that
lie on the periphery of the embed d ing circle. ...