Back بيان مستو Arabic Rovinný graf Czech Planarer Graph German Planar graph English Grafo plano Spanish Tasandiline graaf Estonian Grafo lau Basque گراف مسطح Persian Graphe planaire French גרף מישורי HE
| Exemples de grafs | |
|---|---|
| Planar | No planar |
 |
 |
 |
 |
En teoria de grafs, un graf pla o planar és un graf que pot ser dibuixat en un pla sense que les arestes s'intersequin (o utilitzant una definició més formal, que aquest graf pugui ser "embegut" en un pla).[1][2] Un graf no és pla si no pot ser dibuixat sobre un pla sense que les seves arestes s'intersequin. Hi ha dos grafs no plans minimals; K₅ i K3,3. Tots els grafs no plans contenen almenys un d'aquests subgrafs minimals.
En canvi, el graf complet K₄ és pla, perquè pot ser redibuixat sense que les arestes es creuin, passant una de les diagonals per l'exterior.
Per poder comprovar la planaritat d'un graf, primer s'ha d'adequar a una sèrie de criteris bàsics:
- El graf és connex. Si tenim un graf inconnex, podem considerar cada part com a graf connex independent.
- No té cap vèrtex de grau 1. Si conté vèrtexs de grau 1, per tant amb una sola aresta, aquests es poden eliminar de l'estructura sense risc a modificar-ne la planaritat.
- ↑ Dalfó, Cristina; Fiol, Miquel À. «Grafs, amics i coneguts». Butlletí de la Societat Catalana de Matemàtiques, 25, 1, 2010, pàg. 5-29. DOI: 10.2436/20.2002.01.25 [Consulta: 16 febrer 2020].
- ↑ de Fraysseix, H.; Pach, J.; Pollack, R. «How to draw a planar graph on a grid». Combinatorica, 10, 1990.