An st-orientation of an undirected graph is an assignment of a direction for each edge, turning it into a directed acyclic graph with one source and one sink. For any biconnected graph such an orientation may be found in linear time via depth first search: For each DFS tree edge $$(u,v)$$ (where $$u$$ is the parent), orient $$(u,v)$$ oppositely to the DFS tree edge down from the low vertex of $$v$$ into the subtree containing $$u$$ and $$v$$. For each nontree edge $$(u,v)$$ (where $$u$$ is the top vertex), orient $$(u,v)$$ the same as the DFS tree edge down from $$u$$ into the subtree containing $$v$$. I've been meaning to add this to PADS for a while, after lecturing on it as part of the graph drawing section of my undergraduate graph algorithms class this quarter, but it's now there (in Biconnectivity.py) after I found motivation in a connection to xyz graph recognition:

Any biconnected 3-regular graph can be partitioned in at most $$2^{n/2-1}$$ different ways into three matchings. The idea of the proof is to process the vertices in a topological ordering (also added to PADS, in TopologicalOrder.py) of an st-orientation, and when processing each vertex choose how to assign the adjacent edges to the three matchings, consistently with prior choices. We only have to make a binary choice at the $$n/2-1$$ vertices with one incoming and two outgoing edges; at all other vertices there is no choice to be made. This leads to an $$O(n 2^{n/2})$$ time algorithm for recognizing xyz graphs, which I implemented as part of PADS in xyzGraph.py.

My implementation tells me that the xyz graph representation of the permutohedron is essentially unique: we can permute the values of any coordinate, but we always have the same partition of the permutohedron's edges into three parallel classes. I still don't know of a graph with multiple representations, but I haven't searched very hard for one. My implementation also tells me that, sadly, the only known nonplanar cubic partial cube (formed by the 20 subsets of two and three items of a five-item set, adjacent when two subsets differ in a single item) is not an xyz graph.

Finally, Greg Kuperberg supplied an example proving that the $$2^{n/2-1}$$ bound on the number of partitions into three matchings is nearly tight: a prism over an $$n/2$$-vertex polygon has $$n$$ vertices and $$\Omega(2^{n/2})$$ partitions. So any improvement to the xyz graph recognition algorithm is going to need to use some more structure somehow...