Next:
ND13 MAXIMUM DIRECTED
Up:
Cuts and Connectivity
Previous:
ND11 MAXIMUM CUT
-
I
NSTANCE
:
Directed graph
.
-
S
OLUTION
:
An embedding of
G
in the plane.
-
M
EASURE
:
The number of pairs of edges crossing one another.
-
Good News:
Approximable within 3 in the case of bipartite graphs [
95
].
-
Garey and Johnson:
OPEN3
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997