Skew-symmetric graph

They arise in modeling the search for alternating paths and alternating cycles in algorithms for finding matchings in graphs, in testing whether a still life pattern in Conway's Game of Life may be partitioned into simpler components, in graph drawing, and in the implication graphs used to efficiently solve the 2-satisfiability problem.

Similarly, a directed cycle graph is skew-symmetric if and only if it has an even number of vertices.

In this case, the number of different mappings σ that realize the skew symmetry of the graph equals half the length of the cycle.

The problem of finding non-self-intersecting smooth curves between given points in a train track comes up in testing whether certain kinds of graph drawings are valid.

A regular path or cycle of a skew-symmetric graph corresponds to a path or cycle in the polar graph that uses at most one edge from each subset of edges at each of its vertices.

Goldberg & Karzanov (1996) generalized alternating path algorithms to show that the existence of a regular path between any two vertices of a skew-symmetric graph may be tested in linear time.

Along with the path problems arising in matchings, skew-symmetric generalizations of the max-flow min-cut theorem have also been studied.

Similar bridge-removal techniques in the context of matching were previously considered by Gabow, Kaplan & Tarjan (1999).

An instance of the 2-satisfiability problem, that is, a Boolean expression in conjunctive normal form with two variables or negations of variables per clause, may be transformed into an implication graph by replacing each clause

As Aspvall, Plass & Tarjan (1979) showed, a satisfying assignment to the 2-satisfiability instance is equivalent to a partition of this implication graph into two subsets of vertices, S and σ(S), such that no edge starts in S and ends in σ(S).

The total time for testing strong connectivity and finding a partition of the implication graph is linear in the size of the given 2-CNF expression.