Find Routes on a Doughnut
摘要
In this paper we consider a very restricted version of the drawing problem. Given a matching \(M=(U\cup V, E)\) as a bipartite graph, two concentric circles, the cyclic ordering of the vertices in U and the cyclic ordering of the vertices in V, we wish to draw M with the minimum number of edge crossings so that the vertices in U are on the smaller circle with the given cyclic ordering and the vertices in V are on the larger circle with the given cyclic ordering. We call the problem the doughnut routing problem. We design an \(\text {O}(n^3)\) time algorithm to solve the problem. The main idea of the algorithm is a reduction to a set of the minimum length generator sequence problems.