Registered Data

[02271] Enumerate All Routes on a Doughnut

  • Session Time & Room : 2C (Aug.22, 13:20-15:00) @G304
  • Type : Contributed Talk
  • Abstract : We consider a following doughnut routing problem. Given a matching $M=(U \cap V,E)$ as a bipartite graph, two concentric circles, the cyclic ordering of the vertices in $U$ and $V$ , we wish to draw $M$ with the minimum number of edge crossings so that the vertices in $U ($resp. $V)$ are on the smaller $($resp. larger$)$ circle with the given cyclic ordering. We propose an enumerate algorithm for all optimal solutions of the problem.
  • Classification : 05C38
  • Format : Talk at Waseda University
  • Author(s) :
    • Yasuko Matsui (Tokai University)
    • Shin-ichi Nakano (Gunma University)