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 orientation algorithm.
Is it possible to compute the determinant also in linear time?
Note that if we explicitly write down the matrix with Pfaffian orientation we need $\Omega(|V|^2)$ space to write down the matrix. But since number of edges is only $O(|V|)$ we might be able to get away with linear time algorithm for counting number of perfect matchings of a planar graph. Is this possible?
If $M\in\{-1,0,+1\}^{n\times n}$ be a matrix with only $O(n)$ non-zero entries and hadamard product $M\odot M$ being symmetric can we compute $Det(M)$ in $O(n)$ bit complexity?
Assume that the matrix is given in form a list where $1,-1$ locations are and so the presentation is only $O(n)$ sized.
The motivation comes from possibility of counting $\#$ of perfect matchings in planar graphs in linear time?
First of all $\#$ of perfect matchings can be written down in $O(n)$ bits for planar graphs.
Secondly given adjacency matrix $A$ we can find MST in linear time for planar graphs.
Thirdly from MST we can find a pfaffian orientation and find $M\in\{-1,0,+1\}^{n\times n}$ in linear time (So $M\odot M=A$).
So it seems highly plausible it should be the case that $\#$ of perfect matchings on planar graph should be computable in linear time with $O(n)$ bit complexity.
However if we use $Det(M)$ directly we cannot avoid $O(n^2)$ at best. But there may be an indirect way to compute $Det(M)$.
