Next: MAXIMUM DIRECTED CUT Up: Cuts and Connectivity Previous: MAXIMUM CUT Index

### MINIMUM CROSSING NUMBER

- 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 V1 and V2 must lie on two parallel lines and each edge corresponds to a straight line segment, is approximable within 3 [131].

- Garey and Johnson: OPEN3