
102 CHAPTER 3. SYMMETRIC GRAPH DRAWING
To state the algorithm, we need some more terminology. We say that a vir tu al edge e of
skeleton(v) is a parent (child) virtual edge if e cor r es ponds to a virtual edge of u which is
a parent (resp. child) node of v. We define a parent separation pair s = (s
1
, s
2
) of v as the
two endpoints of a parent virt ual edge e.
The overall algorithm is composed of three steps.
Algorithm MAX
PAG bicon
Step 1. Construct the SPQR-t r ee T of G.
Step 2. Reduction: For each level i of T (from the lowest level to the root level)
(a) For each leaf node on level i, compute labels on the parent virtual edge in
the leaf node.
(b)