edgecrossing

Edge crossing, also written edgecrossing, is the intersection point formed by two edges of a graph drawing when the edges meet at a point not corresponding to a shared endpoint. In a planar drawing, no two edges cross; many graphs require crossings to be represented in the plane.

The minimum possible number of edge crossings across all drawings of a given graph is called the crossing number. A graph is planar if its crossing number is zero. Determining planarity can be done by algorithms, while computing the exact crossing number is computationally hard (NP-hard) for general graphs. Exact values are known for some small graphs; for larger graphs, researchers rely on bounds, heuristics, and approximation methods.

In practice, edge crossings affect readability in graph visualization and influence circuit layout in VLSI design and network design. Several approaches exist to reduce crossings: force-directed layouts attempt to spread vertices and minimize crossings; layered and orthogonal drawings use constraints to reduce or control crossings; planarization methods insert dummy vertices and later re-route edges to lower the crossing count. Rectilinear crossing numbers consider drawings with straight-line edges and lead to different optimization problems.

This is a neutral description; no single best solution exists for all graphs. The study of edge crossing intersects graph theory, computational geometry, and visualization, with implications for theory and practical applications.