I was studying finding a pfaffian orientation of a planar graph in $NC$. In Vazirani's Paper on NC Algorithms for Computing the Number of Perfect Matchings in $K_{3,3}$-Free Graphs and Related Problems he has shown an algorithm to find a pfaffian orientation. So his algorithm is:
- Take a spanning tree $T$ of the planer graph.
- Then create a graph $H$ where $V(H)$ is the faces of $G$ and two vertices of $H$ are connected if the corresponding faces share an edge that is not in $T$. $H$ will be a tree where the external infinite face will be the root. Denote it with $r$.
- Then orient $T$ arbitrarily
- The rooted tree $H$ dictates the order in which the rest of the edges of $G$ will be oriented. The orientation starts with the faces corresponding to the leaves of $H$, and moves up to $r$. Let $e$ be the edge in $G$ corresponding to the edge $(u \to v)$ in $H$ (assuming that all edges in $H$ are directed away from the root). Let $f$ be the face in $G$ corresponding to $u$. Assume that the faces corresponding to all descendants of $v$ have already been oriented. Then, $e$ is the only unoriented edge in $f$ Now orient $e$ so that $f$ has an odd number of edges oriented clockwise.
Now this means any two faces if they are joined by an edge then they share only one edge apart from the tree. How is this true? Also, how can we even say that if the subgraph is rooted at any vertex all the faces for the vertices in that subgraph are already oriented then we can orient that vertex? I get the feeling that it should be and the leaves are all the faces which are all surrounded by the tree edges and only one edge shared with another face. But I can't prove that is the case.
