Coloring drawings of bipartite graphs: A problem in automated assembly (Q1208463)

The ``problem in automated assembly'' which motivates the results obtained in this paper is the following. There are \(m\) vehicles, each tethered to its own base by a tether which can be of any length but must be a straight line, and there are \(n\geq m\) stations, and all these objects lie on a plane. Each vehicle must visit each station in such a way that at each of \(n\) moments of time all the vehicles are simultaneously visiting different stations and no two tethers cross. This leads to the problem of finding rectilinear plane drawings of the complete bipartite graph \(K_{m,n}\) whose edges can be colored with \(n\) colors so that no two edges of the same color intersect (even in a vertex). Two such colorable drawings are isomorphic if their vertices can be labelled in such a way that edge-crossings correspond. The following results are obtained. Up to isomorphism, there is exactly one colorable drawing of \(K_{2,2}\), two of \(K_{2,3}\) and three of \(K_{3,3}\). These colorable drawings of \(K_{3,3}\) are generalized to three nonisomorphic colorable drawings of \(K_{m,n}\), \(n\geq m\geq 3\), but whether any more of them exist is an open question. Finally, a necessary and sufficient condition is given for a drawing of \(K_{2,n}\) to be colorable.