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 , pp. 484-495(Official URL: http://dx.doi.org/10.1007/978-3-319-03841-4_42).

Full text not available from this repository.

Abstract

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
Divisions: UNSPECIFIED
Depositing User: Administration GDEA
Date Deposited: 13 Aug 2014 15:57
Last Modified: 15 Aug 2014 08:48
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1399

Actions (login required)

View Item View Item