Next: MINIMUM LENGTH TRIANGULATION
Up: Miscellaneous
Previous: MINIMUM K-SWITCHING NETWORK
  Index
- INSTANCE:
Directed planar graph
.
- SOLUTION:
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.
- MEASURE:
Number of bends in the drawing.
- Bad News:
Not approximable within
for any
[183].
Viggo Kann
2000-03-20