Pagina Radice del Progetto: Isomorfismo di grafi planari

Dati due grafi G ed H, determinare se essi siano isomorfi, ossia se essi siano lo stesso grafo a seguito di un'opportuna permutazione dei nodi, è un famigerato problema in teoria della complessità. Nel caso i due grafi siano planari, allora si può fare ed in tempo lineare!

Non conosco questo argomento, e quindi mi è difficile dare dei consigli precisi. Ciò presenta dei rischi e lo considero pertanto un progetto ambizioso, che non deve terminare necessariamente con la codifica di un algoritmo lineare nè che valga per tutti i grafi planari. Credo tuttavia possa essere un buon progetto, sopprattutto per chi voglia mettere della matematica in azione.

Hopcroft, J. E.; Wong, J. K.
Linear time algorithm for isomorphism of planar graphs: preliminary report.
Sixth Annual ACM Symposium on Theory of Computing (Seattle, Wash., 1974), pp. 172--184.
Assoc. Comput. Mach., New York, 1974.

Tale risultato è stato ottenuto raffinando il seguente lavoro:

Hopcroft, J. E.; Tarjan, R. E.
Isomorphism of planar graphs.
Complexity of computer computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N. Y., 1972), pp. 131--152, 187--212.
Plenum, New York, 1972.

Che a sua volta portava avanti il seguente risultato, sviluppato per grafi planari 3-connessi.

Hopcroft, J. E.; Tarjan, R. E.
A $V$ ${\rm log} V$ algorithm for isomorphism of triconnected planar graphs.
J. Comput. System Sci. 7 (1973), 323--331.

Il seguente articolo sembra sia stato scritto in modo meno affrettato e forse offre una visione più ampia. Però richiede una certa dimestichezza con l'algebra dei gruppi.

Colbourn, Charles J.; Booth, Kellogg S.
Linear time automorphism algorithms for trees, interval graphs, and planar graphs.
SIAM J. Comput. 10 (1981), no. 1, 203--225.

created: 25 Aprile 2001
updated: 25 Aprile 2001