Un grafo es planar si puede dibujarse en un plano sin que sus aristas se crucen. La planaridad depende de la estructura del grafo, no de un dibujo particular.
Cuando dibujamos un grafo con muchas conexiones, las aristas pueden cruzarse y dificultar su lectura. A veces los cruces desaparecen al mover los vértices; otras veces son inevitables.
La teoría de grafos distingue entre el grafo abstracto y su representación visual. Un grafo es planar si existe al menos una forma de dibujarlo sin cruces entre aristas que no comparten vértices.
Un grafo es planar cuando puede representarse en el plano de modo que las aristas solo se encuentren en sus extremos comunes.
No es necesario que todos sus dibujos estén libres de cruces. Basta con que exista una representación adecuada.
Conviene diferenciar dos conceptos relacionados:
| Concepto | Significado |
|---|---|
| Grafo planar | Grafo que admite alguna representación sin cruces |
| Dibujo plano | Una representación concreta del grafo que no tiene cruces |
K4 puede dibujarse como un cuadrado con diagonales que se cruzan, pero sigue siendo planar porque podemos colocar uno de sus vértices dentro del triángulo formado por los otros tres.
Un dibujo plano divide el plano en regiones denominadas caras. También se cuenta como cara la región exterior que rodea todo el dibujo.
La cantidad de caras depende de la estructura y se relaciona con el número de vértices y aristas mediante la fórmula de Euler.
Elige un grafo y arrastra sus vértices. La aplicación cuenta cruces entre aristas que no comparten extremos. Intenta convertir el dibujo inicial de K₄ en un dibujo plano.
Las aristas que participan en un cruce aparecen en color rosa. En K₅ y K₃,₃ puedes reducir la cantidad, pero nunca conseguir cero cruces: ambos grafos son no planares.
Para todo grafo plano, conectado y finito se cumple una relación entre vértices, aristas y caras.
En un dibujo plano de K4 hay 4 vértices, 6 aristas y 4 caras: 4 − 6 + 4 = 2.
La fórmula de Euler permite deducir que un grafo planar simple y conectado con al menos tres vértices cumple:
Esta desigualdad es una condición necesaria, pero no suficiente: cumplirla no garantiza por sí solo que el grafo sea planar.
Dos grafos tienen un papel central en el estudio de la planaridad.
| Grafo | Estructura | Motivo de interés |
|---|---|---|
| K5 | Cinco vértices completamente conectados | No puede dibujarse sin cruces |
| K3,3 | Bipartito completo con dos grupos de tres | No puede dibujarse sin cruces |
El teorema de Kuratowski caracteriza los grafos no planares mediante subdivisiones de estas dos estructuras.
Para analizar un dibujo podemos comprobar si dos segmentos se intersectan. Las aristas que comparten un vértice no se cuentan como cruce.
function orientacion(a, b, c) {
return (b.x - a.x) * (c.y - a.y) -
(b.y - a.y) * (c.x - a.x);
}
function seCruzan(a, b, c, d) {
const o1 = orientacion(a, b, c);
const o2 = orientacion(a, b, d);
const o3 = orientacion(c, d, a);
const o4 = orientacion(c, d, b);
return o1 * o2 < 0 && o3 * o4 < 0;
}
console.log(seCruzan(
{ x: 0, y: 0 }, { x: 10, y: 10 },
{ x: 0, y: 10 }, { x: 10, y: 0 }
));Podemos implementar la condición |E| ≤ 3|V| − 6 como un descarte rápido para grafos simples.
function superaLimitePlanar(vertices, aristas) {
if (vertices < 3) return false;
return aristas > 3 * vertices - 6;
}
console.log("K5 supera el límite:", superaLimitePlanar(5, 10));
console.log("K4 supera el límite:", superaLimitePlanar(4, 6));K5 supera el límite y por eso no es planar. K3,3 no lo supera, lo que demuestra que la desigualdad no basta para confirmar planaridad.
| Área | Uso | Beneficio |
|---|---|---|
| Diseño de circuitos | Reducir cruces entre conexiones | Simplificar fabricación |
| Cartografía | Representar regiones vecinas | Analizar coloración de mapas |
| Visualización | Ordenar diagramas de relaciones | Mejorar legibilidad |
| Redes e infraestructura | Planificar conexiones sobre superficies | Reducir interferencias |
La planaridad muestra que la estructura de un grafo impone límites sobre la forma en que puede representarse. Mover vértices puede eliminar cruces accidentales, pero no los cruces inevitables de grafos como K5 y K3,3.
En el próximo tema comenzaremos a estudiar cómo almacenar grafos en un programa mediante listas de adyacencia.