neplanárnost

Neplanárnost, also known as non-planarity, is a concept in graph theory, a branch of mathematics. It refers to the property of a graph that cannot be drawn on a plane without any edges crossing. A graph is planar if it can be represented as a drawing in the plane such that no edges intersect except at their endpoints. This concept is fundamental in understanding the structure and properties of graphs.

The study of planarity began with the Four Color Theorem, which states that any map can be colored with no more than four colors such that no two adjacent regions share the same color. This theorem is closely related to the concept of planarity, as it involves the arrangement of regions on a plane.

Kuratowski's Theorem provides a characterization of planar graphs. It states that a graph is non-planar if and only if it contains a subgraph that is homeomorphic to either K5 (the complete graph on five vertices) or K3,3 (the complete bipartite graph on six vertices, with three vertices on each side). This theorem offers a practical way to determine the non-planarity of a graph.

Non-planarity has applications in various fields, including computer science, where it is used in algorithms for graph drawing and network layout. Understanding non-planarity helps in designing efficient algorithms and optimizing the layout of networks and data structures.