squaredirected

Squaredirected is a term used in graph theory to describe the square of a directed graph, a construction that augments a digraph by adding edges that connect vertices through short directed paths in the original graph. The resulting directed graph preserves the same set of vertices and expands the edge set to reflect two-step reachability, providing a compact encoding of immediate and two-step connections.

Formally, if G = (V, E) is a directed graph, its squaredirected graph G^2 = (V, E^2) has an arc (u, v) in E^2 whenever there exists a directed path from u to v of length at most two in G. Variants exist: some definitions include the original edges of G in E^2, while others include only edges corresponding to two-step paths. Some authors also consider the variant where only paths of length exactly two contribute new edges, excluding the original ones. In many treatments, the term square refers to this idea of a graph power applied to directed graphs.

Example: in a digraph with edges A→B and B→C, the squaredirected graph includes A→B and B→C from the original, and also A→C if the two-step path A→B→C is counted under the chosen convention.

Applications of squaredirected graphs appear in reachability analysis, routing and network design, and dataflow or dependency analysis, where two-step connections are relevant. Computation can be performed via standard graph algorithms or matrix representations, using boolean or arithmetic adjacency matrices to reflect two-step relations under the selected convention.

See also: graph power, transitive closure, directed graphs.