Information Technology Reference
In-Depth Information
On the Complexity of HV-rectilinear Planarity Testing
Walter Didimo
1
,Giuseppe Liotta
1
,andMaurizio Patrignani
2
1
Dept. of Engineering, University of Perugia, Italy
2
Dept. of Engineering, Roma Tre University, Italy
Abstract.
An HV-restricted planar graph
G
is a planar graph with vertex-degree
at most fourandsuch that each edge is labeled either H (horizontal) or V (verti-
cal). The
HV-rectilinearplanarity testing
problem asks whether
G
admits a pla-
nar drawing where every edge labeled V is drawn as a vertical segment and every
edge labeled H is drawn as a horizontal segment. We prove that HV-rectilinear
planarity testing is NP-complete even for graphs having vertex degree at most
three, which solves an open problem posed by both Manuch
et al.
(
GD 2010
)and
Durucher
et al.
(
LATIN 2014
). We also show that HV-rectilinear planarity can
be tested in polynomial time for partial 2-trees of maximumdegree four, which
extends a previousresult by Durucher
et al.
(
LATIN 2014
)about HV-restricted
planarity testing of biconnected outerplanar graphs of maximumdegree three.
When the test is positive, ouralgorithm returns an orthogonal representation of
G
that satisfies the given H- and V-labels on the edges.
1
Introduction
Let
G
=(
V,E
) beaplanargraph with vertex-degree at most four. A
rectilinearorthog-
onaldrawing
ʓ
of
G
is a planar drawing of
G
where each vertex
v
∈
V
corresponds to
a distinct point
p
v
of the plane and each edge (
u,v
)
E
corresponds to a horizontal or
vertical segment between
p
u
and
p
v
.If
G
is a planar embedded graph, i.e., a graph with
a given planar embedding (a planar embedding defines for each vertex
v
∈
V
the cir-
cular order of the edges incident to
v
and it also specifies the external face), we assume
that a rectilinear orthogonal drawing of
G
preserves its embedding.If
v
is a vertex of a
planar embedded graph and if
e
1
and
e
2
are two (possibly coincident) edges of
v
that
are consecutive in the clockwise order around
v
, we say that
a
=
∈
is an
angle
at
v
of
G
or simply an
angle
of
G
. Two rectilinear orthogonal drawings
ʓ
and
ʓ
of
the same planar embedded graph
G
are
shape equivalent
if for any angle
a
of
G
,the
geometric angle corresponding to
a
is the same in
ʓ
and
ʓ
.A
rectilinearorthogonal
representation
e
1
,v,e
2
of a planar embedded graph
G
is a class of shape equivalent rectilinear
orthogonal drawingsof
G
;
H
can be described by the embedding of
G
equipped with a
label for each angle of
G
; the labels for an angle can be
R
,
F
,
L
,or
LL
, corresponding
to a geometric angle of 90, 180, 270, and 360 degrees, respectively.
The
rectilinearplanarity testing
problem asks whether a planar graph
G
with vertex-
degree at most four admits a rectilinear orthogonal drawing (or equivalently, a rectilin-
ear orthogonal representation). The problem can be solved in polynomial time in the
H
This research is supported in part by the Italian Ministry of Education, University, and Re-
search (MIUR) under PRIN 2012C4E3KT national research project “AMANDA - Algorith-
mics for MAssive and Networked DAta”
