síkosságát

Planarity, or “síkosság” in Hungarian, is a property of graphs indicating that the graph can be embedded in the Euclidean plane or on a two‑dimensional surface without any edges crossing. An embedding that satisfies this condition is called a planar drawing. The concept originated in the early 20th century with the pioneering work of Johann Karl Kuratowski, who proved that a finite graph is planar if and only if it contains no subgraph that is a subdivision of either the complete graph K₅ or the complete bipartite graph K₃,₃. This result, known as Kuratowski’s theorem, provides a purely structural characterization of planarity. A related but more algorithmic criterion is given by Wagner’s theorem, which states that a graph is planar if and only if it has no minor isomorphic to K₅ or K₃,₃.

Planarity has early roots in cartography and map coloring problems, where the four‑color theorem, proved in 1976, settled the question of how many colors are needed to color any planar map so that adjacent regions receive different colors. Algorithms for testing planarity and producing planar embeddings were developed in the 1960s and have since been refined to linear‑time complexity. The SPQR‑tree data structure, introduced in 1994, allows dynamic manipulation of planar graphs and supports efficient operations such as adding or removing edges while maintaining planarity.

In computer science, planarity underpins many efficient algorithms for planar graphs, including linear‑time shortest path, maximum flow, and minimum cut computations that would otherwise be more complex on general graphs. The property also informs graphical user interface layout, VLSI circuit design, and network visualization, where edge crossings are undesirable. In pure mathematics, planarity interacts with topological graph theory and algebraic topology, extending concepts to surfaces of higher genus and leading to the study of graph embeddings on orientable and non‑orientable surfaces.