An orientation of a static graph is called transitive if for any three vertices $a, b, c$, the presence of arcs $(a,b)$ and $(b,c)$ necessitates the presence of arc $(a,c)$. If only the presence of an arc between $a$ and $c$ is required, but its orientation is unconstrained, the orientation is termed quasi-transitive. A fundamental result by Ghouila-Houri guarantees that any static graph that admits a quasi-transitive orientation also admits a transitive orientation. Mertzios et al. introduced the notion of temporal transitivity to model information flows in simple temporal networks.
We revisit the model proposed by Mertzios et al. and suggest an analogous characterization for the temporal scenario similar to Ghouila-Houri's. We present a structural theorem that enables us to express all constraints imposed by temporal transitive orientations using a 2-SAT formula, resulting in an efficient recognition algorithm for graphs that permit such orientations.
Furthermore, we extend the temporal transitivity model to temporal graphs with multiple time labels associated with their edges, asserting that previous results hold in the multilabel context. Finally, we propose a characterization of temporal comparability graphs through forbidden temporal ordered patterns.
Blogger's Review: This paper delves into the transitivity of temporal graphs, presenting a novel structural theorem that leverages 2-SAT formulas for efficient recognition. This advancement not only enriches the theoretical framework of comparability graphs but also offers new insights for managing information flows in complex temporal networks, showcasing potential practical applications.