Towards the Recognition of Oriented Interval Graphs

Alexander Wolff; Ignaz Rutter; Ji\v{r}\'i Fiala; Lukas P. Bachmann; Miriam M\"unch; Peter Stumpf

Towards the Recognition of Oriented Interval Graphs

T0 review · reviewed 2026-07-08 · glm-5.2

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Linear-time recognition of oriented interval graphs

desk verdict Two linear-time recognition algorithms for constrained oriented interval graphs; the general problem stays open read the letter →

arxiv 2607.05191 v1 pith:W53YWHAF submitted 2026-07-06 cs.CG cs.DM

Lukas P. Bachmann , Jiří Fiala , Miriam Münch , Ignaz Rutter , Peter Stumpf , Alexander Wolff This is my paper · ORCID

classification cs.CGcs.DM

keywords intervalsorientationgraphsintervalorientedcontainmentedgesrecognition

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper studies the recognition of oriented interval graphs — intersection graphs of intervals on the line where each interval is oriented left or right, producing a mixed graph with both directed arcs and undirected edges. The authors prove two main results. First, given a mixed graph G and a prescribed set of containment edges E_cont, there is a linear-time algorithm deciding whether G admits an oriented interval representation where precisely those edges are represented by interval containment (Theorem 1). Second, given G and a prescribed orientation phi, there is a linear-time algorithm deciding whether G admits an oriented interval representation with that orientation (Theorem 3). Both results improve a prior quadratic-time algorithm and, as a corollary, solve the recognition problem for oriented proper (or unit) interval graphs in linear time.

What carries the argument

oriented interval representation, mixed graph, containment edges, clique ordering, orientation, permutation graph, matching representation, MPQ-tree, modular decomposition

What would settle it

A family of mixed graphs where the augmented containment graph H+ has a super-linear number of edges, which would break the linear-time complexity argument for the matching representation algorithm.

Watch

Extended reading notes

Core claim

The central mechanism is a structural decomposition of the three interdependent parameters of an oriented interval representation — orientation phi, clique ordering sigma, and containment edge set E_cont — into pairwise consistency conditions. For prescribed containment edges, the authors show that a feasible orientation is determined component-wise in G minus E_cont (unique up to reversal per connected component), and the remaining question reduces to a constrained matching representation problem on the complement of an augmented containment graph H+, solvable in linear time via modular decomposition. For prescribed orientation, the authors characterize which clique orderings are consistent

Load-bearing premise

The linear-time complexity claim for Theorem 1 depends on the augmented containment graph H+ having edge count bounded by O(|V|+|E|+|E_arrow|), which ensures the complement graph is not too dense for the modular decomposition step to run in linear time.

Editorial extensions

If this is right

Oriented proper and oriented unit interval graphs can now be recognized in linear time, settling the computational complexity of these graph classes.
The structural characterizations of how orientation, clique ordering, and containment edges constrain each other provide a roadmap for the general recognition problem where none of the three parameters is prescribed.
The constrained matching representation framework on augmented containment graphs may extend to other intersection graph classes involving nested or directed geometric objects.
The linear-time algorithms make oriented interval graph recognition practical for large-scale inputs in scheduling or network visualization contexts where mixed directed/undirected relationships arise.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Desk Editor's Note

read the letter

This paper solves two constrained recognition problems for oriented interval graphs in linear time: given a mixed graph with prescribed containment edges (Theorem 1), and given a mixed graph with prescribed orientation (Theorem 3). Both improve on prior work — Theorem 1 generalizes and speeds up a quadratic algorithm of Gutowski et al. (GD 2022), and Theorem 3 solves the proper/unit case as a corollary. The general recognition problem remains open, and the authors are honest about that. This is solid, well-executed work within its subfield. The structural characterizations are the real contribution: the description of feasible orientations via component-wise uniqueness up to reversal (Lemma 7), the reduction to constrained matching representations on the augmented containment graph H+ (Theorem 10), and the MPQ-tree constraints for clique orderings consistent with a given orientation (Lemma 12/18). The proofs are careful — necessity and sufficiency are argued separately, Example 14 explicitly shows Lemma 8's conditions are necessary but not sufficient, and the full proofs in the appendix are detailed. The linear-time claim for Theorem 1 initially looks suspicious because the complement of H+ could be dense. But the stress-test concern does not land: the algorithm never constructs the complement. It works with H+ directly via modular decomposition (Lemma 16), and the size bounds on E+_cont and the constraint set Gamma are justified by standard interval graph clique structure. The one spot that deserves scrutiny is the 'routine case analysis' in Theorem 10 claiming the union of the two transitive orientations is a total order. This is not automatic for arbitrary transitive orientations of a graph and its complement, but the argument works because the algorithm finds a single matching representation that simultaneously defines both orientations, which forces the union to be total. This could be stated more explicitly in the main text rather than left to the reader. The MPQ-tree constraint propagation in Section 4 is the densest part of the paper and the hardest to follow, but the proof structure is sound. This is for researchers working on intersection graph recognition and combinatorial algorithms. It deserves a serious referee who can verify the appendix proofs in detail, particularly the normalized representation argument (Lemma 19/Corollary 20) and the linear-time MPQ-tree construction (Lemma 21).

