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