On a Conjecture for Parameterized st-Orientations
Resolves a conjecture from 2008/2010 for graph drawing researchers, showing the relationship between two orientation algorithms is not as expected.
The paper disproves a conjecture that MaxSTN always produces longer longest paths than MinSTN in st-orientations of biconnected graphs, by presenting a 9-vertex counterexample where MaxSTN gives length 6 and MinSTN gives length 7.
MaxSTN and MinSTN -- proposed by Papamanthou and Tollis (TCS 2008, JGAA 2010) -- are two algorithms for producing $st$-orientations of biconnected graphs with long and short longest paths respectively. Based on extensive experiments on planar and non-planar graphs of up to 5,000 nodes, it was conjectured that $\ell_{\max} \geq \ell_{\min}$ for every biconnected graph $G$, where $\ell_{\max}$ and $\ell_{\min}$ denote the longest-path lengths of the two orientations. This paper disproves this conjecture by exhibiting a biconnected graph on 9 vertices for which MaxSTN yields $\ell_{\max}=6$ while MinSTN yields $\ell_{\min}=7$, regardless of how ties are broken in either algorithm.