Crossing-free Projections and Minimum Crossing Projections

Next: Monotonic Projections Up: Projections Previous: Regular Projections

Crossing-free Projections and Minimum Crossing Projections

Until now, we see that it is a goal for regular projections to keep all of the vertices and edges information. Simplicity, another requirement of effective visualization, can be measured by the number of crossings of edges in the projection. A projection with many crossings is more difficult to visualize than one with few crossings.

Definition: A projection is said crossing free if the number of crossings of edges in the projection is zero.

Definition: A projection that minimizes the number of crossings is called a minimum crossing projection.

Although a regular projection of a set of line segments always exists, we are not lucky to get a crossing-free projection all the time. Therefore, obtaining the minimum crossing projection is desirable in some applications. As showed below, the images of the veins of the same brain appear more or less clear depending on the direction of projection; but the second one has fewer number of crossings and looks clearer than the first one in some sense.

Jean HERBIERE and Yueyun SHU