Information Technology Reference
In-Depth Information
[0]
[0]
[0]
[0]
[0]
[0]
E
E
E
[0]
[0]
[1]
[1]
[1]
[1]
[1]
[1]
F
D
F
F
D
[0]
[0]
D
[0]
[0]
[0]
[1]
[1]
B
[1]
B
B
[1]
[1]
[1]
[1]
[1]
[1]
G
G
[0..2]
[1]
[0]
G
[0..2]
[1]
[0..2]
[1]
[0]
A
C
A
C
A
C
[0]
[1]
[0]
[0]
[1]
[1]
(a)
(b)
(c)
Fig. 2.
(a) A feasible flow for an instance
N
of the S
WITCH
F
LOW
N
ETWORK
problem; the
instance is the underlyingundirected graph. The thick arrow represents a flow of two units while
the thinner arrows represent flows of one unit. (b) The maximal planar S
WITCH
F
LOW
N
ETWORK
instance
N
∗
obtained from
N
.(b)Graph
N
∗
and its dual
D
.
(
c
) the network is planar. Starting from an instance
of the S
WITCH
F
LOW
N
ETWORK
problem satisfyingProperties (
a
), (
b
),and(
c
),wecreateaninstance
G
of HV-planarity
testing of maximumdegree three as follows (refer to Figs2and3):
Step 1.
Construct a maximal planar instance
N
N
∗
by inserting dummy edges with ca-
N
∗
admits a feasible flow if and only if
pacity range [0] into
N
. Observe that
N
does.
N
∗
is a maximal
triconnected graph, each vertex of
D
has degree three and
D
is also triconnected. We
label the edges of
D
with the capacity range of the corresponding edgeof
N
∗
. Observe that, since
Step 2.
Compute the dual plane graph
D
of
N
∗
.
Step 3.
Compute an orthogonal drawing
ʓ
D
of
D
with the linear-time algorithm in [17].
This algorithm takes as input a 4-plane biconnected graph and computes a drawing with
at most 2
n
+4bends and such that each edge has at least one vertical segment.
Step 4.
Transform
ʓ
D
into a positive instance
F
of HV-planarity testing by replacing
orthogonal and vertical segments with rectangular boxes and by labeling each horizontal
and vertical edgeof
F
with labels H and V, respectively (see also Fig. 3(b)). Note that
F
has maximum vertex-degree three and, as
D
is triconnected, it has a uniqueHV-
realization
H
F
up to horizontal and vertical flips.
Step 5.
Build the instance
G
of HV-planarity testing. First, identify for each edge
e
of
D
with a label different from [0] a rectangular box of
F
corresponding to a vertical
segment of
ʓ
D
. If the label of
e
is [
c
], insert the HV-graph
T
c
, called
tendril
,inthe
rectangular box, attaching it with two edges
e
and
e
called the
handles
of the tendril.
See Fig 3(d) and 3(e) for
T
1
and
T
2
.If
e
is labeled [0
...c
] insert into the rectangular box
the HV-graph
W
c
, called
wiggle
.Wiggles
W
1
and
W
2
are shown in Figs. 3(f) and 3(g).
Lemma 1.
An HV-realization of theHV-graph
G
corresponds to a feasible flow of the
switchnetwork
N
and vice versa.
Proof sketch:
First, we show that, starting from an HV-realization
H
G
of
G
, a feasi-
ble flow for
N
can be found. Observe that each tendril
T
h
necessarily has the HV-
realization
H
T
h
or
H
T
h
, giving to its left and right faces
f
l
and
f
r
, 4
h
and
−
4
h
(or
