Access Restriction

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

   Open content in new tab
Source: ACM Digital Library