Referee Report

0 major / 0 minor

Summary. This paper studies the recognition problem for oriented interval graphs, a class of mixed intersection graphs introduced by Gutowski et al. (GD 2022). An oriented interval representation assigns each interval a left or right orientation; overlapping same-orientation intervals yield arcs, while nested intervals and opposite-orientation overlaps yield undirected edges. The representation is determined combinatorially by a triple (φ, σ, E_cont) — orientation, clique ordering, and containment edges — whose mutual dependencies make recognition nontrivial. The authors characterize (i) orientations φ consistent with a given E_cont (Lemma 7) and (ii) clique orderings σ consistent with a given φ (via MPQ-tree constraints, Lemma 12). These yield two main algorithmic results: Theorem 1 gives a linear-time algorithm to decide whether G admits an oriented interval representation with prescribed containment edges E_cont (including E_cont = ∅, i.e., oriented proper/unit interval recognition, as Corollary 2), and Theorem 3 gives a linear-time algorithm for prescribed orientation φ. Both improve on the quadratic algorithm of Gutowski et al. for the uniform-orientation case. The key technical tools are augmented graphs G⁺, permutation graph characterizations (Theorem 10), constrained matching representations solved via modular decomposition (Lemma 16), and MPQ-tree rotations with a normalization step (Corollary 20).

Significance. The paper makes a solid contribution to the structural and algorithmic theory of oriented interval graphs. The linear-time algorithms for two constrained recognition variants (Theorems 1 and 3) constitute genuine progress over the quadratic algorithm of Gutowski et al. [13], and Corollary 2 (oriented proper/unit interval recognition) is a clean corollary. The reduction to constrained matching representations on permutation graphs via the augmented graph G⁺ (Theorem 10, Lemma 16) is an elegant use of modular decomposition. The MPQ-tree constraint framework for Section 4 (Lemmas 18–19, Corollary 20) is well-motivated and the normalization argument is carefully structured. Full proofs are provided in the appendix for all starred lemmas and theorems. The complexity argument that H⁺ is not too dense (|E⁺_cont| ≤ |V|+|E|+|E⃗|, |Γ| ∈ O(|E|+|E⃗|)) is correct: the algorithm operates on H⁺ directly rather than its complement, and the bound follows from the structure of maximal cliques in interval graphs.

Simulated Author's Rebuttal

2 responses · 0 unresolved

The referee report is highly positive, recommending minor revision with no specific major comments. The referee accurately summarizes the paper's contributions (Theorems 1 and 3, Corollary 2), validates the technical approach (augmented graph G+, permutation graph characterization, MPQ-tree constraints, modular decomposition), and confirms the complexity arguments. We thank the referee and note that no substantive changes are required.

read point-by-point responses

Referee: Overall assessment and recommendation of minor revision

Authors: We thank the referee for the careful and accurate reading of our manuscript. The summary correctly captures the structure of our two main algorithmic results (Theorems 1 and 3), the role of the augmented graph G+ and the permutation graph characterization (Theorem 10), the constrained matching representation framework solved via modular decomposition (Lemma 16), and the MPQ-tree constraint framework (Lemmas 18–19, Corollary 20). We are pleased that the referee finds the complexity argument regarding the density of H+ correct, as this was a subtle point in our proof: the algorithm operates on H+ directly rather than its complement, and the bound |E+_cont| ≤ |V|+|E|+|E⃗| follows from the structure of maximal cliques in interval graphs. revision: no
Referee: No major comments raised

Authors: Since the referee did not raise any specific major comments, we will use the opportunity to perform a careful proofreading pass on the manuscript to address any minor typographical or expositional issues before the final version. No substantive changes to the results, proofs, or algorithms are needed. revision: partial

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found; the paper is a self-contained algorithmic contribution.

full rationale

