Next: MAXIMUM DIRECTED CUT
Up: Cuts and Connectivity
Previous: MAXIMUM CUT
  Index
- INSTANCE:
Directed graph
.
- SOLUTION:
An embedding of G in the plane.
- MEASURE:
The number of pairs of edges crossing one another.
- Comment:
Variation in which
is a bipartite graph and
the objective is to minimize the bipartite crossing number, that is
the number of edge crossings in the embedding where the vertices in
and
must lie on two parallel lines and each edge corresponds
to a straight line segment, is approximable within 3
[141].
- Garey and Johnson: OPEN3
Viggo Kann
2000-03-20