Planeitatea

Planeitatea, or planarity, is the property of an object or a graph to be drawn in the plane without crossings. In geometry, a figure is planar if all its points lie in a single plane. In graph theory, a graph is planar if it can be embedded in the plane so that its edges intersect only at their endpoints.

A finite graph is planar if and only if it does not contain a subgraph that is homeomorphic to K5 (the complete graph on five vertices) or K3,3 (the complete bipartite graph with three vertices in each part). This characterization, known as Kuratowski’s theorem, provides a fundamental criterion for non-planarity. For connected planar graphs, Euler’s formula holds: V − E + F = 2, where V is the number of vertices, E the number of edges, and F the number of faces in a planar embedding. From this formula, simple planar graphs satisfy E ≤ 3V − 6 for V ≥ 3; equality occurs in triangulations, where every face is a triangle. For bipartite planar graphs, a sharper bound is E ≤ 2V − 4 for V ≥ 3.

Planarity testing and embedding are well-developed areas in computer science. There exist linear-time algorithms to determine planarity and to produce a planar embedding, notably the Hopcroft–Tarjan algorithm; more recent practical implementations include algorithms by Boyer and Myrvold.

Examples of planar graphs include trees, cycles, and many small graphs, while K5 and K3,3 are classic minimal nonplanar graphs. Planarity has applications in graph drawing, circuit design (VLSI), geographic information systems, and network visualization, where a crossing-free representation improves readability and interpretability.