Acyclic Bidirected and Skew-Symmetric Graphs: Algorithms and Structure

摘要

Bidirected graphs (a sort of nonstandard graphs introduced by Edmonds and Johnson) provide a natural generalization to the notions of directed and undirected graphs. By a weakly acyclic bidirected graph we mean such a graph having no simple cycles. We call a bidirected graph strongly acyclic if it has no cycles (even non-simple). We present (generalizing results of Gabow, Kaplan, and Tarjan) a modification of the depth-first search algorithm that checks (in linear time) if a given bidirected graph is weakly acyclic (in case of negative answer a simple cycle is constructed). We use the notion of skew-symmetric graphs (the latter give another, somewhat more convenient graph language which is essentially equivalent to the language of bidirected graphs). We also give structural results for the class of weakly acyclic bidirected and skew-symmetric graphs explaining how one can construct any such graph starting from strongly acyclic instances and, vice versa, how one can decompose a weakly acyclic graph into strongly acyclic "parts". Finally, we extend acyclicity test to build (in linear time) such a decomposition.