numero di incroci Minimizzare in un grafo bipartito

Question

Il seguente problema algoritmo verificato a me mentre traccia un grafico per qualcosa di estraneo:

Abbiamo un disegno in pianta di una grafo bipartito, con gli insiemi disgiunti disposte nelle colonne come mostrato. Come possiamo riorganizzare i nodi all'interno di ciascuna colonna in modo tale che il numero di attraversamenti dei bordi sia ridotto al minimo? So che questo problema è NP-difficile per i grafici generali (link), ma c'è qualche trucco considerando che il grafico è bipartito?

Come follow-up, cosa succede se c'è una terza colonna w, che ha solo bordi a v? O oltre?

Answer 1

Il documento On the one-sided crossing minimization in a bipartite graph with large degrees by Hiroshi Nagamochi menziona che la carta originale sul numero attraversamento Garey e Johnson anche dimostrato che riducendo il numero di incroci tra archi è NP-difficile per grafi bipartiti. In realtà, è ancora NP-hard anche se si è detto l'ordine ottimale per una colonna:

Dato un grafo bipartito, un disegno 2 strati consiste nell'inserire nodi nel primo set di nodi V una linea retta L1 e posizionando i nodi nel secondo set di nodi W su una linea parallela L2. Il problema di minimizzare il numero di incroci tra gli archi in un disegno a 2 strati era il primo introdotto da Harary e Schwenk. Il problema di minimizzazione dell'incrocio univoco chiede di trovare un ordinamento di nodi in V da posizionare su L1 in modo da che il numero di passaggi ad arco sia ridotto a icona (mentre l'ordine di W su L2 è dato e risolto). Le applicazioni del problema sono disponibili nei layout VLSI e nei disegni gerarchici.

Tuttavia, i problemi su entrambi i lati e su un lato sono indicati come NP-rigido rispettivamente da Garey e Johnson e da Eades e Wormald.

Answer 2

Peter de Rivaz ha indicato che è NP-Hard, ma comunque se si sta bene con qualche approssimazione si può andare con la seguente soluzione.

Il mio primo pensiero era di usare un algoritmo basato sulla forza per il layout grafico, ma può essere un po 'noioso da implementare. Ma hey, c'è questo meraviglioso programma graphviz.org, che può fare tutto il lavoro per te.

Così, dopo l'installazione solo preparare un file con il grafico:

graph G{ 
    {rank=same A B C D E} 
    {rank=same F G H K I J} 

    A -- F; 
    A -- G; 
    A -- K; 
    A -- I; 
    A -- H; 
    A -- J; 

    B -- G; 

    C -- G; 
    C -- J; 

    D -- K; 
    D -- I; 
} 

Run: dot -Tpng yourgraph -o yourgraph.png

e ottenere qualcosa di simile per gratuitamente :-):