- 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