Evolutionary Computation Meets Graph Drawing: Runtime Analysis for Crossing Minimisation on Layered Graph Drawings
Pages 1533 - 1541
Abstract
Graph Drawing aims to make graphs visually comprehensible while faithfully representing their structure. In layered drawings, each vertex is drawn on a horizontal line and edges are drawn as y-monotone curves. A key ingredient for constructing such drawings is the One-Sided Bipartite Crossing Minimisation (OBCM) problem: given two layers of a bipartite graph and a fixed horizontal order of the vertices on the first layer, the task is to order the vertices on the second layer to minimise the number of edge crossings.
We analyse the performance of simple evolutionary algorithms for OBCM and compare different operators for permutations: exchanging two elements, swapping adjacent elements and jumping an element to a new position. We show that the simplest and cheapest mutation operator, swap, shows excellent performance on instances that can be drawn crossing-free, which corresponds to a generalised sorting problem. We give a tight runtime bound of Θ(n2) via a parallel BubbleSort algorithm and a delay sequence argument. This gives a positive answer to an open problem from Scharnow, Tinnefeld, and Wegener (2004) on whether the best-known bound of O(n2 log n) for sorting in permutation spaces can be improved to Θ(n2), albeit for an even simpler operator.
References
[1]
Giuseppe Di Battista, Peter Eades, Roberto Tamassia, and Ioannis G Tollis. 1998. Graph drawing: algorithms for the visualization of graphs. Prentice Hall PTR.
[2]
Vijay Dhanjibhai Bhuva, Duc-Cuong Dang, Liam Huber, and Dirk Sudholt. 2022. Evolutionary Algorithms for Cardinality-Constrained Ising Models. In 17th International Conference on Parallel Problem Solving from Nature (PPSN 2022), Günter Rudolph, Anna V. Kononova, Hernán E. Aguirre, Pascal Kerschke, Gabriela Ochoa, and Tea Tusar (Eds.). Springer, 456--469.
[3]
Camil Demestrescu and Irene Finocchi. 2001. Breaking cycles for minimizing crossings. Journal of Experimental Algorithmics (JEA) 6 (2001), 2--es.
[4]
M. Dietzfelbinger, B. Naudts, C. Van Hoyweghen, and I. Wegener. 2003. The analysis of a recombinative hill-climber on H-IFF. IEEE Transactions on Evolutionary Computation 7, 5 (2003), 417--423.
[5]
Benjamin Doerr, Yassine Ghannane, and Marouane Ibn Brahim. 2024. Runtime Analysis for Permutation-based Evolutionary Algorithms. Algorithmica 86, 1 (2024), 90--129.
[6]
Benjamin Doerr and Edda Happ. 2008. Directed trees: A powerful representation for sorting and ordering problems. In Proceedings of the IEEE Congress on Evolutionary Computation (CEC 2008). IEEE, 3606--3613.
[7]
Benjamin Doerr and Frank Neumann (Eds.). 2020. Theory of Evolutionary Computation: Recent Developments in Discrete Optimization. Springer.
[8]
Vida Dujmović, Henning Fernau, and Michael Kaufmann. 2008. Fixed parameter algorithms for one-sided crossing minimization revisited. Journal of Discrete Algorithms 6, 2 (2008), 313--323.
[9]
Vida Dujmovic and Sue Whitesides. 2004. An Efficient Fixed Parameter Tractable Algorithm for 1-Sided Crossing Minimization. Algorithmica 40, 1 (2004), 15--31.
[10]
Peter Eades, Brendan D McKay, and Nicholas C Wormald. 1986. On an edge crossing problem. In Proc. 9th Australian Computer Science Conference. 334.
[11]
Peter Eades and Nicholas C. Wormald. 1994. Edge crossings in drawings of bipartite graphs. Algorithmica 11, 4 (1994), 379--403.
[12]
Henning Fernau, Fedor V Fomin, Daniel Lokshtanov, Matthias Mnich, Geevarghese Philip, and Saket Saurabh. 2010. Ranking and drawing in subexponential time. In International Workshop on Combinatorial Algorithms. Springer, 337--348.
[13]
Paul Fischer, Emil Lundt Larsen, and Carsten Witt. 2023. First Steps Towards a Runtime Analysis of Neuroevolution. In Proceedings of the 17th ACM/SIGEVO Conference on Foundations of Genetic Algorithms (FOGA 2023). ACM, 61--72.
[14]
Michael R Garey and David S Johnson. 1979. Computers and intractability: a guide to the theory of NP-hardness.
[15]
Tomas Gavenciak, Barbara Geissmann, and Johannes Lengler. 2019. Sorting by Swaps with Noisy Comparisons. Algorithmica 81, 2 (2019), 796--827.
[16]
Thomas Jansen. 2013. Analyzing Evolutionary Algorithms - The Computer Science Perspective. Springer.
[17]
Michael Jünger and Petra Mutzel. 2002. 2-layer straightline crossing minimization: Performance of exact and heuristic algorithms. In Graph Algorithms and Applications I. World Scientific, 3--27.
[18]
Yasuaki Kobayashi and Hisao Tamaki. 2015. A Fast and Simple Subexponential Fixed Parameter Algorithm for One-Sided Crossing Minimization. Algorithmica 72, 3 (2015), 778--790.
[19]
Per Kristian Lehre and Xin Yao. 2014. Runtime analysis of the (1 + 1) EA on computing unique input output sequences. Information Sciences 259 (2014), 510--531.
[20]
Erkki Mäkinen and Mika Sieranta. 1994. Genetic algorithms for drawing bipartite graphs. International Journal of Computer Mathematics 53, 3-4 (1994), 157--166.
[21]
Xavier Muñoz, W. Unger, and Imrich Vrt'o. 2002. One Sided Crossing Minimization Is NP-Hard for Sparse Graphs. In Graph Drawing, Petra Mutzel, Michael Jünger, and Sebastian Leipert (Eds.). Springer Berlin Heidelberg, 115--123.
[22]
Samadhi Nallaperuma, Frank Neumann, and Dirk Sudholt. 2017. Expected Fitness Gains of Randomized Search Heuristics for the Traveling Salesperson Problem. Evolutionary Computation 25 (2017), 673--705. Issue 4.
[23]
Frank Neumann. 2008. Expected runtimes of evolutionary algorithms for the Eulerian cycle problem. Computers & Operations Research 35, 9 (2008), 2750--2759.
[24]
Frank Neumann and Carsten Witt. 2010. Bioinspired Computation in Combinatorial Optimization - Algorithms and Their Computational Complexity. Springer.
[25]
Matthew Newton, Ondrej Sỳkora, Mark Withall, and Imrich Vrt'o. 2003. A parallel approach to row-based VLSI layout using stochastic hill-climbing. In International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems. Springer, 750--758.
[26]
Chao Qian. 2023. Can Evolutionary Clustering Have Theoretical Guarantees? IEEE Transactions on Evolutionary Computation (2023). Early access.
[27]
Abhiram Ranade. 2001. The Delay Sequence Argument. In Handbook of Randomized Algorithms. Kluwer Academic Publishers, Chapter 1.
[28]
J. Scharnow, K. Tinnefeld, and Ingo Wegener. 2004. The Analysis of Evolutionary Algorithms on Sorting and Shortest Paths Problems. Journal of Mathematical Modelling and Algorithms 3, 4 (2004), 349--366.
[29]
Kozo Sugiyama, Shojiro Tagawa, and Mitsuhiko Toda. 1981. Methods for visual understanding of hierarchical system structures. IEEE Transactions on Systems, Man, and Cybernetics 11, 2 (1981), 109--125.
[30]
Madeleine Theile. 2009. Exact Solutions to the Traveling Salesperson Problem by a Population-Based Evolutionary Algorithm. In Evolutionary Computation in Combinatorial Optimization, Carlos Cotta and Peter Cowling (Eds.). Springer, 145--155.
[31]
Deborah C. Wang. 1991. Novel Routing Schemes for IC Layout, Part I: Two-Layer Channel Routing. In Proceedings of the 28th Design Automation Conference, A. Richard Newton (Ed.). ACM, 49--53.
[32]
Lin Xuemin. 1989. How to draw a directed graph. In 1989 IEEE Workshop on Visual Languages. IEEE Computer Society, 13--14.
Index Terms
- Evolutionary Computation Meets Graph Drawing: Runtime Analysis for Crossing Minimisation on Layered Graph Drawings
Recommendations
On the Parameterized Complexity of Layered Graph Drawing
We consider graph drawings in which vertices are assigned to layers and edges are drawn as straight line-segments between vertices on adjacent layers. We prove that graphs admitting crossing-free h-layer drawings (for fixed h) have bounded pathwidth. We ...
Layered Separators for Queue Layouts, 3D Graph Drawing and Nonrepetitive Coloring
FOCS '13: Proceedings of the 2013 IEEE 54th Annual Symposium on Foundations of Computer ScienceGraph separators are a ubiquitous tool in graph theory and computer science. However, in some applications, their usefulness is limited by the fact that the separator can be as large as Ω(__ __n) in graphs with n vertices. This is the case for planar ...
Outerplanar graph drawings with few slopes
We consider straight-line outerplanar drawings of outerplanar graphs in which a small number of distinct edge slopes are used, that is, the segments representing edges are parallel to a small number of directions. We prove that @D-1 edge slopes suffice ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2024
1657 pages
Copyright © 2024 Copyright is held by the owner/author(s). Publication rights licensed to ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 14 July 2024
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
GECCO '24
Sponsor:
GECCO '24: Genetic and Evolutionary Computation Conference
July 14 - 18, 2024
VIC, Melbourne, Australia
Acceptance Rates
Overall Acceptance Rate 1,669 of 4,410 submissions, 38%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 88Total Downloads
- Downloads (Last 12 months)88
- Downloads (Last 6 weeks)25
Reflects downloads up to 18 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in