Handshaking with no crossovers in minimum number of rounds: has this problem been studied?

I've met a group of 9 colleagues (PhD students), and when we came to handshake it was complicated as always to handshake everyone and avoid cross overs.

So one guy suggested (he was not serious about it) to study the problem of the minimum number of rounds for a circle of $n$ friends to handshake such that no crossovers occur. Of couse the minimum if we allow crossovers is $n-1$ rounds, because if we fix a person, then in each round he gets to shake hands with at most one other person. But there is a moment where the two guys next to him shake hands, and so he sits idle in that round.

The natural question is if there is a formula for the least number of rounds needed in this case, or at least lower bound lower than the trivial bound where each person gets to shake hands with all others while everyone else stands still waiting for him to finish.

I am not expecting a solution but rather hoping if this problem has been studied before. When I tried searching I ran into all sorts of homework problems like "if 534345 handshakes happened then how many people were there" ... I wasn't also sure of the search terms; I tried both "crossovers" and "intersection" but no avail.


Edit:

From the comments I realize that maybe more solid definition for the problem is needed. Here it goes:

There is a set $P$ of $n$ people positioned at the vertices of a regular $n$-gon. The goal is that after the "program" terminates, every person should have shook hands with every other person exactly once. By "shaking hands" we mean that two persons have a edge connecting them. The execution proceeds in rounds, such that at each round a person may be either "shaking hands" with another person, or doing nothing. A person $i$ who shook hands in some preceding round with a subset of people $J\subseteq (P-\{i\})$ will consider only the people he did not shake hands with yet $(P-(J\cup\{i\}))$ in the next round, by selecting one of them to shake hands with. The constraint is that at no round no two edges can intersect.

The question is to determine the minimum number of rounds needed to solve this problem ?

Also I would be interested in a special case where the edges are restricted to be "straight lines", rendering the constraint a little bit different from planar graph condition, to a more geometrical condition.


I don't know if it has been studied before, but I think this may be a solution for even $n=2m$.

Number the people around the circle from 1 to $2m$.

In round $j$, $1\le j\le m$, person $j$ shakes hands with person $j+1$, and all other handshakes are "parallel" to this (so, $j-1$ with $j+2$, $j-2$ with $j+3$, and so on - throughout, the labels are interpreted modulo $n$, as necessary). At the end of these $m$ rounds, everyone has shaken hands with everyone an odd number of people away.

In round $m+j$, $1\le j\le m$, $j$ shakes with $j+2$ and all other handshakes are parallel (so $j-1$ with $j+3$, $j-2$ with $j+4$, etc.). This handles all the pairs an even number of people apart. So the total is $2m$ rounds.

As noted in the problem statement, $2m-1$ rounds is impossible, so $2m$ is the answer.

EDIT: The odd case is even easier. In round $j$, person $j$ sits out while $j-1$ greets $j+1$, $j-2$ greets $j+2$, etc., again using $n$ rounds.


Yes, this has been considered before.

When I was a high school student, I've seen this problem in a mathematics problem solving seminar (problem 4). Unfortunately, there is no English version of the problem statements and solutions.

If you drop the non-crossing condition, then the fact that $n-1$ rounds are enough when $n$ is even is a special case of Baranyai's theorem. The case of odd $n$ follows easily, because then $n-1$ rounds are not enough (since no perfect matching exists) and $n$ are enough, because we can use the strategy for $n+1$ people and ignore the person number $n+1$.

Allowing non-straight connections is the same as allowing crossings and the above applies. Indeed, whatever matching you come up with, you can draw it with curves without any crossings. This is because you can draw the connections one by one and since the graph has no cycles, no person will ever get enclosed.

Peter Jackson's notes on the combinatorics of handshakes contains the description of the solution with crossings allowed and it also gives the non-crossing solution for $n$ odd on page 5.

The dissertation of Andreas Razen contains a similar problem with almost the same motivation. (See page 48.)