crossingfree

Crossingfree is an adjective used in geometry and graph drawing to describe a representation in which no two curves or line segments intersect except possibly at common endpoints. In the plane, a drawing of a graph is crossingfree if its edges meet only at shared vertices and otherwise do not cross. A graph is described as crossingfree when it admits such a drawing.

In graph theory, a crossing-free drawing is a planar embedding; the graph is planar if and only if it has a crossing-free drawing in the plane.

Key results: Fary's theorem states that every planar graph can be drawn with straight-line edges without crossings, confirming that the class of crossingfree drawings is exactly the class of planar graphs when straight segments are allowed. Conversely, if a graph is non-planar, every drawing must contain at least one crossing.

Planarity testing: Determining if a given graph is crossingfree is done by planarity testing algorithms, such as the Hopcroft-Tarjan linear-time planarity test and subsequent improvements.

Applications: crossingfree representations are important in network visualization, circuit layout (VLSI), cartography, and geometric data visualization, where minimizing crossings improves readability and manufacturability.

See also: planar graph, crossing number, straight-line drawing, planarity testing.