Grafo plano

Grafos de exemplo
Plano	Non plano
Grafo de bolboretas	Grafo completo K₅
Grafo completo K₄	Grafo de utilidade K_3,3

Na teoría de grafos, un grafo plano é un grafo que se pode mergullar no plano, é dicir, pódese debuxar no plano de forma que as súas arestas se corten só nos seus extremos.

Noutras palabras, pódese debuxar de forma que ningúnha aresta se cruce.^[1]^[2]

Todo grafo que se poida debuxar nun plano tamén se pode debuxar na esfera, e viceversa, mediante proxección estereográfica.

Os grafos planos pódense codificar mediante mapas combinatorios ou sistemas de rotación.

Os grafos planos xeneralízanse como grafos que se poden debuxar nunha superficie dun genus determinado. Nesta terminoloxía, os grafos planos teñen genus 0, xa que o plano (e a esfera) son superficies de genus 0. Consulte "mergullo de grafos" para outros temas relacionados.

Criterios para ser plano

Teoremas de Kuratowski e Wagner

O matemático polaco Kazimierz Kuratowski proporcionou unha caracterización dos grafos planos en termos de grafos prohibidos, agora coñecido como teorema de Kuratowski:

Un grafo finito é plano se e só se non contén un subgrafo que sexa unha subdivisión do grafo completo

K 5

ou do grafo bipartito completo

K 3,3

(grafo de utilidade).

Unha subdivisión dun grafo resulta de inserir vértices nas arestas (por exemplo, mudar unha aresta • —— • a • — • — • ) cero ou máis veces.

En lugar de considerar as subdivisións, o teorema de Wagner trata dos menores:

Un grafo finito é plano se e só se non ten

K 5

ou

K 3,3

como menor.

Un menor dun grafo resulta de tomar un subgrafo e contraer repetidamente unha aresta nun vértice, con cada veciño dos vértices finais orixinais converténdose nun veciño do novo vértice.

Unha animación que mostra que o grafo de Petersen contén un grafo menor isomorfo ao grafo $K 3,3$ e, polo tanto, non é plano.

Klaus Wagner preguntou de xeito máis xeral se algunha clase de grafos pechados menores está determinada por un conxunto finito de "menores prohibidos". Este é agora o teorema de Robertson-Seymour, demostrado nunha longa serie de artigos. Na linguaxe deste teorema, $K 5$ e $K 3,3$ son os menores prohibidos para a clase de grafos planos finitos.

Propiedades

Fórmula de Euler

A característica de Euler indica que se se debuxa no plano un grafo plano, conexo e finito sen ningunha intersección de arestas, e $v$ é o número de vértices, $e$ é o número de arestas e $f$ é o número de caras (rexións limitadas por arestas, incluída a rexión exterior infinitamente grande), entón

v-e+f=2.

A modo de ilustración, no grafo de bolboreta mostrado na primeira figura, $v = 5$ , $e = 6$ e $f = 3$ (5-6+3=2).

Nun grafo finito, conexo, simple e plano, calquera cara (excepto posibelmente a exterior) está limitada por polo menos tres arestas e cada aresta toca como máximo dúas caras, polo que $3 f <= 2 e$ ; usando a fórmula de Euler, pódese mostrar que estes grafos son escasos no sentido de que se $v \geq 3$ :

e\leq 3v-6.

Grao medio

Os grafos planos conexos con máis dunha aresta obedecen á desigualdade $2 e \geq 3 f$ , porque cada cara ten polo menos tres incidencias cara-aresta e cada aresta aporta exactamente dúas incidencias. Dedúcese mediante transformacións alxébricas desta desigualdade coa fórmula de Euler $v - e + f = 2$ que para os grafos planos finitos o grao medio é estritamente inferior a 6. Os grafos con grao medio máis alto non poden ser planos.

Grafos de moedas

Dicimos que dous círculos debuxados nun plano se bican (ou osculan) sempre que coinciden nun único punto. Un "grafo de moedas" é un grafo formado por un conxunto de círculos, dos que non hai dous interiores superpostos, facendo un vértice para cada círculo e unha aresta para cada par de círculos que se bican. O teorema de empaquetamento circular, probado por primeira vez por Paul Koebe en 1936, afirma que un grafo é plano se e só se é un grafo de moedas.

Densidade do grafo plano

O coeficiente de retícula ou densidade $D$ dun grafo plano, ou rede, é a relación entre o número $f - 1$ de caras limitadas (o mesmo que o rango do circuíto do grafo, segundo o criterio de grafo plano de Mac Lane ) polos seus valores máximos posíbeis $2 v - 5$ para un grafo con $v$ vértices:

