@techreport{oai:ipsj.ixsq.nii.ac.jp:00072909,
 author = {Yasuaki, Kobayashi and Yuichiro, Miyamoto and Hisao, Tamaki and Yasuaki, Kobayashi and Yuichiro, Miyamoto and Hisao, Tamaki},
 issue = {6},
 month = {Feb},
 note = {An orientation of an undirected graph G is a directed graph, with same vertex set, whose underlying graph is G. For integer k ≥ 3, we say a directed graph D is k-cyclic if every edge of D belongs to a directed cycle in D of length at most k. We consider the problem of deciding if a given graph has a k-cyclic orientation. We show that this problem is NP-complete for every fixed k ≥ 3 for general graphs and for every fixed k ≥ 4 for planar graphs. We give a polynomial time algorithm for planar graphs with k = 3, which constructs a 3-cyclic orientation when the answer is affirmative., An orientation of an undirected graph G is a directed graph, with same vertex set, whose underlying graph is G. For integer k ≥ 3, we say a directed graph D is k-cyclic if every edge of D belongs to a directed cycle in D of length at most k. We consider the problem of deciding if a given graph has a k-cyclic orientation. We show that this problem is NP-complete for every fixed k ≥ 3 for general graphs and for every fixed k ≥ 4 for planar graphs. We give a polynomial time algorithm for planar graphs with k = 3, which constructs a 3-cyclic orientation when the answer is affirmative.},
 title = {<i>k</i>-cyclic Orientations of Graphs},
 year = {2011}
}