Grafo plano

Grafos de ejemplo
Plano No plano
6n-graf.svg
K5
El grafo completo K4 es plano
K3,3

En teoría de grafos, un grafo plano (o planar según referencias) es un grafo que puede ser dibujado en el plano sin que ninguna arista se cruce (una definición más formal puede ser que este grafo pueda ser "incrustado" en un plano). Los grafos K5 y el K3,3 son los grafos no planos minimales, lo cual nos permitirán caracterizar el resto de los grafos no planos.

Todo grafo plano puede ser dibujado sobre la esfera, y viceversa. Una generalización de los grafos planos son grafos dibujados e incrustados sobre superficies de genero arbitrario. En esta terminología, los grafos planos tienen genero 0, por ser el plano y la esfera de género 0

Teorema de Kuratowski

El matemático polaco Kazimierz Kuratowski encontró una caracterización de los grafos planos, conocida como el teorema de Kuratowski:[1]

Teorema de Kuratowski

Un grafo es plano si y solo si no contiene un subgrafo isomorfo a una subdivisión elemental de K5 (el grafo completo de 5 vértices) o K3,3 (el grafo bipartito completo de 6 vértices).


Kuratowski (1930)

Una subdivisión elemental de un grafo resulta de insertar vértices en las aristas (por ejemplo, cambiando •——• por •—•—•). Una formulación equivalente a este teorema es:

Un grafo es plano si y solo si no contiene ningún subgrafo homeomorfo a K5 ó K3,3

Other Languages
العربية: مخطط مستو
català: Graf pla
čeština: Rovinný graf
English: Planar graph
فارسی: گراف مسطح
français: Graphe planaire
italiano: Grafo planare
日本語: 平面グラフ
한국어: 평면 그래프
latviešu: Planārs grafs
norsk nynorsk: Planar graf
português: Grafo planar
slovenčina: Rovinný graf
slovenščina: Ravninski graf
српски / srpski: Planarni grafovi
svenska: Planär graf
українська: Планарний граф
Tiếng Việt: Đồ thị phẳng