[Generico] algoritmo ricerca facce di un grafo

[TuLKaS85]

salve

devo trovare le facce di un grafo planare.
Un grafo planare, è un grafo in cui gli archi non si incrociano mai se non nei vertici stessi. Nel mio caso gli archi sono dei segmenti che uniscono i vertici, e sono non orientati, quindi se ho due vertici a,b collegati da un arco e1 è possibile che avvengano le seguenti comunicazioni
a->b
b->a
dove le frecce rappresentano l'arco e1

Non è un problema di facile risoluzione e non mi interessano metodi particolarmente efficienti.
Qualcuno con esperienze in tal senso sa darmi qualche consiglio ?

A livello di implementazione, diciamo che riesco a ricavarmi un grafo planare, con una struttura contente le coordinate x,y dei nodi ed un altra gli archi, ogni arco non è altro che una coppia di nodi.
Sto lavorando in java, ma se qualcuno ha qualche idea usando qualche altro linguaggio non ci sono problemi.

[wingman87]

Manca una definizione di "faccia". Avendo una definizione formale magari è possibile tradurla senza difficoltà in codice...

[banryu79]

Originariamente inviato da TuLKaS85

s
Sto lavorando in java, ma se qualcuno ha qualche idea usando qualche altro linguaggio non ci sono problemi.

Se puoi usare librerie per i grafi, ti consiglio JGraphT (per la parte di strutture dati/algoritmi) eventualmente accoppiata a JGraph (senza la T ) per la visualizzazione grafica (JGraphT espone degli Adapter per JGraph)

Io sto usando JGraphT da un po' e mi sono trovato benissimo.

Circa il tuo algoritmo quoto wingman87.

[TuLKaS85]

si scusate, ho mancato una parte fondamentale...

beh per faccia intendo un ciclo chiuso all'interno del grafo, che non contiene altri cicli.
meglio spiegarlo con un immagine


qui si vedono tanti triangoli formati dagli archi che connettono i vari vertici, bene io ho bisogno per ognuno di quei singoli triangoli un IDfaccia, e ad esso associato una lista con gli id dei vertici che la compongono. Come si può vedere si possono formare cicli che hanno diciamo dei cicli minori all'interno, ma a me interessano solo quelli interni, cioè i triangolini.
Non sono ferrato in teoria dei grafi, per cui spero mi passiate la terminologia.
L'immagine comunque mostra un grafo dove ogni faccia ha tre vertici, diciamo che il mio caso è più generale, e non ci sono limiti massimi, ovviamente per avere una faccia ho bisogno di almeno tre vertici.

@banryu79
darò un occhiata grazie