%0 Conference Paper %1 fkrwz-cotf-gd19 %A Firman, Oksana %A Kindermann, Philipp %A Ravsky, Alexander %A Wolff, Alexander %A Zink, Johannes %B Proceedings of the 27th International Symposium on Graph Drawing and Network Visualization (GD'19) %D 2019 %E Archambault, Daniel %E Tóth, Csaba D. %I Springer-Verlag %K myown %P 203--215 %R 10.1007/978-3-030-35802-0\_16 %T Computing Height-Optimal Tangles Faster %V 11904 %X We study the following combinatorial problem. Given a set of n y-monotone wires, a tangle determines the order of the wires on a number of horizontal layers such that the orders of the wires on any two consecutive layers differ only in swaps of neighboring wires. Given a multiset L of swaps (that is, unordered pairs of numbers between 1 and n) and an initial order of the wires, a tangle realizes L if each pair of wires changes its order exactly as many times as specified by L. The aim is to find a tangle that realizes L using the smallest number of layers. We show that this problem is NP-hard, and we give an algorithm that computes an optimal tangle for n wires and a given list L of swaps in O((2|L|/n^2+1)^(n^2/2)phi^n n) time, where phi~1.618 is the golden ratio. We can treat lists where every swap occurs at most once in O(n! phi^n) time. We implemented the algorithm for the general case and compared it to an existing algorithm.

@inproceedings{fkrwz-cotf-gd19, abstract = {We study the following combinatorial problem. Given a set of n y-monotone wires, a tangle determines the order of the wires on a number of horizontal layers such that the orders of the wires on any two consecutive layers differ only in swaps of neighboring wires. Given a multiset L of swaps (that is, unordered pairs of numbers between 1 and n) and an initial order of the wires, a tangle realizes L if each pair of wires changes its order exactly as many times as specified by L. The aim is to find a tangle that realizes L using the smallest number of layers. We show that this problem is NP-hard, and we give an algorithm that computes an optimal tangle for n wires and a given list L of swaps in O((2|L|/n^2+1)^(n^2/2)phi^n n) time, where phi~1.618 is the golden ratio. We can treat lists where every swap occurs at most once in O(n! phi^n) time. We implemented the algorithm for the general case and compared it to an existing algorithm.}, added-at = {2019-10-01T18:14:41.000+0200}, arxiv = {https://arxiv.org/abs/1901.06548}, author = {Firman, Oksana and Kindermann, Philipp and Ravsky, Alexander and Wolff, Alexander and Zink, Johannes}, biburl = {https://www.bibsonomy.org/bibtex/231a97a76ff1b07773ef5c7bc84e1748a/kindermann}, booktitle = {Proceedings of the 27th International Symposium on Graph Drawing and Network Visualization (GD'19)}, doi = {10.1007/978-3-030-35802-0\_16}, editor = {Archambault, Daniel and T\'{o}th, Csaba D.}, interhash = {8261540fb2757401653d53a8f931bc86}, intrahash = {31a97a76ff1b07773ef5c7bc84e1748a}, keywords = {myown}, pages = {203--215}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, slides = {http://www1.pub.informatik.uni-wuerzburg.de/pub/kindermann/slides/2019-gd-tangles-oksana.pdf}, timestamp = {2021-02-12T10:13:49.000+0100}, title = {Computing Height-Optimal Tangles Faster}, volume = 11904, year = 2019 }