Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs

Chetan Gupta, Raghunath Tewari, Vimal Raj Sharma

We show that given an embedding of an $O(\log n)$ genus bipartite graph, one can construct an edge weight function in logarithmic space, with respect to which the minimum weight pe…