Next:
ND58 MINIMUM LENGTH
Up:
Miscellaneous
Previous:
ND56 MINIMUM K-SWITCHING
-
I
NSTANCE
:
Directed planar graph
.
-
S
OLUTION
:
A planar orthogonal drawing of
G
, i.e., a drawing mapping vertices of
G
into
points in the plane and edges of
G
into chains of horizontal and vertical
segments such that no two edges cross.
-
M
EASURE
:
Number of bends in the drawing.
-
Bad News:
Not approximable within
for any
[
122
].
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997