Have you ever gone to the movies and worried about who you’re going to sit next to?  This comic illustrates the common dilemma moviegoers face when filling the theatre aisles.

www.xkcd.com/173

The complex relationships between each pair of people in a group can be reflected in an acquaintance graph, such as the one shown above in the comic. Most people in such a network are usually acquainted with a majority of the group.  Consequently, a problem arises when each person can sit next to at most two people.  The question is: how do you convert a regular acquaintance graph (one where each person can be connected to an unlimited number of people) to a linear graph (where each person has an edge to a maximum of two people) while achieving maximum social enjoyment for each person?

In constructing our linear graph, we shall assume that maximum social enjoyment is achieved if each person is sitting next to the person they like most out of the group.  Here is one possible method of constructing such a linear graph.  1) In the regular acquaintance graph, place a value on each side of the edge, representing how much a particular person likes the person on the other side of the edge. 2) Now, look at each node and circle the maximum value it has towards a node (in case of a tie, circle all the maximums). 3) Eliminate any edges which do not have any circled values.  This should give us a simplified acquaintance graph (Note that the new graph can consist of more than one connected component). 4) If the graph is linear, we are done.  If not, the problem boils down to finding a path within from one node to another that traverses all the nodes within the connected component exactly once.   This is called a Hamiltonian path (for more information see: http://en.wikipedia.org/wiki/Hamiltonian_path ).  5) The resulting Hamiltonian path is our linear graph.  (Note: there are some cases in which a Hamiltonian path does not exist.  However, we shall assume that group dynamics usually support Hamiltonian paths, because of the way friendships naturally unfold.)

This is a very simplistic approach towards constructing linear graphs, where many nuances have been overlooked.  Also, a different definition of maximum social enjoyment can be used.  However, this method is useful because of its simple approach, and will give a good result in most cases.