Towards the Recognition of Oriented Interval Graphs
2026-07-06 • Computational Geometry
Computational GeometryDiscrete Mathematics
AI summaryⓘ
The authors study a type of graph called oriented interval graphs, where intervals have directions and overlap in specific ways to form edges. They analyze how three key parts—interval directions, orderings of cliques, and containment edges—affect each other in these graphs. Using their insights, they create efficient algorithms that can recognize certain types of these graphs much faster than before. Their work also solves recognition for oriented proper or unit interval graphs, which are important special cases.
oriented interval graphinterval graphmixed graphclique orderingcontainment edgeinterval orientationgraph recognitionproper interval graphunit interval graphintersection graph
Authors
Lukas P. Bachmann, Jiří Fiala, Miriam Münch, Ignaz Rutter, Peter Stumpf, Alexander Wolff
Abstract
Oriented interval graphs, a recent generalization of interval graphs introduced by Gutowski et al. [GD 2022], are intersection graphs of intervals, each of which is oriented either left or right. Such a representation defines a mixed intersection graph: overlapping intervals with the same orientation define a (directed) arc; nested intervals (irrespective of the orientations of the intervals) and overlapping intervals of opposite orientations define an (undirected) edge. An oriented interval representation of a mixed graph $G$ can be described combinatorially by the combination of (i) an orientation $\varphi \colon V(G) \to \{-1,1\}$ of all intervals, (ii) a clique ordering $σ$, and (iii) a set $E_\mathrm{cont} \subseteq E(G)$ of containment edges, which are represented by nested intervals. The non-trivial dependencies between these three ingredients make the recognition of oriented interval graphs a challenging problem. In this paper, we take steps towards a general recognition algorithm by studying how orientation, clique ordering, and containment edges influence and restrict each other. We characterize the orientations that are consistent with a given set of containment edges as well as the clique orderings that are consistent with a given orientation. Based on these characterizations, we give linear-time algorithms for two constrained versions of the recognition problem where, in addition to the mixed input graph $G$, either the set of containment edges $E_\mathrm{cont}$ or the orientation $\varphi$ is prescribed. This improves a quadratic-time algorithm of Gutowski et al. for the case that all vertices have the same orientation; an assumption that determines both the orientation and the containment edges. In particular, this also solves the recognition problem for oriented proper (or unit) interval graphs.