An exact approach to upward crossing minimization

Autor(en): Chimani, M. 
Zeranski, R.
Herausgeber: McGeoch, C.C.
Meyer, U.
Stichwörter: Boolean algebra; Drawing (graphics); Iterative methods; Optimization, Boolean formulae; Crossing minimization; Crossing number; Edge crossing; Exact approach; Graph-drawing problem; Optimum solution; State of the art, Problem solving
Erscheinungsdatum: 2014
Herausgeber: Society for Industrial and Applied Mathematics Publications
Enthalten in: Proceedings of the Workshop on Algorithm Engineering and Experiments
Startseite: 73
Seitenende: 85
The upward crossing number problem asks for a drawing of the graph into the plane with the minimum number of edge crossings where the edges are drawn as monotonously increasing curves w.r.t. the y-axis. While there is a large body of work on solving this central graph drawing problem heuristically, we present the first approach to solve the problem to proven optimality. Our approach is based on a reformulation of the problem as a boolean formula that can be iteratively tightened and resolved. In our experiments, we show the practical applicability and limits of our approach. Furthermore, we can now for the first time evaluate the state-of-the-art heuristics w.r.t. true optimum solutions. This leads to the finding that these algorithms are in general surprisingly far away from the optimum. Finally, we show that we can use our approach as a strong heuristic: even after only one minute of running time, our approach typically gives better solutions than the known heuristics for medium sized instances. Copyright © 2014. by the Society for Industrial and Applied Mathematics.
Conference of 16th Workshop on Algorithm Engineering and Experiments, ALENEX 2014 ; Conference Date: 5 January 2014 Through 5 January 2014; Conference Code:109505
ISBN: 9781611973198
ISSN: 21640300
DOI: 10.1137/1.9781611973198.8
Externe URL:

Show full item record

Page view(s)

Last Week
Last month
checked on Jun 16, 2024

Google ScholarTM