Finding the smallest ordering of all distance-1 points in a regular $3 \times N$ grid?

Question

Apologies for the poor mathematical terminology, I'm a physicist/engineer by training.

So I have a set of 2D coordinates of the form $s \in S$ where

$$s = (x, y), \quad x \in \{0, 1, 2\}, \quad y \in \{0, 1, 2, \dots, N-1\}.$$

In layman's terms, they form a rectangle of $3 \times N$ points / vertices.

I want to form an ordered list of points $[s_1, s_2, \dots, s_m]$ of length $m$, (each pair $(s_i, s_{i+1})$ can be considered a edge / line drawn between those two points).

With $M = \{1, 2, 3, \dots, m\}$, the rules constraining the graph are:

1. An edge can only have length 1, that is $$|x_{i+1} - x_i| + |y_{i+1} - y_i| = 1 \quad \forall\ \ i \in M ,\ i \neq m$$ This means that an edge can only be between in the direction $(1,0), (-1,0), (0, 1)$ or $(0, -1)$.

2. Every vertex must be connected to all vertices length 1 away from it (so at least one edge for each vertex below, above, to the right and to the left (if they exist)).

3. We start where we finish: $s_1 = s_m$

I'm trying to find a solution (algorithm) to the above which minimises $m$.

Here is a figure showing a possible to the $N=4$ case (starting and finishing at $(0,0)$), but I very much doubt it is an optimal solution.

Things to note:

1. I'm pretty sure that this is not possible without having some nodes connected by multiple edges, so some entries are non-unique $(\exists (i, j ) \in M^2 : s_i = s_j)$.

2. An edge is direction independent, so as long as distance-1 pair $\{s_i, s_j\}$ have an edge $(s_i, s_j)$, there is no requirement of an edge $(s_j, s_i)$ and visa versa.

3. This seems, according to my research, similar to a number of problems in graph theory and computer science, but I couldn't find an exact analogue. Most concern themselves with variable distance vertices and edges, this appears to be a very particular case. Is there a particular name for these sort of graphs?

Doing it the naive way (just making a sequence of $2 \times 3$ outline boxes with a line back down the middle like I did in the figure) gives

$$m \approx 5N$$

Even finding any $m$ smaller than this would be useful.

Thank you for anyone who even took the time to try and decipher this, let alone answer!

Answer 1

First, we must have $2N$ vertical edges and $3(N-1)$ horizontal edges just to put one edge between every two adjacent vertices: $5N-3$ edges.

Second, at each vertex, we must have the same number of edges going in and going out, so an even number of edges total. In the minimal construction above, $2N-2$ vertices have odd degree: the $2(N-2)$ vertices on the top and bottom sides, and the $2$ vertices on the left and right sides (but not the corners).

Each extra edge can fix at most two of these odd vertices, so we need $N-1$ more edges. This would bring us to $6N-4$.

But the two odd vertices on the left and right sides cannot be fixed that easily. Each of them has only even vertices as neighbors, so adding one extra edge to them makes a new vertex odd, which requires another edge to fix. This adds $2$ more edges, putting us at $6N-2$.

There is a $6N-2$ edge solution, as shown below, so this is best possible.

Starting in, say, the top left corner, just go around the outside cycle and come back (which takes $2(N-1)+4 = 2N+2$ steps) and then go around the inside cycle and come back (which takes $4(N-1) = 4N-4$ steps), for $6N-2$ steps total.