The paper's derivation chain is self-contained. The main characterization results (Theorem 10 on transitive orientations of H+ and its complement; Lemma 12/18 on φ-consistent clique orders via MPQ-tree constraints) are proved directly in the paper without reducing to self-cited premises. The linear-time implementation (Lemma 16) cites [18] (Münch, Rutter, Stumpf, Algorithmica 2024) for the constrained matching representation algorithm on permutation graphs via modular decomposition. While Rutter and Stumpf are co-authors of both papers, [18] is a published, peer-reviewed algorithm used as a black box with explicitly stated complexity O(|V|+|E|+|Γ|) and assumptions (permutation graph input, constraint set) that do not include the target result of the present paper. The complexity bound on H+ in Theorem 1's proof (|E+_cont| ≤ |V|+|E|+|E⃗|, |Γ| ∈ O(|E|+|E⃗|)) follows from standard interval graph properties (each edge appears in at least one maximal clique, each vertex in at least one) and is argued directly. Theorem 3 legitimately reduces to Corollary 11 (a variant of Theorem 1) by splitting the graph into same-orientation subgraphs — this is a standard algorithmic reduction, not circularity. No step reduces to its own inputs by construction.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The paper introduces no free parameters, no ad-hoc axioms, and no invented entities. All background results are standard or cited from prior literature. The augmented graph G+ and clique point vertices are constructions internal to the algorithm, not new mathematical entities postulated to exist.

assumptions (5)

standard math A mixed graph G is an interval graph if and only if its maximal cliques admit a linear ordering where cliques containing each vertex are consecutive (Fulkerson-Gross).
Section 2, used to define clique orders and PQ-trees.
standard math The modular decomposition of a graph can be computed in O(|V|+|E|) time and yields a unique tree with empty/complete/prime quotient graphs.
Section B.1, used for the linear-time algorithm in Lemma 16.
standard math A permutation graph admits only four distinct matching representations when its modular decomposition root is prime.
Section B.1, Lemma 16 proof, citing [18].
standard math MPQ-trees correctly represent all clique orders of an interval graph with the stated vertex assignment properties (Proposition 17).
Section 4, Proposition 17, citing Korte and Möhring [16].
standard math The partial transitive orientation extension problem can be solved in O(n+m) time.
Section 3.2, proof of Theorem 1, citing [18].

how reviews work

0 comments

Cite this review

Pith. "Pith review of Towards the Recognition of Oriented Interval Graphs." pith.science (2026). https://pith.science/paper/W53YWHAF

@misc{pith2026260705191,
  author       = {Pith},
  title        = {Pith review of: Towards the Recognition of Oriented Interval Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/W53YWHAF}},
  note         = {Machine review of arXiv:2607.05191}
}

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 $\sigma$, 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.

Figures

Figures reproduced from arXiv: 2607.05191 by the authors.

**Figure 12.** (a) Assignment of matching representations to the quotient graphs in T. (b) The corresponding matching representations for H[Mµ] and H[Mν]. (c) The matching representation of H composed from the matching representations of the quotient graphs. a matching representation of H is equivalent to the simultaneous choice of a representation for the quotient graph Hµ for each node µ in T. For each node µ in T let Dµ denote … view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

21 extracted references · 21 canonical work pages

[13]

Coloring Mixed and Directional Interval Graphs

Grzegorz Gutowski, Florian Mittelst \"a dt, Ignaz Rutter, Joachim Spoerhase, Alexander Wolff, and Johannes Zink. Coloring mixed and directional interval graphs. In Patrizio Angelini and Reinhard von Hanxleden, editors, Proc. 30th Int. Symp. Graph Drawing & Network Vis. (GD'22) , volume 13764 of LNCS , pages 418--431. Springer, 2023. URL: https://arxiv.org...

work page Pith review arXiv doi:10.1007/978-3-031-22203-0_30 2023
[1]

Completing orientations of partially oriented graphs

J rgen Bang - Jensen, Jing Huang, and Xuding Zhu. Completing orientations of partially oriented graphs. J. Graph Theory , 87(3):285--304, 2018. https://doi.org/10.1002/jgt.22157 doi:10.1002/jgt.22157

work page doi:10.1002/jgt.22157 2018
[2]

Computing quasi-upward planar drawings of mixed graphs

Carla Binucci and Walter Didimo. Computing quasi-upward planar drawings of mixed graphs. Comput. J. , 59(1):133--150, 2016. https://doi.org/10.1093/comjnl/bxv082 doi:10.1093/comjnl/bxv082

