Draw this planar graph

Question

The playing board for this puzzle is a short list of digits; there is one rule governing possible moves: The 1 may swap with a digit one place to the right; the 2 may swap with a digit two places to the right, and so on.

For example, in the list 1,3,7,2,6,5,4, you can swap 3 and 6, because the latter is 3 places to the right of 3:

┌─┐
┷ ▼
1,3,7,2,6,5,4     →     3,1,7,2,6,5,4

The only other legal moves from this position are to swap 1 and 3 (yielding 3,1,7,2,6,5,4) or to swap 2 and 5 (yielding 1,6,7,5,3,2,4):

  ┌─────┐
  ┷     ▼
1,3,7,2,6,5,4     →     1,6,7,2,3,5,4

      ┌───┐
      ┷   ▼
1,3,7,2,6,5,4     →     1,3,7,5,6,2,4

Here is a graph of all possible states reachable from 1,2,3:

123 → 213 → 312 → 321
       ↓     ↑
      231 → 132

(For lists of few digits, let's just omit the separating commas).

For the 24 states reachable from 1,2,3,4, the corresponding graph can be drawn. Do so, and make sure to avoid crossing lines!

Bonus points for symmetries, aesthetics, and for using ASCII-art (or Unicode text ─ │ ┌ ┐ └ ┘).

_{If you need to omit the arrowheads, or the labels that distinguish the nodes, that's okay as long as the nodes are recognizable. Maybe mark the 1234 and 4321 nodes.}

Is there a cycle (some sequence of two or more moves, after which the board state is the same in the beginning) for any permutation of the numbers 1,2,...,n, any n?

Answer 1

The fact that flipping all sequences flips all the arrows makes for some very nice graph symmetries:

Anyone with way too much time on their hands is free to play with the length-5 version here.

Answer 2

ASCII art rendering of completed graph:

 .------------------------------------.
 |                                    |
 |    .---------->4321<-----------.   |
 |    |                           |   |
 |    |                           |   |
 |  4312<--4132<--1432<--1234   2341  |
 |    ^      ^             |      ^   |
 |    |      |             v      |   |
 '->4213-->4231          2134-->2314  |
      ^                    |      |   |
      |                    v      v   |
 .->4123<----------------3124<--1324  |
 |    ^                    |          |
 |    |                    v          |
 |  1423<--3421<--3412<--3214---------'
 |    ^      ^      ^      |
 |    |      |      |      v
 |  2413-->2431     |    3241-->1243--.
 |    ^             |      |      |   |
 |    |             |      |      v   |
 '--2143<---------3142<----'    1342  |
      ^             |             |   |
      |             '-------------'   |
      |                               |
      '-------------------------------'

Answer 3

I think this works, without crossing lines:

I’d imagine the answer to the second question is

No. Consider a string of length n, with elements i=1,...,n and positions j=1,...,n. Once element n is moved away from position n, it can never return to its initial position. This is because moving from position j, j != n, to position n requires an element of at most n-1. So we conclude that element i=n must stay in place in order for this sequence to work. This is then equivalent to creating a cycle from a string of length n-1, with elements i=1,...,n-1 and positions j=1,...,n-1. We see that, by similar logic to the above, element i=n-1 must also stay in place (moving from position j, j != n-1, to position n-1 requires an element of at most n-2). By induction it follows that the starting position can not be arrived at after any moves have been made.

Answer 4

Hint:

Explore paths from 3124 to 4213 first.

Here's my own answer using unicode line-drawing characters (without arrowheads) - different lines for swaps depending on their offset:

      ┌─────────────────────────────────────────2341
     2314═══1324                                  ║
      │      │                                    ║
     2134═══3124───────────────────────┐          ║
      │      ┃   ┏━━━━━━━━━━━━3241───3214━━┓      ║
      │      ┃   ┃              ║      ║   ┃   ▃▃▃║▃▃
      │      ┃  1243═══1342───3142───3412  ┃   ▉4321▉
      │      ┃   │┏━━━━━━━━━━━━━┛     ┃│   ┃   ▀▀▀│▀▀
    ▃▃│▃▃▃   ┃   │┃     ┏━━━━━━━━━━━━━┛│   ┃      │
    ▉1234▉   ┃  2143───2413───2431═══3421  ┃      │
    ▀▀║▀▀▀   ┃   ║      ║              ┃   ┃      │
      ║      ┗━━4123───1423━━━━━━━━━━━━┛   ┃      │
      ║          └───────────────────────4213═══4312
      ║                                    │      │
      ║                                  4231═══4132
     1432 ────────────────────────────────────────┘

Unicode within <pre> within a spoiler was a puzzle of its own. Kudos to Daniel!