### Breaking cycles for minimizing crossingsBreaking cycles for minimizing crossings

Access Restriction
Subscribed

 Author Demestrescu, Camil ♦ Finocchi, Irene Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2001 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data Subject Keyword Experimental algorithms ♦ Bipartite graphs ♦ Crossing minimization Abstract We consider the one-sided crossing minimization problem (CP):given a bipartite graph $\textit{G}$ and a $permutationx_{0}$ of the vertices on a layer, find a $perumuationx_{1}$ of the vertices on the other layer whichminimizes the number of edge crossings in any straightline drawingof $\textit{G}$ where vertices are placed on two parallel lines andsorted according to $x_{0}$ and $x_{1}.Solving$ CP represents a fundamental step in the construction ofaesthetically pleasing layouts of heirarchies and directed graphs,but unfortunately this problem has been proved to beNP-complete.In this paper we address the strong relation between CP and theproblem of computing minimum feedback arc sets in directed graphsand we devise a enw approximation algorithm for CP, called PM, thatexploits this dependency. We experimantally and visually comparethe performance of PM with the performance of well-known algorithmsand of recent attractive strategies. Experiments are carried out ondifferent families of randomly generated graphs, on pathologicalinstances, and on real test sets. Performance indicators includeboth number of edge crossings and running time, as well asstructural measures of the problem instances. We found CP to be avery interesting and rich problem from a combinatorial point ofview. Our results clearly separate the behavior of the algorithms,proving the effectiveness of PM on most test sets and showingtradeoffs between quality of the solutions and running time.However, if the visual complexity of the drawings is considered, wefound no clear winner. This confirms the importance of optimizingalso other aesthetic criteria such as symmetry, edge length, andangular resolution. ISSN 10846654 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2001-12-01 Publisher Place New York e-ISSN 10846654 Journal Journal of Experimental Algorithmics (JEA) Volume Number 6

#### Open content in new tab

Source: ACM Digital Library