All Questions

The slides here provide a way to get a pfaffian orientation from Minimum Spanning Tree. MST can be found in linear time if graph is planar and weights are $1$ and the slides give a linear time ...

Permanent of biadjacency of bipartite graphs is the number of perfect matchings. In the case of planar graphs we can obtain an orientation with sign changes and get away with computing the determinant ...

We can find Pfaffian orientation and take determinant to compute permanent in $O(n^\omega)$ time where $\omega$ is exponent of matrix multiplication. We know that permanent of $O(n)$ vertex planar ...