
23.3. MATCHINGS 707
(a) after inserting c
i
(b) after rerouting c
i
and c
j
(c) after rerouting c
i
and c
j
0
Figure 23.7 Rerouting type-po leaders.
Proof: We first sort sites and ports such that s
1
, . . . , s
n
and p
1
, . . . , p
n
are indexed in
order of non-decreasing y-coordinates. For i = 1, . . . , n, we connect s
i
to p
i
by a po-leader c
i
that consists of a (possibly zero-length) vertical line segment incident to s
i
and a horizontal
line segment incident to p
i
. We assume that the previously placed leaders c
1
, . . . , c
i−1
are
pairwise disjoint, and we show that we can add c
i
such that this assumption ...