work page doi:10.1093/comjnl/bxv082 2016
[3]

Upward and quasi-upward planarity testing of embedded mixed graphs

Carla Binucci, Walter Didimo, and Maurizio Patrignani. Upward and quasi-upward planarity testing of embedded mixed graphs. Theor. Comput. Sci. , 526:75--89, 2014. https://doi.org/10.1016/J.TCS.2014.01.015 doi:10.1016/J.TCS.2014.01.015

work page doi:10.1016/j.tcs.2014.01.015 2014
[4]

Booth and George S

Kellogg S. Booth and George S. Lueker. Testing for the consecutive ones property, interval graphs, and graph planarity using PQ -tree algorithms. J. Comput. Syst. Sci. , 13(3):335--379, 1976. https://doi.org/10.1016/S0022-0000(76)80045-1 doi:10.1016/S0022-0000(76)80045-1

work page doi:10.1016/s0022-0000(76)80045-1 1976
[5]

A recursive linear time modular decomposition algorithm via LexBFS

Derek Corneil, Michel Habib, Christophe Paul, and Marc Tedder. A recursive linear time modular decomposition algorithm via LexBFS . arXiv report, 2024. URL: https://arxiv.org/abs/0710.3901

work page Pith review arXiv 2024
[6]

Ben Dushnik and E. W. Miller. Partially ordered sets. Amer. J. Math. , 63(3):600--610, 1941. https://doi.org/10.2307/2371374 doi:10.2307/2371374

work page doi:10.2307/2371374 1941
[7]

Permutation graphs and transitive graphs

Shimon Even, Amir Pnueli, and Abraham Lempel. Permutation graphs and transitive graphs. J. ACM , 19:400--410, 1972. https://doi.org/10.1145/321707.321710 doi:10.1145/321707.321710

work page doi:10.1145/321707.321710 1972

Show all 21 references

[8]

T \' o th, and David R

Fabrizio Frati, Michael Kaufmann, J \' a nos Pach, Csaba D. T \' o th, and David R. Wood. On the upward planarity of mixed plane graphs. J. Graph Algorithms Appl. , 18(2):253--279, 2014. https://doi.org/10.7155/JGAA.00322 doi:10.7155/JGAA.00322

2014 doi
[9]

Fulkerson and Oliver Gross

Delbert R. Fulkerson and Oliver Gross. Incidence matrices and interval graphs. Pac. J. Math. , 15:835--855, 1965. https://doi.org/10.2140/pjm.1965.15.835 doi:10.2140/pjm.1965.15.835

1965 doi
[10]

Transitiv orientierbare Graphen

Tibor Gallai. Transitiv orientierbare Graphen . Acta Math. Hung. , 18(1--2):25--66, 1967. https://doi.org/10.1007/BF02020961 doi:10.1007/BF02020961

1967 doi
[11]

Garey, David S

Michael R. Garey, David S. Johnson, Gerald L. Miller, and Christos H. Papadimitriou. The complexity of coloring circular arcs and chords. SIAM J. Algebr. Discrete Meth. , 1(2):216--227, 1980. https://doi.org/10.1137/0601025 doi:10.1137/0601025

1980 doi
[12]

Golumbic

Martin C. Golumbic. Algorithmic Graph Theory and Perfect Graphs . Annals of Discrete Mathematics. North Holland, 2004. https://doi.org/10.1016/C2013-0-10739-8 doi:10.1016/C2013-0-10739-8

2004 doi
[14]

Mixed graph colorings

Pierre Hansen, Julio Kuplinsky, and Dominique de Werra. Mixed graph colorings. Math. Methods Oper. Res. , 45(1):145--160, 1997. https://doi.org/10.1007/BF01194253 doi:10.1007/BF01194253

1997 doi
[15]

Maximum weight clique algorithms for circular-arc graphs and circle graphs

Wen - Lian Hsu. Maximum weight clique algorithms for circular-arc graphs and circle graphs. SIAM J. Comput. , 14(1):224--231, 1985. https://doi.org/10.1137/0214018 doi:10.1137/0214018

1985 doi
[16]

Norbert Korte and Rolf H. Möhring. An incremental linear-time algorithm for recognizing interval graphs. SIAM J. Comput. , 18(1):68--81, 1989. https://doi.org/10.1137/0218005 doi:10.1137/0218005

1989 doi
[17]

McConnell and Jeremy P

