2026-08-25T18:47:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27282 2026-08-25T13:18:20Z ddc:004 open_access

Towards the Recognition of Oriented Interval Graphs Bachmann, Lukas P. Fiala, Jiří Münch, Miriam Rutter, Ignaz Stumpf, Peter Wolff, Alexander Interval graphs mixed graphs oriented interval graphs recognition 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 φ : V(G) → {-1,1} of all intervals, (ii) a clique ordering σ, and (iii) a set E_cont ⊆ 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_cont or the orientation φ 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Lukas P. Bachmann and Jiří Fiala and Miriam Münch and Ignaz Rutter and Peter Stumpf and Alexander Wolff 2026 Is Part Of LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2026.146 urn:nbn:de:0030-drops-272825 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.146 eng https://creativecommons.org/licenses/by/4.0/legalcode