Graf planar

Grafuri de exemplificare
Planar	Neplanar
Graful fluture^⁠(d)	Graful complet K₅
Graful complet K₄	Graful utilitar^⁠(d) K_3,3

În teoria grafurilor, un graf planar este un graf care poate fi încorporat într-un plan, adică poate fi trasat în plan în așa fel încât muchiile sale să se intersecteze doar în noduri. Cu alte cuvinte, acesta poate fi desenat în așa fel încât oricare două muchii să nu se intersecteze.^[1] Un astfel de desen este numit un graf în plan sau o încorporare în plan a grafului. Un graf în plan poate fi definit ca un graf planar cu o funcție de corespondență de la fiecare nod la un punct din plan, și de la fiecare muchie la o curbă plană în planul respectiv, astfel încât punctele extreme ale fiecărei curbe să fie punctele corespunzătoare nodurilor de capăt, și ca toate curbele să fie disjuncte, cu excepția extremităților lor.

Toate grafurile care pot fi trasate într-un plan pot fi trasate și pe sferă, și vice-versa.

Grafurile planare pot fi codificate prin aplicații combinatorice^⁠(d).

Clasa de echivalență a reprezentărilor topologic echivalente de pe sferă se numește aplicație planară. Deși un graf planar are o față externă, sau nemărginită, niciuna dintre fețele unei aplicații planare nu are statut special.

Grafurile planare se pot generaliza la grafurile care pot fi desenate pe o suprafață de un anumit gen. În această terminologie, grafurile planare au genul^⁠(d) 0, deoarece planul (și sfera) sunt suprafețe de genul 0.

Note modificare

^ Trudeau, Richard J. (1993). Introduction to Graph Theory (ed. Corrected, enlarged republication.). New York: Dover Pub.. pp. 64. ISBN 978-0-486-67870-2. http://store.doverpublications.com/0486678709.html. Accesat la 8 august 2012. „Thus a planar graph, when drawn on a flat surface, either has no edge-crossings or can be redrawn without them.”

Referințe modificare

Kuratowski, Kazimierz (1930), „Sur le problème des courbes gauches en topologie” (în French), Fundamenta Mathematicae 15: 271–283, http://matwbn.icm.edu.pl/ksiazki/fm/fm15/fm15126.pdf
.
Wagner, K. (1937), „Über eine Eigenschaft der ebenen Komplexe”, Mathematische Annalen (în German), 114: 570–590, doi:10.1007/BF01594196 Mai multe valori specificate pentru |DOI= și |doi= (ajutor).
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^⁠(d), 8 (3): 241–273, doi:10.7155/jgaa.00091 Mai multe valori specificate pentru |DOI= și |doi= (ajutor).
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 (5): 1017–1029, doi:10.1142/S0129054106004248 Mai multe valori specificate pentru |DOI= și |doi= (ajutor). Ediție specială pe Grafic Desen.
D. A. Bader și S. Sreshta, Un Nou Algoritm Paralel pentru Planeitate de Testare Arhivat în 16 martie 2016, la Wayback Machine., UNM-ECE Raport Tehnic 03-002, octombrie 1, 2003.
Fisk, Steve (1978), „A short proof of Chvátal's watchman theorem”, Journal of Combinatorial Theory, Series B, 24 (3): 374, doi:10.1016/0095-8956(78)90059-X Mai multe valori specificate pentru |DOI= și |doi= (ajutor).

[1] Trudeau, Richard J. (1993). Introduction to Graph Theory (ed. Corrected, enlarged republication.). New York: Dover Pub.. pp. 64. ISBN 978-0-486-67870-2. http://store.doverpublications.com/0486678709.html. Accesat la 8 august 2012. „Thus a planar graph, when drawn on a flat surface, either has no edge-crossings or can be redrawn without them.”

[1]