An exact approach to upward crossing minimization

DC FieldValueLanguage
dc.contributor.authorChimani, M.
dc.contributor.authorZeranski, R.
dc.contributor.editorMcGeoch, C.C.
dc.contributor.editorMeyer, U.
dc.descriptionConference of 16th Workshop on Algorithm Engineering and Experiments, ALENEX 2014 ; Conference Date: 5 January 2014 Through 5 January 2014; Conference Code:109505
dc.description.abstractThe 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.
dc.publisherSociety for Industrial and Applied Mathematics Publications
dc.relation.ispartofProceedings of the Workshop on Algorithm Engineering and Experiments
dc.subjectBoolean algebra
dc.subjectDrawing (graphics)
dc.subjectIterative methods
dc.subjectOptimization, Boolean formulae
dc.subjectCrossing minimization
dc.subjectCrossing number
dc.subjectEdge crossing
dc.subjectExact approach
dc.subjectGraph-drawing problem
dc.subjectOptimum solution
dc.subjectState of the art, Problem solving
dc.titleAn exact approach to upward crossing minimization
dc.typeconference paper
dcterms.isPartOf.abbreviationProc. Workshop Algorithm Eng. Exp.
Show simple item record

Page view(s)

Last Week
Last month
checked on May 27, 2024

Google ScholarTM