Information Technology Reference
In-Depth Information
the complexity of HV-rectilinear planarity testing in the variable embedding setting for
general HV-graphs. We study these problems and establish the following results:
(
i
) HV-rectilinear planarity testing is NP-complete in the variable embedding setting
even for HV-graphs with vertex-degree at most three. We recall, for a contrast, that
Garg and Tamassia proved the NP-completeness of rectlinear planarity testing for planar
graphs of vertex-degreeatmostfour[11],but that rectlinear planarity testing can be
solved in linear time for planar graphs of vertex-degree at most three [16].
(
ii
) There exists a polynomial-time algorithm to test HV-rectilinear planarity for HV-
graphs that are partial 2-trees. In the affirmative case, the algorithm returns an HV-
realization of the graph. Recall that biconnected outerplanar graphs are a sub-family of
partial 2-trees, hence ourresult provides an algorithmic answer to the open problem of
Durocher
et al.
[9], even for graphs with maximum vertex-degree four.
The remainder of the paper is organized as follows. Section 2 proves that HV- rec-
tilinear planarity testing is NP-complete. Section 3 describes a polynomial-time algo-
rithm for HV-rectilinear planarity testing of series-parallel graphs, which is used as a
building-block for the design of an HV-rectilinear planarity testing algorithm for partial
2-trees presented in Sec. 4. Conclusions and open problems are in Sec. 5. For space
reasons several proofs are sketched.
2
NP-completeness of HV-rectilinear Planarity Testing
It is easy to see that HV-rectilinear planarity testing is in NP, since the problem is poly-
nomial when a planar embedding of the graph is given [9] and since all planar embed-
dings can be non-deterministically explored [1]. We show the hardness of this problem
even on instances of maximum vertex-degree three by reducing S
WITCH
F
LOW
N
ET
-
WORK
to it. Hence, the following theorem holds.
Theorem 1.
HV-rectilinearplanarity testing is NP-complete even for HV-graphsof
maximum vertex-degree three.
is an undirected graph where each edge
e
is labeled with
arange [
c
...c
] of nonnegative integers, called the
capacity range
of
e
. For simplicity,
the capacity range [
c...c
] is denoted with [
c
].A
flow
for a switch-flow network is an
orientation of its edges and an assignment of integer values to them. A flow is
feasible
if it satisfies the following two properties: (
i
) the total flow entering a vertex from the
incoming edges is equal to the total flow exiting the vertex from the outgoing edges,
and (
ii
) the flow assignedtoanedgeisaninteger within the capacity rangeoftheedge.
Given a switch-flow network
A
switch-flownetwork
N
N
,theS
WITCH
F
LOW
N
ETWORK
problem is the problem
of finding a feasible flow for
.
The S
WITCH
F
LOW
N
ETWORK
problem is trivially in NP, by assigning to the edges
all possible flow values and orientations and computing the sum of the flows at each
vertex. In [11] it is shown that S
WITCH
F
LOW
N
ETWORK
is NP-hardeveninavery
restrictive setting, that is, if its instances are such that: (
a
) the lower bounds of the
capacities ranges of the edges are either zero (as in [0
...c
])orequal to the upper bounds
(as in [
c
]), (
b
),edges with a proper capacity range(asin[0
...c
]) do not form a cut, and
N
