REVIEW 2 major objections 3 minor 30 references
Simultaneous Representation of Proper and Unit Interval Graphs
T0 review · 2 major / 3 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read Simultaneous proper interval graphs with a shared induced subgraph are recognizable in linear time, unit versions in $O(|V|\cdot|E|)$ time, and both are NP-complete without the shared subgraph.
desk verdict The proper-interval half of this paper is good; the unit-interval half is not reliable as written, because Theorem 8 is false as stated. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The machinery is a chain of order-theoretic translations. PQ-trees encode all linear orders (fine enumerations) of each $G_i$; projecting them to the shared graph $S$ and intersecting the projections tests simultaneous proper interval representability. For the unit step, the paper introduces chains and bars: a $(u,v)$-chain is an ordered path from $u$ to $v$ inside one $G_i$, and a $(u,v)$-bar is an ordered independent set between them; a chain-bar conflict occurs when, for shared vertices $u,v$, one graph contributes a chain and another contributes a bar of the same size, making unit-length placement impossible. Scouting and zipping are two sweeps that extend the partial order induced by the simultaneous enumeration into a left-closed linear order, which is exactly a fine enumeration of a sandwich graph $H$ containing every $G_i$ as an induced subgraph; unit intervals are read off from that fine enumeration. The set of all possible simultaneous enumerations is described combinatorially by reversals of loose components organized into independent components and reversible parts.
What would settle it
Enumerate all connected sunflower graphs with, say, up to nine vertices and three input graphs, and compare the algorithm's verdict with an exact unit-interval checker that solves the linear program for equal-length intervals (or uses rational placement). One instance where the algorithm says 'yes' but no unit drawing exists, or says 'no' while a drawing exists, would refute the Theorem 13 characterization.
Extended reading notes
Core claim
The central claim is a characterization-then-algorithm story. A sunflower simultaneous graph $G=(G_1,\ldots,G_k)$ with shared induced subgraph $S$ has a simultaneous proper interval representation exactly when the graphs admit a simultaneous enumeration: straight enumerations of the $G_i$ that order the blocks of $S$ consistently. Such an enumeration exists iff the intersection of the PQ-trees of fine enumerations of the $G_i$ projected to $S$ is non-null, so recognition is linear-time. For unit intervals, Theorem 13 says a simultaneous enumeration $\zeta$ is realizable by unit intervals iff no chain-bar conflict occurs: no ordered path in one $G_i$ and ordered independent set in another $G_j$ between two shared vertices have equal length. Since Theorem 8 describes every simultaneous enumeration as reversals of independent components and reversible parts of a given one, conflict-freeness can be searched by 2-SAT; Theorem 17 gives $O(|V|\cdot|E|)$ recognition and representation. Finally, dropping the sunflower requirement and letting $k$ vary makes both problems NP-complete (Theorems 28 and 29).
Load-bearing premise
The unit-interval algorithm rests on Theorem 13, the claim that a simultaneous enumeration admits a unit-length representation exactly when no chain-bar conflict exists; if that equivalence fails for some configuration, the 2-SAT search over reversal choices can certify the wrong answer.
Editorial extensions
If this is right
- The linear-time proper-interval test is optimal and constructive: a sunflower simultaneous graph that passes the PQ-tree test comes with a representation.
- Unit-interval recognition handles any number of sunflower graphs in $O(|V|\cdot|E|)$ time on the union graph.
- The sunflower restriction is essential: without it, both recognition problems become NP-complete as soon as the number of graphs is part of the input.
- The 2-SAT formulation yields a compact negative certificate: an unsatisfiable formula lists the reversal combinations that each contain a chain-bar conflict.
- Both algorithms output an actual simultaneous representation, not only a decision, so they can be used as building blocks for drawing or verification tools.
Reading between the lines
- The chain-bar distance argument does not need the sunflower assumption in its core inequality, so a plausible next step is to test the same conflict criterion on non-sunflower two-graph instances, where the representation space is not described by reversible parts but may still be closed under the same scouting-zipping sweeps.
- If the scouting-zipping construction can be re-run with prescribed interval lengths instead of unit lengths, the same framework would yield a length-constrained simultaneous representation algorithm, with chain-bar conflicts replaced by weighted distance inequalities.
- The Betweenness reductions suggest a wider pattern: any graph class whose local representation forces a vertex to lie between two others is likely to give NP-complete simultaneous recognition for unbounded $k$.
- A natural stress test is to check whether the no-conflict criterion remains sufficient when the shared graph $S$ is disconnected; the paper assumes the union graph is connected without loss, but the unit-interval construction may behave differently across disconnected shared pieces.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies simultaneous proper and unit interval graphs in the sunflower case, where all input graphs share a common subgraph S. It presents a linear-time recognition algorithm for simultaneous proper interval graphs (Theorem 6) based on PQ-tree projection and intersection, followed by a partial representation extension. For simultaneous unit interval graphs, it develops a combinatorial characterization via chain-bar conflicts (Theorem 13) and an O(|V||E|) recognition algorithm (Theorem 17) that combines a characterization of all simultaneous enumerations (Theorem 8) with a 2-SAT search over reversals. The paper also proves NP-completeness for both recognition problems when the number of input graphs is not fixed and the sunflower restriction is dropped (Theorems 28 and 29).
Significance. If correct, the paper settles an open problem by giving the first polynomial-time algorithms for sunflower simultaneous proper and unit interval graphs with an unbounded number of input graphs, and it establishes tight complexity boundaries. The proper-interval recognition algorithm is elegant and robust, built on standard PQ-tree machinery and on the known partial representation extension algorithm of Klavík et al. The chain-bar conflict criterion and the reduction of the unit case to a 2-SAT instance are appealing and, if the supporting theorems are repaired, would constitute a substantial contribution. The NP-completeness reductions from Betweenness are straightforward and appear sound. However, the correctness of the unit-interval algorithm currently rests on Theorem 8, which is false as stated; this must be fixed before the main algorithmic claims can be accepted.
major comments (2)
- [§3.3, definition of 'loose' and Theorem 8; Appendix B.5] Theorem 8 is false as stated. Let S have vertices s1,s2,c,d and the single edge s1s2, so B={s1,s2}, {c}, {d} are its blocks. Let G1 have edges s1s2, s1p, pc and G2 have edges s1s2, qs1, qs2, qd. Both graphs are proper interval graphs, and the tuple (c<p<s1<s2<d, c<B<q<d) is a simultaneous enumeration: the shared block orders are c<s1<s2<d in G1 and c<B<d in G2. The component C1={c,p,s1,s2} of G1 is loose by the definition in Section 3.3, since the only shared vertex outside C1 is d, which forms a single block, and C1 is oriented at B, so C(B)={C1} is a reversible part. Reversing C1 yields the tuple (s2<s1<p<c<d, c<B<q<d), whose shared order in G1 is B<c<d and in G2 is c<B<d; this is not a simultaneous enumeration. This directly contradicts the 'if' direction of Theorem 8. The flaw is visible in the proof in Appendix B.5: it only treats shared-vertex pairs lying both inside the same block B or both outside the reversed component, and never a pair with one endpoint in B and another shared vertex in a different block that lies in the same component. The definition of 'loose' needs to be amended (e.g., require V_S∩C to be contained in one block of S), and Theorem 8 reproved. Because Theorem 17 uses Theorem 8 to restrict the candidate simultaneous enumerations searched by 2-SAT, this issue is load-bearing for the unit-interval algorithm.
- [Appendix B.3, Lemma 18] Lemma 18 is also false under the stated definition of 'loose'. The proof claims that when the shared order is unchanged, 'no straight enumeration containing vertices from more than one block of S is reversed'; but a component may contain vertices from several blocks of S while all shared vertices outside it lie in one block, and the current definition of 'loose' does not exclude that. The example in my first comment is exactly such a component: reversing the loose component C1 changes the shared order from c<B<d to B<c<d. The fix should make the 'loose' condition a property of the shared vertices inside the component, so that reversal of a loose component can never change the order of two blocks of S.
minor comments (3)
- [Section 4.1] The statement of Theorem 13 appears twice with the same number, once after Corollary 12 and once after Lemma 16; the second occurrence should be renumbered.
- [Section 4.1, Lemma 9] In Lemma 9, 'compatible with σ on V_i' is not formally defined for a fine enumeration σ of H; please state explicitly that the restriction of σ to V_i is the order to which ζ_i is compatible.
- [Section 3.3] The notation C(B) is used both for the set of components oriented at block B and for the reversible part formed by such a set, which makes phrases like 'reversal of reversible part C(B)' ambiguous; consider using a different symbol for the part itself.
Circularity Check
No significant circularity: the algorithms are built from independently characterized combinatorial conditions and external algorithms, with no fitted input renamed as a prediction.
full rationale
The paper's derivation chain is self-contained against its stated definitions. The proper-interval recognition (Theorem 6) reduces to PQ-tree projections and intersections plus the partial-representation extension algorithm of Klavik et al. [21]; these are external published tools, and Rutter's co-authorship of [21] does not make the citation load-bearing because the present paper's sunflower characterization (Theorems 4 and 5) is proved directly by constructing endpoint orders from simultaneous enumerations. The unit-interval criterion (Theorem 13) is derived from the Looges-Olariu fine-enumeration condition and explicit distance inequalities between chains and bars; the 'no conflict' condition is not defined as 'has a unit representation' but is shown equivalent by a scouting/zipping construction. The NP-completeness reductions are from Betweenness and do not assume their target. The only conceivable circularity concern, Theorem 8's enumeration-reversal characterization, is a correctness issue rather than a circularity: its proof in Appendix B.5 argues from Lemma 18 and Lemma 19 instead of assuming the conclusion, and the skeptical counterexample attack concerns validity, not input-output equivalence. No parameter is fitted to a subset of data and then renamed a prediction; no known result is repackaged under new coordinates; and the self-citations are to algorithms and reductions that are applied as black boxes, not invoked to forbid alternatives. Accordingly the circularity score is 0.
Assumptions & free parameters
assumptions (6)
- standard math A graph is a proper interval graph if and only if it has a straight enumeration, and a connected proper interval graph has a straight enumeration unique up to reversal.
- standard math PQ-tree projection, intersection, and reduction operations correctly represent sets of linear orders satisfying consecutivity constraints and run in linear time.
- standard math The partial representation extension algorithm for proper and unit interval graphs of Klavik et al. is correct and runs in linear time.
- standard math Looges and Olariu's fine enumeration characterization of unit and proper interval graphs, including the forbidden four-vertex configuration, is correct.
- standard math Betweenness is NP-complete.
- domain assumption In a sunflower simultaneous graph, the shared graph S is an induced subgraph of every Gi, and the problem can be reduced to connected instances where the union graph is connected.
Cite this review
Pith. "Pith review of Simultaneous Representation of Proper and Unit Interval Graphs." pith.science (2026). https://pith.science/paper/DUM5JBDB
@misc{pith2026190808882,
author = {Pith},
title = {Pith review of: Simultaneous Representation of Proper and Unit Interval Graphs},
year = {2026},
howpublished = {\url{https://pith.science/paper/DUM5JBDB}},
note = {Machine review of arXiv:1908.08882}
}
read the original abstract
In a confluence of combinatorics and geometry, simultaneous representations provide a way to realize combinatorial objects that share common structure. A standard case in the study of simultaneous representations is the sunflower case where all objects share the same common structure. While the recognition problem for general simultaneous interval graphs -- the simultaneous version of arguably one of the most well-studied graph classes -- is NP-complete, the complexity of the sunflower case for three or more simultaneous interval graphs is currently open. In this work we settle this question for proper interval graphs. We give an algorithm to recognize simultaneous proper interval graphs in linear time in the sunflower case where we allow any number of simultaneous graphs. Simultaneous unit interval graphs are much more 'rigid' and therefore have less freedom in their representation. We show they can be recognized in time O(|V|*|E|) for any number of simultaneous graphs in the sunflower case where G = (V, E) is the union of the simultaneous graphs. We further show that both recognition problems are in general NP-complete if the number of simultaneous graphs is not fixed. The restriction to the sunflower case is in this sense necessary.
Reference graph
Works this paper leans on
-
[1]
On some NP -complete SEFE problems
Patrizio Angelini, Giordano Da Lozzo, and Daniel Neuwirth. On some NP -complete SEFE problems. In Sudebkumar Prasant Pal and Kunihiko Sadakane, editors, Algorithms and Computation: 8th International Workshop, WALCOM 2014, Chennai, Proceedings , pages 200--212. Springer, 2014. http://dx.doi.org/10.1007/978-3-319-04657-0_20 doi:10.1007/978-3-319-04657-0_20
-
[2]
Plass, and Robert Endre Tarjan
Bengt Aspvall, Michael F. Plass, and Robert Endre Tarjan. A linear-time algorithm for testing the truth of certain quantified boolean formulas. Information Processing Letters , 8(3):121--123, 1979. http://dx.doi.org/10.1016/0020-0190(79)90002-4 doi:10.1016/0020-0190(79)90002-4
-
[3]
Simultaneous Embedding of Planar Graphs
Thomas Bl \" a sius, Stephen G. Kobourov, and Ignaz Rutter. Simultaneous embedding of planar graphs. CoRR , abs/1204.5853, 2012. URL: http://arxiv.org/abs/1204.5853, http://arxiv.org/abs/1204.5853 arXiv:1204.5853
work page Pith review arXiv 2012
-
[4]
Simultaneous PQ -ordering with applications to constrained embedding problems
Thomas Bl\" a sius and Ignaz Rutter. Simultaneous PQ -ordering with applications to constrained embedding problems. ACM Trans. Algorithms , 12(2):16:1--16:46, 2015. http://dx.doi.org/10.1145/2738054 doi:10.1145/2738054
doi:10.1145/2738054 2015
-
[5]
A note on simultaneous representation problem for interval and circular-arc graphs
Jan Bok and Nikola Jedli c kov \'a . A note on simultaneous representation problem for interval and circular-arc graphs. arXiv preprint arXiv:1811.04062 , 2018. URL: https://arxiv.org/abs/1811.04062
work page Pith review arXiv 2018
-
[6]
Kellogg S. Booth. PQ Tree Algorithms . PhD thesis, University of California, Berkeley, 1975
work page 1975
-
[7]
Kellogg S. Booth and George S. Lueker. Testing for the consecutive ones property, interval graphs, and graph planarity using PQ -tree algorithms. Journal of Computer and System Sciences , 13(3):335--379, 1976. http://dx.doi.org/10.1016/S0022-0000(76)80045-1 doi:10.1016/S0022-0000(76)80045-1
-
[8]
On simultaneous planar graph embeddings
Peter Brass, Eowyn Cenek, Cristian A Duncan, Alon Efrat, Cesim Erten, Dan P Ismailescu, Stephen G Kobourov, Anna Lubiw, and Joseph SB Mitchell. On simultaneous planar graph embeddings. Computational Geometry , 36(2):117--130, 2007. http://dx.doi.org/10.1016/j.comgeo.2006.05.006 doi:10.1016/j.comgeo.2006.05.006
Show all 30 references
-
[9]
Extending partial representations of circle graphs
Steven Chaplick, Radoslav Fulek, and Pavel Klav \'i k. Extending partial representations of circle graphs. In Stephen Wismath and Alexander Wolff, editors, Graph Drawing: 21st International Symposium, GD 2013, Bordeaux, Revised Selected Papers , pages 131--142. Springer, 2013....
2013 doi
-
[10]
Herrera de Figueiredo, João Meidanis, and Célia Picinin de Mello
Celina M. Herrera de Figueiredo, João Meidanis, and Célia Picinin de Mello. A linear-time algorithm for proper interval graph recognition. Information Processing Letters , 56(3):179--184, 1995. http://dx.doi.org/10.1016/0020-0190(95)00133-W doi:10.1016/0020-0190(95)00133-W
1995 doi
-
[11]
Linear-time representation algorithms for proper circular-arc graphs and proper interval graphs
Xiaotie Deng, Pavol Hell, and Jing Huang. Linear-time representation algorithms for proper circular-arc graphs and proper interval graphs. SIAM J. Comput. , 25(2):390--403, 1996. http://dx.doi.org/10.1137/S0097539792269095 doi:10.1137/S0097539792269095
1996 doi
-
[12]
Simultaneous geometric graph embeddings
Alejandro Estrella-Balderrama, Elisabeth Gassner, Michael J \"u nger, Merijam Percan, Marcus Schaefer, and Michael Schulz. Simultaneous geometric graph embeddings. In Seok-Hee Hong, Takao Nishizeki, and Wu Quan, editors, Graph Drawing: 15th International Symposium, GD 2007, Sy...
2007 doi
-
[13]
Simultaneous graph embeddings with fixed edges
Elisabeth Gassner, Michael J \"u nger, Merijam Percan, Marcus Schaefer, and Michael Schulz. Simultaneous graph embeddings with fixed edges. In Fedor V. Fomin, editor, Graph-Theoretic Concepts in Computer Science: 32nd International Workshop, WG 2006, Bergen, Revised Papers , p...
2006 doi
-
[14]
Goldberg, Martin C
Paul W. Goldberg, Martin C. Golumbic, Haim Kaplan, and Ron Shamir. Four strikes against physical mapping of DNA . Journal of Computational Biology , 2(1):139--152, 1995. http://dx.doi.org/10.1089/cmb.1995.2.139 doi:10.1089/cmb.1995.2.139
1995 doi
-
[15]
Algorithmic Graph Theory and Perfect Graphs (Annals of Discrete Mathematics, Vol 57)
Martin Charles Golumbic. Algorithmic Graph Theory and Perfect Graphs (Annals of Discrete Mathematics, Vol 57) . North-Holland Publishing Co., 2004
2004
-
[16]
Graph sandwich problems
Martin Charles Golumbic, Haim Kaplan, and Ron Shamir. Graph sandwich problems. Journal of Algorithms , 19(3):449--473, 1995. http://dx.doi.org/10.1006/jagm.1995.1047 doi:10.1006/jagm.1995.1047
1995
-
[17]
Induced subgraph isomorphism on proper interval and bipartite permutation graphs
Pinar Heggernes, Pim van 't Hof, Daniel Meister, and Yngve Villanger. Induced subgraph isomorphism on proper interval and bipartite permutation graphs. Theoretical Computer Science , 562:252--269, 2015. http://dx.doi.org/10.1016/j.tcs.2014.10.002 doi:10.1016/j.tcs.2014.10.002
2015 doi
-
[18]
A fully dynamic algorithm for recognizing and representing proper interval graphs
Pavol Hell, Ron Shamir, and Roded Sharan. A fully dynamic algorithm for recognizing and representing proper interval graphs. SIAM J. Comput. , 31(1):289--305, 2002. http://dx.doi.org/10.1137/S0097539700372216 doi:10.1137/S0097539700372216
2002 doi
-
[19]
Simultaneous interval graphs
Krishnam Raju Jampani and Anna Lubiw. Simultaneous interval graphs. In Otfried Cheong, Kyung-Yong Chwa, and Kunsoo Park, editors, Algorithms and Computation: 21st International Symposium, ISAAC 2010, Jeju Island, Proceedings, Part I , pages 206--217. Springer, 2010. http://dx....
2010 doi
-
[20]
The simultaneous representation problem for chordal, comparability and permutation graphs
Krishnam Raju Jampani and Anna Lubiw . The simultaneous representation problem for chordal, comparability and permutation graphs. Journal of Graph Algorithms and Applications , 16(2):283--315, 2012. http://dx.doi.org/10.7155/jgaa.00259 doi:10.7155/jgaa.00259
2012 doi
-
[21]
Extending partial representations of proper and unit interval graphs
Pavel Klav \'i k, Jan Kratochv \'i l, Yota Otachi, Ignaz Rutter, Toshiki Saitoh, Maria Saumell, and Tom \'a s Vysko c il. Extending partial representations of proper and unit interval graphs. Algorithmica , 77(4):1071--1104, Apr 2017. http://dx.doi.org/10.1007/s00453-016-0133-...
2017 doi
-
[22]
Optimal greedy algorithms for indifference graphs
Peter J Looges and Stephan Olariu. Optimal greedy algorithms for indifference graphs. Computers & Mathematics with Applications , 25(7):15--25, 1993. http://dx.doi.org/10.1016/0898-1221(93)90308-I doi:10.1016/0898-1221(93)90308-I
1993 doi
-
[23]
Linear-time recognition of probe interval graphs
Ross M McConnell and Yahav Nussbaum. Linear-time recognition of probe interval graphs. In Amos Fiat and Peter Sanders, editors, Proceedings of the 17th Annual European Symposium on Algorithms (ESA'09) , volume 5757 of Lecture Notes in Computer Science , pages 349--360. Springe...
2009 doi
-
[24]
Recognition of probe proper interval graphs
Yahav Nussbaum. Recognition of probe proper interval graphs. Discrete Applied Mathematics , 167:228--238, 2014. http://dx.doi.org/10.1016/j.dam.2013.11.013 doi:10.1016/j.dam.2013.11.013
2014 doi
-
[25]
Total ordering problem
Jaroslav Opatrny. Total ordering problem. SIAM J. Comput. , 8(1):111--114, 1979. URL: http://dblp.uni-trier.de/db/journals/siamcomp/siamcomp8.html#Opatrny79
1979
-
[26]
Representations of indifference relations
Fred S Roberts. Representations of indifference relations . PhD thesis, Department of Mathematics, Stanford University, 1968
1968
-
[27]
Fred S. Roberts. Indifference graphs. In F. Harary, editor, Proof Techniques in Graph Theory , pages 139--146. Academic Press, New York, 1969
1969
-
[28]
Toward a theory of planarity: Hanani- T utte and planarity variants
Marcus Schaefer. Toward a theory of planarity: Hanani- T utte and planarity variants. In Walter Didimo and Maurizio Patrignani, editors, Graph Drawing: 20th International Symposium, GD 2012, Redmond, Revised Selected Papers , pages 162--173. Springer, 2013. http://dx.doi.org/1...
2012 doi
-
[29]
Dale J. Skrien. A relationship between triangulated graphs, comparability graphs, proper interval graphs, proper circular-arc graphs, and nested interval graphs. Journal of Graph Theory , 6(3):309--316, 1982. http://dx.doi.org/10.1002/jgt.3190060307 doi:10.1002/jgt.3190060307
1982 doi
-
[30]
Jeremy P. Spinrad. Efficient Graph Representations . Fields Institute Monographs. AMS, 2003
2003
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.