D={\frac {f-1}{2v-5}}

A densidade obedece $0 \leq D \leq 1$ , con $D = 0$ para un grafo plano completamente escaso (unha árbore) e $D = 1$ para un grafo plano completamente denso (máximal).

Grafo dual

Dado un mergullo $G$ dun grafo conexo (non necesariamente simple) no plano sen interseccións de arestas, construímos o grafo dual $G*$ do seguinte xeito: escollemos un vértice en cada cara de $G$ (incluída a cara exterior) e para cada aresta $e$ en $G$ introducimos unha nova aresta en $G*$ que une os dous vértices en $G*$ correspondentes ás dúas caras de $G$ que se atopan en $e$ en G.

A maiores, esta aresta debúxase de xeito que atravese $e$ exactamente unha vez e que non corte ningunha outra aresta de $G$ ou $G*$ . Daquela $G*$ é de novo un mergullo dun grafo plano (non necesariamente simple); ten tantas arestas como $G$ , tantos vértices como $G$ teña caras e tantas caras como $G$ teña vértices.

O termo "dual" xustifícase polo feito de que $G ** = G$ ; aquí a igualdade é a equivalencia de mergullos na esfera. Se $G$ é o grafo plano correspondente a un poliedro convexo, entón $G*$ é o grafo plano correspondente ao poliedro dual.

Aínda que o dual construído para un mergullo particular é único (ata isomorfismo), os grafos poden ter diferentes duais (é dicir, non isomorfos), obtidos a partir de diferentes mergullos (é dicir, non homeomorfos).

Notas

↑ Trudeau, Richard J. (1993). Introduction to Graph Theory (Corrected, enlarged republication. ed.). New York: Dover Pub. p. 64. ISBN 978-0-486-67870-2. Consultado o 8 agosto 2012.
↑ Barthelemy, M. (2017). "1.5 Planar Graphs". Morphogenesis of Spatial Networks. Springer. p. 6. ISBN 978-3-319-20565-6.

Véxase tamén

Bibliografía

Kuratowski, Kazimierz (1930). Sur le problème des courbes gauches en topologie (PDF). Fundamenta Mathematicae (en francés) 15. pp. 271–283. doi:10.4064/fm-15-1-271-283.
Wagner, K. (1937). Über eine Eigenschaft der ebenen Komplexe. Mathematische Annalen (en alemán) 114. pp. 570–590. doi:10.1007/BF01594196.
Boyer, John M.; Myrvold, Wendy J. (2005). On the cutting edge: Simplified O(n) planarity by edge addition (PDF). Journal of Graph Algorithms and Applications 8. pp. 241–273. doi:10.7155/jgaa.00091.
McKay, Brendan; Brinkmann, Gunnar. A useful planar graph generator.
de Fraysseix, H.; Ossona de Mendez, P.; Rosenstiehl, P. (2006). Trémaux trees and planarity. International Journal of Foundations of Computer Science 17. pp. 1017–1029. arXiv:math/0610935. doi:10.1142/S0129054106004248. Special Issue on Graph Drawing
Bader, D.A.; Sreshta, S. (October 1, 2003). "A New Parallel Algorithm for Planarity Testing". UNM-ECE Technical Report 03-002. Arquivado dende o orixinal o 2016-03-16.
Fisk, Steve (1978). A short proof of Chvátal's watchman theorem. Journal of Combinatorial Theory, Series B 24. p. 374. doi:10.1016/0095-8956(78)90059-X.

Outros artigos

Ligazóns externas

Edge Addition Planarity Algorithm Source Code, version 1.0 contén Edge Addition Planarity Algorithms, current version.
Public Implementation of a Graph Algorithm Library and Editor, GPL biblioteca de algoritmos de grafos que inclúe probas de grafos planos, megullador de grafos planos e exposición de subgrafos de Kuratowski en tempo linear.
Boost Graph Library tools for planar graphs, similar á anterior.
3 Utilidades de Puzzle e Grafos planos
NetLogo Planarity model, NetLogo versión do xogo de John Tantalo

[1] Trudeau, Richard J. (1993). Introduction to Graph Theory (Corrected, enlarged republication. ed.). New York: Dover Pub. p. 64. ISBN 978-0-486-67870-2. Consultado o 8 agosto 2012.

[2] Barthelemy, M. (2017). "1.5 Planar Graphs". Morphogenesis of Spatial Networks. Springer. p. 6. ISBN 978-3-319-20565-6.

[1]

[2]