Cualquiera

Grafo plano

Grafos de ejemplo |
Plano | No plano |
| K5 |
El grafo completo K4 es plano | K3,3 |
* |
Definición y ejemplos
En teoría de grafos, un grafo plano (o planar segúnreferencias) es un grafo que puede ser dibujado en el plano sin que ninguna arista se interseque (una definición más formal puede ser que este grafo pueda ser "embebido" en un plano). Un grafo no es planosi no puede ser dibujado sobre un plano sin que sus aristas se intersequen. Los grafos K5 y el K3,3 son los grafos no planos minimales, lo cual nos permitirán caracterizar el resto de los grafos noplanos.
Teorema de Kuratowski
El matemático polaco Kazimierz Kuratowski encontró una caracterización de los grafos planos, conocida como el teorema de Kuratowski:
Un grafo es plano si y solo si nocontiene un subgrafo que es una subdivisión elemental de K5 (el grafo completo de 5 vértices) o K3,3 (el grafo bipartito completo de 6 vértices).
Una subdivisión elemental de un grafo resulta deinsertar vértices en las aristas (por ejemplo, cambiando •——• por •—•—•). Una formulación equivalente a este teorema es:
Un grafo es plano sí y solo sí no contiene ningún subgrafo homeomorfo a K5 ó K3,3.Otros criterios para determinar si un grafo es plano
En la práctica, es difícil usar el teorema de Kuratowski para decidir rápidamente si un grafo es plano. Sin embargo, existe un algoritmo rápidopara este problema: dado un grafo de n vértices y e el número de aristas, es posible determinar en tiempo O(n) (lineal) si el grafo es plano o no, utilizando los dos teoremas siguientes:
Teorema 1. Sin ≥ 3 entonces e ≤ 3n - 6
Teorema 2. Si n > 3 y no existen ciclos de longitud 3, entonces e ≤ 2n - 4
El grafo K3,3, por ejemplo, tiene 6 vértices, 9 aristas y ningún ciclo de longitud 3. Por elteorema 2, no puede ser plano. Nótese que estos teoremas están construidos con una implicación unidireccional (si), y no bicondicional (si y solo si) y por tanto, solamente pueden ser usados para...