Drawing Permutations with Few Corners

Bereg, Sergey and Holroyd, Alexander E. and Nachmanson, Lev and Pupyrev, Sergey (2013) Drawing Permutations with Few Corners. In: 21st International Symposium, GD 2013, September 23-25, 2013, Bordeaux, France , pp. 484-495 (Official URL: http://dx.doi.org/10.1007/978-3-319-03841-4_42).

Full text not available from this repository.


A permutation may be represented by a collection of paths in the plane. We consider a natural class of such representations, which we call tangles, in which the paths consist of straight segments at 45 degree angles, and the permutation is decomposed into nearest-neighbour transpositions. We address the problem of minimizing the number of crossings together with the number of corners of the paths, focusing on classes of permutations in which both can be minimized simultaneously. We give algorithms for computing such tangles for several classes of permutations.

Item Type:Conference Paper
Classifications:G Algorithms and Complexity > G.210 Bends
G Algorithms and Complexity > G.420 Crossings
P Styles > P.600 Poly-line
ID Code:1399

Repository Staff Only: item control page


Albert, M.H., Aldred, R.E.L., Atkinson, M., van Ditmarsch, H.P., Handley, C.C., Holton, D.A., McCaughan, D.J.: Compositions of pattern restricted sets of permutations. Australian J. Combinatorics 37, 43–56 (2007)

Angel, O., Holroyd, A.E., Romik, D., Virag, B.: Random sorting networks. Advances in Mathematics 215(2), 839–868 (2007)

Argyriou, E.N., Bekos, M.A., Kaufmann, M., Symvonis, A.: On metro-line crossing minimization. Journal of Graph Algorithms and Applications 14(1), 75–96 (2010)

Benkert, M., Nöllenburg, M., Uno, T., Wolff, A.: Minimizing intra-edge crossings in wiring diagrams and public transportation maps. In: Kaufmann, M., Wagner, D. (eds.) GD 2006. LNCS, vol. 4372, pp. 270–281. Springer, Heidelberg (2007)

Bereg, S., Holroyd, A.E., Nachmanson, L., Pupyrev, S.: Drawing permutations with few corners. ArXiv e-print abs/1306.4048 (2013)

Didimo, W., Eades, P., Liotta, G.: Drawing graphs with right angle crossings. Theoretical Computer Science 412(39), 5156–5166 (2011)

Klazar, M.: The Füredi-Hajnal conjecture implies the Stanley-Wilf conjecture. In: Krob, D., Mikhalev, A., Mikhalev, A. (eds.) Formal Power Series and Algebraic Combinatorics, pp. 250–255. Springer, Heidelberg (2000)

Knuth, D.: The art of computer programming. Addison-Wesley (1973)

Marcus, A., Tardos, G.: Excluded permutation matrices and the Stanley-Wilf conjecture. Journal of Combinatorial Theory, Series A 107(1), 153–160 (2004)

Pupyrev, S., Nachmanson, L., Bereg, S., Holroyd, A.E.: Edge routing with ordered bundles. In: van Kreveld, M.J., Speckmann, B. (eds.) GD 2011. LNCS, vol. 7034, pp. 136–147. Springer, Heidelberg (2012)

Spencer, T.H., Mayr, E.W.: Node weighted matching. In: Paredaens, J. (ed.) ICALP 1984. LNCS, vol. 172, pp. 454–464. Springer, Heidelberg (1984)

Wang, D.C.: Novel routing schemes for IC layout, part I: Two-layer channel routing. In: 28th ACM/IEEE Design Automation Conference, pp. 49–53 (1991)

White, A.T.: Ringing the changes. Mathematical Proceedings of the Cambridge Philosophical Society 94, 203–215 (1983)