Ross M. McConnell and Jeremy P. Spinrad. Modular decomposition and transitive orientation. Discret. Math. , 201(1-3):189--241, 1999. https://doi.org/10.1016/S0012-365X(98)00319-7 doi:10.1016/S0012-365X(98)00319-7

1999 doi
[18]

Partial and simultaneous transitive orientations via modular decompositions

Miriam M \" u nch, Ignaz Rutter, and Peter Stumpf. Partial and simultaneous transitive orientations via modular decompositions. Algorithmica , 86(4):1263--1292, 2024. https://doi.org/10.1007/S00453-023-01188-Y doi:10.1007/S00453-023-01188-Y

2024 doi
[19]

Fred S. Roberts. Indifference graphs. In Proof Techniques in Graph Theory: Proceedings of the 2nd Ann Arbor Graph Theory Conference , pages 139--146, 1969

1969
[20]

Yuri N. Sotskov. Mixed graph colorings: A historical review. Mathematics , 8(3):385, 2020. https://doi.org/10.3390/math8030385 doi:10.3390/math8030385

2020 doi
[21]

Sotskov and Vyacheslav S

Yuri N. Sotskov and Vyacheslav S. Tanaev. Chromatic polynomial of a mixed graph. Vestsi Akademii Navuk BSSR, Ser. Fiz. Mat. Navuk , 6:20--23, 1976

1976

Pith tools

Reviewed July 8, 2026 · model on record in the stance chip above.

[1] [13]

Coloring Mixed and Directional Interval Graphs

Grzegorz Gutowski, Florian Mittelst \"a dt, Ignaz Rutter, Joachim Spoerhase, Alexander Wolff, and Johannes Zink. Coloring mixed and directional interval graphs. In Patrizio Angelini and Reinhard von Hanxleden, editors, Proc. 30th Int. Symp. Graph Drawing & Network Vis. (GD'22) , volume 13764 of LNCS , pages 418--431. Springer, 2023. URL: https://arxiv.org...

work page Pith review arXiv doi:10.1007/978-3-031-22203-0_30 2023

[2] [1]

Completing orientations of partially oriented graphs

J rgen Bang - Jensen, Jing Huang, and Xuding Zhu. Completing orientations of partially oriented graphs. J. Graph Theory , 87(3):285--304, 2018. https://doi.org/10.1002/jgt.22157 doi:10.1002/jgt.22157

work page doi:10.1002/jgt.22157 2018

[3] [2]

Computing quasi-upward planar drawings of mixed graphs

Carla Binucci and Walter Didimo. Computing quasi-upward planar drawings of mixed graphs. Comput. J. , 59(1):133--150, 2016. https://doi.org/10.1093/comjnl/bxv082 doi:10.1093/comjnl/bxv082

work page doi:10.1093/comjnl/bxv082 2016

[4] [3]

Upward and quasi-upward planarity testing of embedded mixed graphs

Carla Binucci, Walter Didimo, and Maurizio Patrignani. Upward and quasi-upward planarity testing of embedded mixed graphs. Theor. Comput. Sci. , 526:75--89, 2014. https://doi.org/10.1016/J.TCS.2014.01.015 doi:10.1016/J.TCS.2014.01.015

work page doi:10.1016/j.tcs.2014.01.015 2014

[5] [4]

Booth and George S

Kellogg S. Booth and George S. Lueker. Testing for the consecutive ones property, interval graphs, and graph planarity using PQ -tree algorithms. J. Comput. Syst. Sci. , 13(3):335--379, 1976. https://doi.org/10.1016/S0022-0000(76)80045-1 doi:10.1016/S0022-0000(76)80045-1

work page doi:10.1016/s0022-0000(76)80045-1 1976

[6] [5]

A recursive linear time modular decomposition algorithm via LexBFS

Derek Corneil, Michel Habib, Christophe Paul, and Marc Tedder. A recursive linear time modular decomposition algorithm via LexBFS . arXiv report, 2024. URL: https://arxiv.org/abs/0710.3901

work page Pith review arXiv 2024

[7] [6]

Ben Dushnik and E. W. Miller. Partially ordered sets. Amer. J. Math. , 63(3):600--610, 1941. https://doi.org/10.2307/2371374 doi:10.2307/2371374

work page doi:10.2307/2371374 1941

[8] [7]

Permutation graphs and transitive graphs

Shimon Even, Amir Pnueli, and Abraham Lempel. Permutation graphs and transitive graphs. J. ACM , 19:400--410, 1972. https://doi.org/10.1145/321707.321710 doi:10.1145/321707.321710

work page doi:10.1145/321707.321710 1972