Algoritmo più veloce per la planarizzazione dei grafici

Question

Sto utilizzando Elaborazione per sviluppare un sistema di navigazione per dati e processi complessi. Come parte di ciò sono entrato nel layout grafico piuttosto profondamente. È tutto divertente e le mie opinioni sugli algoritmi di layout sono: force-directed è per le femminucce (basta guardare la scala ... haha), la proiezione di autovetture è fantastica, gli strati Sugiyama sembrano buoni ma falliscono velocemente sui grafi graphy, e anche se ho fatto affidamento per quanto riguarda gli autovettori finora, ho bisogno di ridurre al minimo gli attraversamenti dei bordi per arrivare veramente al punto dei dati. Lo so, lo so NP-completo ecc

Vorrei aggiungere che ho qualche buon successo di applicare xy boxe e utilizzando permutazione Sugiyama-simile per ridurre incroci tra archi in tutta righe e colonne. Viz: grafico (| V | = 90, log di grado medio | V |) può passare da 11000 incroci -> 1500 (da autovettori inscatolati) -> 300 alternando permutazioni di riga e colonna per ridurre gli incroci.

Ma i minimi locali ... qualsiasi cosa si attesti attorno a questo marchio, e il risultato non è chiaro come potrebbe essere. La mia ricerca sulla Lit mi fa pensare che voglio davvero utilizzare l'algoritmo planarizzazione come quello che usano per VLSI:

1. Usa BFS o qualcosa per rendere il massimo planare sottografo 1.a. Layout La sottografo planare bello-come
2. abilmente aggiungere bordi eccezionali per recuperare il grafico originale

preghiamo di rispondere con i vostri pensieri sull'algoritmo planarizzazione più veloce, siete invitati a entrare in una certa profondità su eventuali ottimizzazioni specifiche hai avuto familiarità con.

Grazie mille!

Answer 1

Dato che tutti i grafici non sono planari (che tu sai), potrebbe essere meglio optare per un approccio "next-best" piuttosto che un approccio "always provide best answer".

Dico questo perché il mio compagno di stanza nella scuola di specializzazione ha avuto lo stesso problema che hai fatto. Stava cercando di convertire un grafico in una forma planare e tutti gli algoritmi che garantivano il minimo margine di attraversamento erano troppo lenti. Quello che ha finito per fare ciò che sta solo implementando un algoritmo randomizzato. Fondamentalmente, disponi il grafico, poi i nodi jigger che hanno bordi con molti incroci, e alla fine potrai gestire i peggiori ciuffi di bordi.

I vantaggi erano: puoi ritagliare dopo un certo periodo di tempo, quindi se hai un limite di tempo questo arriva sempre entro un certo periodo di tempo, se ottieni un grafico schifoso puoi semplicemente eseguirlo di nuovo (oltre il grafico già illustrato) per ottenere qualcosa di meglio, ed è relativamente facile da codificare.

Lo svantaggio è che non si ottengono sempre i minimi globali negli incroci, e se il grafico si blocca in zone ad alto passaggio, a volte il suo algoritmo scaglia un nodo in lontananza per cercare di risolverlo, il che a volte causa grafici davvero bizzarri.

Answer 2

Sai già molto layout grafico, ma credo che la tua domanda sia ancora, sfortunatamente, sottostimata.

È possibile planarizzare qualsiasi grafico molto velocemente nel modo seguente: (1) il layout in modo casuale il grafico su un piano (2) calcolare dove bordi croce (3) creare pseudo-vertici agli incroci (questo è quello che comunque quando si usa il layout basato sulla planarità per i grafi non planari) (4) il grafico esteso con i nuovi vertici e i bordi divisi è automaticamente planare.

La prima difficoltà deriva dall'avere un algoritmo che calcola un incorporamento combinatorio che riduce al minimo il numero di attraversamenti dei bordi. La seconda difficoltà consiste nell'utilizzare quell'incorporazione combinatoria per fare il layout nel piano euclideo che è visivamente accattivante, ad es. per il layout grafico ortogonale si potrebbe voler minimizzare il numero di curve, massimizzare la dimensione delle facce, minimizzare l'area del grafico nel suo insieme, ecc. e questi obiettivi potrebbero essere in conflitto l'un l'altro.