In graph theory, a branch of mathematics, a skew-symmetric graph is a directed graph that is isomorphic to its own transpose graph, the graph formed by reversing all of its edges, under an isomorphism that is an involution without any fixed points. Skew-symmetric graphs are identical to the double covering graphs of bidirected graphs. Skew-symmetric graphs were first introduced under the name of antisymmetrical digraphs by Tutte (1967), later as the double covering graphs of polar graphs by Zelinka (1976b), and still later as the double covering graphs of bidirected graphs by Zaslavsky (1991). 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.
Definition As defined, e.g., by Goldberg & Karzanov (1996), a skew-symmetric graph G is a directed graph, together with a function σ mapping vertices of G to other vertices of G, satisfying the following properties:
For every vertex v, σ(v) ≠ v, For every vertex v, σ(σ(v)) = v, For every edge (u,v), (σ(v),σ(u)) must also be an edge. One may use the third property to extend σ to an orientation-reversing function on the edges of G. The transpose graph of G is the graph formed by reversing every edge of G, and σ defines a graph isomorphism from G to its transpose. However, in a skew-symmetric graph, it is additionally required that the isomorphism pair each vertex with a different vertex, rather than allowing a vertex to be mapped to itself by the isomorphism or to group more than two vertices in a cycle of isomorphism. A path or cycle in a skew-symmetric graph is said to be regular if, for each vertex v of the path or cycle, the corresponding vertex σ(v) is not part of the path or cycle.
Examples Every directed path graph with an even number of vertices is skew-symmetric, via a symmetry that swaps the two ends of the path. However, path graphs with an odd number of vertices are not skew-symmetric, because the orientation-reversing symmetry of these graphs maps the center vertex of the path to itself, something that is not allowed for skew-symmetric graphs. 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.
Polar/switch graphs, double covering graphs, and bidirected graphs A skew-symmetric graph may equivalently be defined as the double covering graph of a polar graph or switch graph, which is an undirected graph in which the edges incident to each vertex are partitioned into two subsets. Each vertex of the polar graph corresponds to two vertices of the skew-symmetric graph, and each edge of the polar graph corresponds to two edges of the skew-symmetric graph. This equivalence is the one used by Goldberg & Karzanov (1996) to model problems of matching in terms of skew-symmetric graphs; in that application, the two subsets of edges at each vertex are the unmatched edges and the matched edges. Zelinka (following F. Zitek) and Cook visualize the vertices of a polar graph as points where multiple tracks of a train track come together: if a train enters a switch via a track that comes in from one direction, it must exit via a track in the other direction. 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. and may be modeled as the search for a regular path in a skew-symmetric graph. A closely related concept is the bidirected graph or polarized graph, a graph in which each of the two ends of each edge may be either a head or a tail, independently of the other end. A bidirected graph may be interpreted as a polar graph by letting the partition of edges at each vertex be determined by the partition of endpoints at that vertex into heads and tails; however, swapping the roles of heads and tails at a single vertex ("switching" the vertex) produces a different bidirected graph but the same polar graph. To form the double covering graph (i.e., the corresponding skew-symmetric graph) from a polar graph G, create for each vertex v of G two vertices v0 and v1, and let σ(vi) = v1 − i. For each edge e = (u,v) of G, create two directed edges in the covering graph, one oriented from u to v and one oriented from v to u. If e is in the first subset of edges at v, these two edges are from u0 into v0 and from v1 into u1, while if e is in the second subset, the edges are from u0 into v1 and from v0 into u1. In the other direction, given a skew-symmetric graph G, one may form a polar graph that has one vertex for every corresponding pair of vertices in G and one undirected edge for every corresponding pair of edges in G. The undirected edges at each vertex of the polar graph may be partitioned into two subsets according to which vertex of the polar graph they go out of and come into. 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.
… excerpt ends here. Continue reading the full article.
