TY - GEN
T1 - One-way trail orientations
AU - Aamand, Anders
AU - Hjuler, Niklas
AU - Holm, Jacob
AU - Rotenberg, Eva
PY - 2018/7/1
Y1 - 2018/7/1
N2 - Given a graph, does there exist an orientation of the edges such that the resulting directed graph is strongly connected? Robbins' theorem [Robbins, Am. Math. Monthly, 1939] asserts that such an orientation exists if and only if the graph is 2-edge connected. A natural extension of this problem is the following: Suppose that the edges of the graph are partitioned into trails. Can the trails be oriented consistently such that the resulting directed graph is strongly connected? We show that 2-edge connectivity is again a su cient condition and we provide a linear time algorithm for finding such an orientation. The generalised Robbins' theorem [Boesch, Am. Math. Monthly, 1980] for mixed multigraphs asserts that the undirected edges of a mixed multigraph can be oriented to make the resulting directed graph strongly connected exactly when the mixed graph is strongly connected and the underlying graph is bridgeless. We consider the natural extension where the undirected edges of a mixed multigraph are partitioned into trails. It turns out that in this case the condition of the generalised Robbin's Theorem is not su cient. However, we show that as long as each cut either contains at least 2 undirected edges or directed edges in both directions, there exists an orientation of the trails such that the resulting directed graph is strongly connected. Moreover, if the condition is satisfied, we may start by orienting an arbitrary trail in an arbitrary direction. Using this result one obtains a very simple polynomial time algorithm for finding a strong trail orientation if it exists, both in the undirected and the mixed setting.
AB - Given a graph, does there exist an orientation of the edges such that the resulting directed graph is strongly connected? Robbins' theorem [Robbins, Am. Math. Monthly, 1939] asserts that such an orientation exists if and only if the graph is 2-edge connected. A natural extension of this problem is the following: Suppose that the edges of the graph are partitioned into trails. Can the trails be oriented consistently such that the resulting directed graph is strongly connected? We show that 2-edge connectivity is again a su cient condition and we provide a linear time algorithm for finding such an orientation. The generalised Robbins' theorem [Boesch, Am. Math. Monthly, 1980] for mixed multigraphs asserts that the undirected edges of a mixed multigraph can be oriented to make the resulting directed graph strongly connected exactly when the mixed graph is strongly connected and the underlying graph is bridgeless. We consider the natural extension where the undirected edges of a mixed multigraph are partitioned into trails. It turns out that in this case the condition of the generalised Robbin's Theorem is not su cient. However, we show that as long as each cut either contains at least 2 undirected edges or directed edges in both directions, there exists an orientation of the trails such that the resulting directed graph is strongly connected. Moreover, if the condition is satisfied, we may start by orienting an arbitrary trail in an arbitrary direction. Using this result one obtains a very simple polynomial time algorithm for finding a strong trail orientation if it exists, both in the undirected and the mixed setting.
KW - Graph algorithms
KW - Graph orientation
KW - Robbins' theorem
UR - http://www.scopus.com/inward/record.url?scp=85049793618&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ICALP.2018.6
DO - 10.4230/LIPIcs.ICALP.2018.6
M3 - Article in proceedings
AN - SCOPUS:85049793618
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018
A2 - Kaklamanis, Christos
A2 - Marx, Daniel
A2 - Chatzigiannakis, Ioannis
A2 - Sannella, Donald
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018
Y2 - 9 July 2018 through 13 July 2018
ER -