We consider the one-sided crossing minimization problem (CP): given a bipartite graph G and a permutation x0 of the vertices on a layer, find a permutation x1 of the vertices on the other layer which minimizes the number of edge crossings in any straigthline drawing of G where vertices are placed on two parallel lines and sorted according to x0 and x1. Solving CP represents a fundamental step in the construction of aesthetically pleasing layouts of hierarchies and directed graphs, but unfortunately this problem has been proved to be NP-complete. In this paper we address the strong relation between CP and the problem of computing minimum feedback arc sets in directed graphs and we devise a new approximation algorithm for CP, called PM, that exploits this dependency. We experimentally and visually compare the performance of PM with the performance of well-known algorithms and of recent attractive strategies. Experiments are carried out on different families of randomly generated graphs, on pathological instances, and on real test sets. Performance indicators include both number of edge crossings and running time, as well as structural measures of the problem instances. We found CP to be a very interesting and rich problem from a combinatorial point of view. Our results clearly separate the behavior of the algorithms, proving the effectiveness of PM on most test sets and showing tradeoffs between quality of the solutions and running time. However, if the visual complexity of the drawings is considered, we found no clear winner. This confirms the importance of optimizing also other aesthetic criteria such as symmetry, edge length, and angular resolution.

Breaking cycles for minimizing crossings / Demetrescu, Camil; Finocchi, Irene. - In: ACM JOURNAL OF EXPERIMENTAL ALGORITHMICS. - ISSN 1084-6654. - 6:(2001), pp. 2-es. [10.1145/945394.945396]

Breaking cycles for minimizing crossings

DEMETRESCU, Camil;FINOCCHI, Irene
2001

Abstract

We consider the one-sided crossing minimization problem (CP): given a bipartite graph G and a permutation x0 of the vertices on a layer, find a permutation x1 of the vertices on the other layer which minimizes the number of edge crossings in any straigthline drawing of G where vertices are placed on two parallel lines and sorted according to x0 and x1. Solving CP represents a fundamental step in the construction of aesthetically pleasing layouts of hierarchies and directed graphs, but unfortunately this problem has been proved to be NP-complete. In this paper we address the strong relation between CP and the problem of computing minimum feedback arc sets in directed graphs and we devise a new approximation algorithm for CP, called PM, that exploits this dependency. We experimentally and visually compare the performance of PM with the performance of well-known algorithms and of recent attractive strategies. Experiments are carried out on different families of randomly generated graphs, on pathological instances, and on real test sets. Performance indicators include both number of edge crossings and running time, as well as structural measures of the problem instances. We found CP to be a very interesting and rich problem from a combinatorial point of view. Our results clearly separate the behavior of the algorithms, proving the effectiveness of PM on most test sets and showing tradeoffs between quality of the solutions and running time. However, if the visual complexity of the drawings is considered, we found no clear winner. This confirms the importance of optimizing also other aesthetic criteria such as symmetry, edge length, and angular resolution.
File allegati a questo prodotto
File Dimensione Formato  
VE_2001_11573-132574.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 1.02 MB
Formato Adobe PDF
1.02 MB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/132574
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 17
  • ???jsp.display-item.citation.isi??? ND
social impact