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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Find Routes on a Doughnut

  • Yasuko Matsui,
  • Shin-ichi Nakano

摘要

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.