Quasiplanarity

Quasiplanarity is a concept in graph drawing and computational geometry that describes a relaxation of planarity. A drawing of a graph in the plane is called quasi-planar if it contains no three edges that pairwise cross each other. In other words, there is no triple of edges such that every pair among the three crosses. Equivalently, the set of edges can be viewed as a crossing graph with vertices representing edges and edges representing crossings, and this crossing graph has no triangle.

A graph is said to be quasi-planar if it admits such a drawing. Quasiplanarity sits between planarity and more general nonplanar drawings: every planar graph is quasi-planar, but a quasi-planar graph need not be planar since some edge crossings are allowed, just not the triplewise-crossing configuration.

In most studies, the focus is on simple quasi-planar graphs, meaning drawings where edges cross at most once and there are no loops or multiple edges. A central result concerns the maximum possible number of edges in an n-vertex simple quasi-planar graph. It is known that this maximum is Theta(n log n): there exist constructions with on the order of n log n edges, and the best known upper bounds also grow on the order of n log n. This makes quasi-planar graphs a natural intermediate class between planar graphs (O(n)) and general nonplanar graphs.

Quasiplanarity has been investigated for theoretical reasons related to crossing patterns, as well as for practical applications in graph drawing, visualization, and geometric graphs. Related concepts include planar graphs, crossing numbers, and topological graph theory.

See also: planar graph, crossing number, topological graph, graph drawing.