Information Technology Reference
In-Depth Information
C
i
C
i
D
i
e
j
C
i
q
i
1
2
m
C
i
C
i
q
i
v
1
(a)
(b)
(c)
Fig. 3.
Illustration of the drawing of exclusive internal edges
Note that we remove loops but not multiple edges. We will produce the largest part of
the drawing inside a grid of size 2deg(
v
1
)
2deg(
v
2
), which we position inside the
kernel of
f
. We distinguish the exclusive edges of
G
1
and
G
2
into two types. An ex-
clusive edgeis
internal
if its endpoint distinct from
v
1
and
v
2
belongs to one of the
C
i
for
i
=1
,...,c
. Otherwise the endpoint belongsto
C
and the edgeis
external
.
The vertices
v
1
and
v
2
are positioned below and left of the grid, respectively; see
Fig. 2a. By picking two external edges incident to
v
1
and
v
2
as the first edge, the circular
ordering around these vertices determine corresponding linear orderings. Second, for
each component
C
i
, we obtain a linear ordering of its incident internal edges by the
ordering around a point in the kernel of the outer face; see Fig.2b.Our goal is to
draw the edges as shown in Fig. 3b. Since the linear ordering around
v
1
and the linear
ordering determined by
C
i
do not necessarily coincide, this requires that component
C
i
is positioned at a specific position, namely slightly left of the so-called last edge, which
is shown bold in Fig. 3a and 3b. In this way, the ordering of the edges around
v
1
and
v
2
imply a certain ordering of the components
C
i
. Since these orderings generally differ,
we use the ordering around
v
1
to determine the
x
-coordinate and the ordering around
v
2
to determine the
y
-coordinate on the grid. Thus, each of the two vertices “sees” the
components in the expected ordering;seeFig.2c.
We now sketch how to draw the edges of
G
1
.Graph
G
2
is drawn analogously,
but with exchanged
x
-and
y
-coordinates, which corresponds to mirroring the draw-
ing along adiagonal. Let
e
0
,...,e
k
denote the internal edges incident to
v
1
linearly
ordered from left to right. Let
C
i
be a component incident to edge
e
j
.Wedrawedge
e
i
first from
v
1
to the grid point (2
j,
0), then vertically upwards uptosomeheight
y
(
e
j
),
then horizontally above the position of
C
i
(see Fig. 3b), and from there down to the
position of
C
i
and into its kernel. Finally, from there we route it to its endpoint in
C
i
(see Fig. 3c). The main point is the height
y
(
e
j
), which we choose such that
e
j
passes
above all components
C
i
whose
x
-coordinate lies between the
x
-coordinate of
e
j
, i.e.,
2
j
,andthe
x
-coordinate of the target component
C
i
;seeFig.3b.If
e
j
is an internal
edge, then we draw it from
v
1
to (2
j,
0) and from there vertically upwards throughthe
hole grid. It is then not hard to reach the target vertex of
C
with one or two more bends.
×
