3
$\begingroup$

My problem is to find an efficient data structure that allows the encoding of a (non-directed) graph on the surface of a cylinder (without top and bottom discs). Usually I would store a graph as a list of edges, which are pairs $(a,b)$ of vertices. My problem is that I can have two kinds of edge from $a$ to $b$ either by taking the shortest path or going around the cylinder. These two edges should be considered as being different.

My set of vertices is fixed ($n$ vertices on the top circle, $n$ vertices on the bottom circle of the cylinder) and I requires that, for any vertex, there exists precisely one edge to another vertex. Furthermore crossings of edges are not allowed (that is why it is important to be able of "going around" the cylinder; taking a "longer" way).

The aim then is to glue two such cylinders together (the bottom of one goes on the top of the other) and compute the connected components of the "glued" graphs, which will produce another graph on a cylinder.

Of course one could just tag the edges, depending whether one goes the shortest or longest way, but maybe someone has a better idea!?

$\endgroup$
1
$\begingroup$

Let the vertices at the top be $a_0, \dots, a_{n-1}$ and those at the bottom be $b_0,\dots, b_{n-1}$, both ordered, say, clockwise. If the graph has no edge-crossings, the edge set can only be $\{(a_i,b_{i+k})\mid 0\leq i\leq n\}$ for some $k$, with addition carried out modulo $n$. So the edge set is uniquely determined by the value of $k$.

Beyond that, though, it's not clear what you're asking. The embedding of the graph in the surface of the cylinder could be much more complicated than you're suggesting. For example, the edges could all spiral anticlockwise around the cylinder thirteen times. Or they could spiral anticlockwise three times, then clockwise four times, and then wiggle around lots. Perhaps you have a requirement that the edges can't spiral multiple times? And/or that they're straight lines if you "unwrap" the cylinder and lay it flat? If so, note that gluing two cylinders together doesn't maintain this property: for example, if you glue the cylinder that has edges $(a_i,b_{i+1})$ using shortest paths to the cylinder that has edges $(a_i,b_{i-1})$ using shortest paths, you get a cylinder whose edges zig-zag, so aren't straight lines, don't use shortest paths and don't "go the long way around". Likewise, if you glue $2n$ copies of the cylinder that uses shortest paths to link $a_i$ to $a_{i+1}$, you get a cylinder whose edges spiral twice.

$\endgroup$
2
  • $\begingroup$ Thanks, David. Maybe I wasn't clear enough. Vertices have to be pairwise connected, but not necessarily from the top to the bottom. For instance it is possible that two vertices on the top are connected by an edge. If these two vertices are not adjacent, then the vertices "between" them have to be also linked among themselves as otherwise one would have crossings. When composing such graphs it is possible that loops are created on cylinder, which have to be removed (sorry, forgot about it). Such a loop can be either contractible to a point or can be a circle around the cylinder. $\endgroup$ Oct 8 '15 at 8:10
  • $\begingroup$ Also the spinning around $n$ times is allowed and probably I have forgotten that I need to record this as well in my data structure. If one takes the graph that links $a_0$ to $b_{n-1}$ and $a_i$ to $b_{i-1}$ for $1\leq i\leq n-1$ and composes it with itself $k$ times, then at each step I will get a different graph (in the sense that it is not homotopic equivalent to the ones before). Any idea how to save this in my data structure? $\endgroup$ Oct 8 '15 at 8:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.