knearplanar

k-near-planar is a concept in graph drawing describing graphs that are close to planar. A graph G is k-near-planar if there exists a subset F of at most k edges such that removing those edges yields a planar graph on the same vertex set. In other words, G can be drawn in the plane so that it becomes planar after deleting no more than k edges. For k = 0 this reduces to the class of planar graphs, and for k = 1 the graphs are often referred to as almost planar.

Key properties

- Edge bound: If G has n vertices (n ≥ 3) and is k-near-planar, then |E(G)| ≤ 3n − 6 + k, since removing F yields a planar graph with at most 3n − 6 edges.

- Construction: Starting from a planar graph on n vertices, adding up to k edges yields a k-near-planar graph. The chosen k edges form a set whose removal restores planarity.

- Non-uniqueness: A given graph may be k-near-planar with different choices of the edge set F, and the same graph could be k-near-planar for different values of k.

- Relationships: k-near-planar is distinct from k-planar graphs (which constrain edge crossings per edge) and from almost planar graphs in more restrictive senses. It focuses on edge deletions needed to attain planarity rather than per-edge crossing counts.

Scope and applications

The notion is studied in graph drawing and algorithmic contexts, where researchers investigate recognition problems, structural properties, and how near-planarity affects visualization and layout algorithms. It provides a framework for measuring how far a graph is from planarity in terms of edge deletions rather than crossings per edge.

See also

Planar graphs, almost planar graphs, k-planar graphs, crossing number.