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.