Information Technology Reference
In-Depth Information
Case 3 (
v
k
is a nonprimary vertex in
T
l
but a primary vertex in
T
r
):
This case is symmetric to Case 2, i.e., we perform a 1-shift with respect to
h
to obtain a new grid point
p
on
D
(
w
l
) and assume that
q
=
C
(
w
r
).
Case 4 (
v
k
is a primary vertex in both
T
l
and
T
r
):
In this case we do
not perform any shift, and assume that
p
=
C
(
w
l
)and
q
=
C
(
w
r
).
We now have the following lemma whose proof is omitted due to space con-
straints.
Lemma 2.
ʓ
n
is a drawing on a
(
W
+2)
×
(
H
+2)
grid, where W
+
H
≤
leaf
(
T
l
)+
leaf
(
T
r
).
Phase 2 (Expansion):
For any plus-contact representation on an integer grid,
we define a
free grid line
as a grid line that does not contain any vertex-center
or contact points. We refer the reader to Figure 5.
Consider the horizontal grid lines from top to bottom. For every horizontal
grid line
containing at least one vertex of
ʓ
,wenowperformtwo
-
shifts, where
v
is the vertex with the largest degree over all the vertices on
.Let
h
(respectively,
h
) be an infinite horizontal line that lies in between the hori-
zontal grid line
and the horizontal grid line immediately below (respectively,
above)
.Performa
d
(
v
)
/
2
-shift
with respect to
h
. Observe that for each vertex
w
on
,wenowhaveasetof
d
(
v
)
/
2
-shift with respect to
h
,andthena
d
(
v
)
/
2
free grid lines below
w
.
We consider a corresponding set
S
w
that consists of these 2
d
(
v
)
/
2
free grid lines above
w
and a set of
d
(
v
)
/
2
free grid
lines along with the line
. Furthermore, we assume that the grid lines of
S
w
are
ordered in the increasing order of
y
-coordinates. Figure 5(b) illustrates
S
v
4
.
Similarly, we consider the vertical grid lines from right to left, and for every
vertical grid line
containing at least one vertex of
ʓ
,weperformtwo
d
(
v
)
/
2
-
shifts to the left and right side of
,where
v
is the vertex with the largest degree
over all the vertices on
. We consider a corresponding set
S
w
that contains
these 2
d
(
v
)
/
2
free vertical grid lines along with the line
, where the lines are
ordered in the decreasing order of
x
-coordinates. Let the resulting drawing be
ʓ
n
,
as shown in Figure 5(c). The following property is a straightforward consequence
of the Expansion phase.
d
(
v
)
/
2
Remark 2.
For every vertex v in ʓ
n
,thepoint
C
(
v
)
lies at the center of an
integer grid A
v
of size
(2
+1)
.ThegridA
v
does
not contain any vertex, contact point, or edge of ʓ
except the four hands of v.
Furthermore, for any other vertex u
(
d
(
v
)
/
2
+1)
×
(2
d
(
v
)
/
2
=
v
)
,thegridsA
u
and A
v
are disjoint, i.e.,
they do not share any common grid point.
Phase 3 (Edge Routing):
For each vertex in canonical order, we first route
the incoming
m
-edges incident to
v
k
, as follows. Recall that the
m
-edges start
at the vertices
w
l
+1
,...,w
r−
1
and ends at
v
k
.
By the construction of
ʓ
n
, the vertices
w
l
+1
,...,w
r−
1
lie below
S
v
k
and to
the left of
S
v
k
. Hence all the boundary grid points of
A
v
k
, which lie below
S
v
k
and to the left of
S
v
k
, are visible from the top-right corner
c
w
j
of
A
w
j
, for all
l
+1
≤
j
≤
r
−
1. Assume that
z
=
d
m
(
v
)
/
2
.Let
M
be the monotone chain
