All Questions

Planar graph permanent can be reduced to determinants and so statistics should be amenable. Pick a uniformly random bipartite planar graph $G$ with $n$ vertices of each color and choose new additional ...

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 ...