Drawing permutations with few corners

DOI10.1007/978-3-319-03841-4_42zbMATH Open1406.68064arXiv1306.4048OpenAlexW1920108104MaRDI QIDQ2867686FDOQ2867686

Authors: Sergey Bereg, A. E. Holroyd, Lev Nachmanson, Sergey Pupyrev 

Publication date: 20 December 2013

Published in: Graph Drawing (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1306.4048

Recommendations

• Representing permutations with few moves
• Tangles and degenerate tangles
• Permutation layout
• Drawing (complete) binary tanglegrams
• scientific article; zbMATH DE number 3877182

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cited In (4)

• Representing permutations with few moves
• Edge routing with ordered bundles
• The complexity of finding tangles
• Computing height-optimal tangles faster

This page was built for publication: Drawing permutations with few corners

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2867686)