On the structure of normalized models of circular-arc graphs -- Hsu's approach revisited

Tomasz Krawczyk

REVIEW 4 major objections 4 minor 1 cited by

On the structure of normalized models of circular-arc graphs -- Hsu's approach revisited

T0 review · 4 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read This paper proves that every circular-arc graph has a canonical string representation computable in linear time, which yields a linear-time isomorphism test.

desk verdict A serious, likely-correct resolution of a 40-year-open problem, but the written proof has load-bearing gaps that need a full referee pass. read the letter →

arxiv 2411.13374 v2 pith:WO2Q75TQ submitted 2024-11-20 cs.DS

Tomasz Krawczyk This is my paper · ORCID

classification cs.DS MSC 05C6205C6068R10

keywords circular-arcgraphsnormalizedintersectionmodelsPQSM-treeoverlapgraphisomorphismcanonizationmodulardecompositionconformalchord

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

Circular-arc graphs are intersection graphs of arcs on a circle, and the paper claims that the normalized arc drawings—those that mirror the neighborhood relation of vertices—have a complete structural description. The description is a linear-space data structure, the PQSM-tree, which records every normalized model of a given graph: the tree encodes all possible circular orders of blocks of endpoints and all ways to permute vertices inside each block. The paper proves this tree can be built in linear time and that it gives a canonical string for the graph in linear time. Since two circular-arc graphs are isomorphic exactly when their canonical strings agree, the same result solves graph isomorphism for this class in linear time.

What carries the argument

The PQSM-tree is a linear-size ordered tree representation of all conformal chord models of the overlap graph: S-nodes are endpoint slots, Q-nodes are connected components, P-nodes are regions of the circular drawing, and M-nodes come from modular decomposition trees of the CA-modules that serve as metachords. The important property is that every conformal model is obtained by choosing one circular order of slots allowed by the tree and then replacing each slot with an admissible permutation of its vertices; Theorem 6.2 states exactly this equivalence. It is the object that makes the structural description algorithmic, since canonization reduces to canonically ordering the PQM-nodes level by level.

What would settle it

Enumerate, for all connected circular-arc graphs with no twins and no universal vertices up to, say, ten vertices, all conformal models of their overlap graphs; if any prime induced subgraph has three non-equivalent conformal models, Lemma 8.4 fails. A more direct check is to implement the PQSM-tree construction and compare the set of models it generates with brute-force enumeration for random instances: any conformal word that is not admissible by the tree would refute Theorem 6.2.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central discovery is a characterization theorem: after converting normalized arc models into oriented chord models, normalized models of G correspond one-to-one with conformal models of the overlap graph Gov (Theorem 3.3), and a circular word is a conformal model precisely when it is admissible for the quadruple DS=(S,S*,MC,Π), represented compactly as the PQSM-tree (Theorem 6.2). The proof splits according to whether the root of the modular decomposition is serial, prime, or parallel, and handles both prime and serial components uniformly through CA-modules and metachords. From this structural theorem the paper derives Theorem 1.2: the canonization problem for circular-arc graphs can be solved in linear time, and hence the isomorphism problem for this class is also linear-time.

Load-bearing premise

The whole construction depends on the uniqueness lemma that every prime induced subgraph of the overlap graph has exactly two conformal models, one being the reflection of the other; if any prime piece had a third conformal model, the induction behind the PQSM-tree would miss models and the linear-time canonization would collapse.

Editorial extensions

If this is right

If the central theorems are right, circular-arc graph isomorphism is decidable in linear time because two graphs are isomorphic exactly when their canonical strings are equal.
The PQSM-tree is a complete registry of normalized models, so every structural operation on models—reflections of Q-nodes, permutations of P-nodes, and replacements of admissible metachord models—stays inside the described class.
The linear-time bound covers the full class, not just proper, Helly, or co-bipartite circular-arc graphs, because universal vertices and twins are stripped into a separate representation (G,m,u).
The construction algorithm for the PQSM-tree starts from a normalized model supplied by circular-arc recognition, so the canonization pipeline is compatible with existing linear-time recognition.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

A concrete test the paper leaves implicit: implement the PQSM-tree on the known counterexample graphs from earlier work on circular-arc isomorphism and check that the tree reproduces all normalized models, which would validate the corrected structural claim directly.
Because canonization is organized as level-wise canonical forms of PQM-nodes, the same framework should adapt to other geometric graph classes whose models are described by modular-decomposition-style trees, such as circle graphs or permutation graphs, although the paper does not claim this.
The paper's operational description of how conformal models transform into one another gives, as a byproduct, a way to count or uniformly sample normalized models of a circular-arc graph in polynomial time; the paper only uses the description for canonization.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

The short version: this is a real attempt at the long-open linear-time isomorphism and canonization problem for circular-arc graphs, and the overall approach looks right. I think the main theorem is probably true, but the submitted proof is not complete enough to accept as is. The PQSM-tree description of normalized models is genuinely new, and the canonization algorithm built on it is a clean idea.

The paper does several things well. It correctly diagnoses why Hsu's 1995 decomposition trees fail, and it avoids the trap by using oriented chords and tracking left/right relations explicitly. The reduction to conformal models of the overlap graph is sound, and the use of split decomposition (Gabor-Supowit-Hsu, Chaplick-Fulek-Klavik) is appropriate. There are no fitted parameters, and the only self-citation supports a negative claim about Hsu's work, not the positive theorem. That is honest scholarship.

The soft spots are real, though. The stress-test note lands: Lemma 8.4 is the keystone of the prime case, and the induction in Claim 8.6 applies the induction hypothesis to arbitrary probes that are not necessarily sets of representatives of children of a prime module. As written, the lemma statement does not justify that step unless the lemma is implicitly meant for all prime induced subgraphs, which is not stated. The subcase where Condition (*) fails also leans on a tie-breaking rule in the maximal-split algorithm ('the algorithm always takes the first option') to rule out a non-trivial module; if that rule is not precisely defined, the contradiction is unsupported. Section 10, which computes CA-modules, and part of the sufficiency proof in Section 6 are explicitly left to the reader. These are gaps in presentation and proof detail, not signs of a counterexample. The architecture is coherent, and the prior negative results on Hsu's algorithm are not in question.

Who this is for: researchers in algorithmic graph theory, especially those working on graph isomorphism or geometric intersection graphs. It deserves a serious referee, but with the expectation of heavy revision. I would engage with it and ask the author to expand the missing proofs, or to provide machine-checked formalization for the crucial induction. My verdict is conditional: if the gaps close, this is a major result.

Referee Report

4 major / 4 minor

Summary. The paper claims a complete structural description of all normalized intersection models of a circular-arc graph, encoded in a new data structure called a PQSM-tree. It further claims that the PQSM-tree can be built in linear time, yielding a linear-time canonization algorithm and hence a linear-time isomorphism test for circular-arc graphs. The approach follows Hsu's 1995 strategy but replaces non-oriented chords with oriented chords, and reduces normalized models of the circular-arc graph to conformal models of its overlap graph. The main structural theorem (Theorem 6.2) is split into serial, prime, and parallel cases; the prime case rests on a long induction over split decompositions, culminating in Lemma 8.4, which asserts that every prime induced subgraph of the overlap graph has exactly two conformal models, one the reflection of the other.

Significance. If the main results are correct, they resolve a long-standing open problem: circular-arc graph isomorphism in linear time. The paper contains no fitted parameters and no circular argumentation: the positive proof builds on external theorems (Gabor-Supowit-Hsu, Chaplick-Fulek-Klavik, McConnell, Gallai) rather than on the claims being proved. The proposed PQSM-tree is a substantial and plausible generalization of PQ-trees, and the reframing using oriented chords is a genuine improvement over Hsu's setup. However, the correctness of the central structure theorem depends critically on Lemma 8.4, and the proof of that lemma as written has gaps in the induction and in one case of the maximal-split argument. Because Theorem 1.2 and the linear-time algorithm inherit those gaps, the contribution is not yet fully established.

major comments (4)

[Section 8 (Lemma 8.4 and Claim 8.6)] The induction in Lemma 8.4 is not justified by the stated lemma. Lemma 8.4 is formulated for a graph (U,∼) consisting of one vertex from each child of a prime component Q of the overlap graph. In the proof of Claim 8.6, the induction hypothesis is applied to arbitrary prime induced subgraphs (P,∼) of (U,∼), such as (P\{z},∼), which need not be of the form 'one representative from each child of a prime component'. Either Lemma 8.4 must be stated and proved for every prime induced subgraph of the overlap graph, or an additional argument must show that each probe graph has exactly the form covered by the induction hypothesis. Without this, the induction step for the case Z=∅ and for the prime subgraph in the case Z={z} is unsupported.
[Section 8 (Condition (*) fails, around equation (8.6.3))] The treatment of the case where Condition (*) fails relies on a tie-breaking rule for the maximal-split algorithm: the text says 'in each step, having the choice of extending (A,B) into a non-trivial or a trivial split, the algorithm always takes the first option', and later uses this rule to rule out the possibility M1=∅. This rule is not a well-defined deterministic tie-breaker when there are multiple non-trivial extensions, and no proof is given that the 'second option' mentioned in the contradiction is the unique non-trivial alternative. If the maximal-split algorithm admits alternative executions, the contradiction is not established. This is a load-bearing point: a missed configuration in this subcase would allow more than two conformal models of a prime overlap graph, invalidating the prime-case characterization.
[Section 6 (sufficiency direction of Theorem 6.2)] The sufficiency proof of the central equivalence is left almost entirely to the reader: after describing the allowed transformations, the text says 'We leave the reader to check that all those transformations keep the left/right relation between non-intersecting chords'. This check is not a formality, because transformations of the first type operate inside CA-modules while transformations of the second type permute or reflect slots at the PQS-tree level, and one must verify that the two operations interact correctly for all pairs of non-intersecting chords, including chords that belong to different CA-modules or different components. A complete verification is required for Theorem 6.2 to support the canonization claim.
[Section 10 (linear-time construction of CA-modules)] The linear-time algorithm for constructing the PQSM-tree contains two 'we leave it to the reader' steps: verifying that the set S of CA-modules can be computed using Property (R), and checking that the bottom-up computed sets S(M) comprise all CA-modules contained in M. Since the linear-time bound and the correctness of the data structure both depend on this step, these claims need a proof rather than a reader exercise. In particular, the assertion that each module in M(Gov) can be processed in time linear in the number of its children is plausible but not demonstrated; the computation of S(M) for serial, parallel, and prime cases must be specified in enough detail to rule out hidden superlinear behavior.

minor comments (4)

[Throughout] The text uses the symbol 'integerdivide' in many places where set difference (\\setminus) is clearly intended, e.g., 'V /integerdivide X' and 'Q /integerdivide Mi'. This should be fixed in the final typeset version.
[Abstract and Introduction] The abstract and the introduction contain nearly identical sentences about errors in Hsu's decomposition trees pointed out in [18]; consider unifying these two passages to avoid repetition.
[Section 1] The footnote about the author's earlier arXiv paper [17] and publishing difficulties is not relevant to the technical content and could be removed or moved to an acknowledgements section.
[Section 2] In the definition of normalized models, the paper refers to [25,14] for the fact that every circular-arc model without twins and universal vertices can be normalized; the provided text does not show the bibliography, so the reader cannot easily verify these references. Please ensure all cited works are included.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the derivation is self-contained and the only self-citation is not load-bearing.

full rationale

The paper does not fit any parameters and its central claims are not equivalent to their inputs. The normalized-model/conformal-model correspondence (Theorem 3.3) is a definitional encoding: “conformal” is defined by the same left/right partition that defines normalized models, so the equivalence holds by construction, but this bridge is not the paper’s advertised prediction and no subsequent theorem reduces to it. Theorem 6.2, the structural characterization, is proved by a case analysis over the modular decomposition of the overlap graph (serial/prime/parallel), whose key lemma is Lemma 8.4, proved by induction using external split-decomposition theorems of Gabor-Supowit-Hsu and Chaplick-Fulek-Klavik, together with the paper’s own probe argument. The only author self-citation, reference [18], is used to document failures of Hsu’s construction and does not carry a load-bearing positive premise. The linear-time canonization algorithm is obtained from combinatorial definitions of CA-modules, metachords, and PQS/PQSM-trees, with no fitted parameter renamed as a prediction. Any concerns about the induction in Lemma 8.4, the use of probes, or the tie-breaking rule in the maximal-split algorithm are correctness risks, not circularity.

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

No numerical parameters are fitted; the paper is a mathematical derivation. The PQSM-tree, CA-modules, slots, and metachords are internal constructions whose defining properties are proved in the paper, not unexplained postulated entities. The derivation depends on several external algorithmic and structural theorems, as listed above, and on the companion paper [18] only for negative claims against Hsu.

assumptions (7)

domain assumption Standard word RAM with words of length O(log n), arithmetic and bitwise operations in constant time.
Stated in footnote 2, Section 1; needed for the linear-time claims.
domain assumption G has no universal vertices and no twins; every circular-arc graph can be reduced to this case by grouping twins (Claims 11.1 and 11.2).
Normalized models and the one-to-one correspondence of Theorem 3.3 are defined for this case; Section 11 handles general graphs.
standard math Claim 2.6: if x is adjacent to all of U, any chord model of a circle graph restricts to x tau x tau' with (tau, tau') a permutation model of U.
Used repeatedly to derive permutation models inside circular-arc overlap graphs; proof is given in Section 2.
standard math Theorem 8.1 (Gabor-Supowit-Hsu): a connected circle graph without non-trivial splits has exactly two chord models up to reflection.
External theorem used to prove the uniqueness part of Lemma 8.4.
standard math Theorems 8.2 and 8.3 (Chaplick-Fulek-Klavik): structure of chord models relative to maximal splits.
External theorems used in the induction of Lemma 8.4.
domain assumption Linear-time recognition algorithm of McConnell [21] returns a normalized circular-arc model on yes-instances.
Used in Section 10 to obtain the initial conformal model; not re-proved in this paper.
domain assumption Linear-time modular decomposition algorithm of McConnell and Spinrad [22] exists.
Used to compute the modular decomposition trees in Section 10.

how reviews work

0 comments

Cite this review

Pith. "Pith review of On the structure of normalized models of circular-arc graphs -- Hsu's approach revisited." pith.science (2026). https://pith.science/paper/WO2Q75TQ

@misc{pith2026241113374,
  author       = {Pith},
  title        = {Pith review of: On the structure of normalized models of circular-arc graphs -- Hsu's approach revisited},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/WO2Q75TQ}},
  note         = {Machine review of arXiv:2411.13374}
}

abstract

Circular-arc graphs are the intersection graphs of arcs of a circle. The main result of this work describes the structure of all \emph{normalized intersection models} of circular-arc graphs. Normalized models of a circular-arc graph reflect the neighborhood relation between its vertices and can be seen as its canonical representations; in particular, any intersection model can be made normalized by possibly extending some of its arcs. We~devise a data-structure, called \emph{PQM-tree}, that maintains the set of all normalized models of a circular-arc graph. We show that the PQM-tree of a circular-arc graph can be computed in linear time. Finally, basing on PQM-trees, we provide a linear-time algorithm for the canonization and the isomorphism problem for circular-arc graphs. We describe the structure of the normalized models of circular-arc graphs using an approach proposed by Hsu~[\emph{SIAM J. Comput. 24(3), 411--439, (1995)}]. In the aforementioned work, Hsu claimed the construction of decomposition trees representing the set of all normalized intersection models of circular-arc graphs and an $\mathcal{O}(nm)$ time isomorphism algorithm for this class of graphs. However, the counterexample given in~[\emph{Discrete Math. Theor. Comput. Sci., 15(1), 157--182, 2013}] shows that Hsu's isomorphism algorithm is incorrect. Also, in a companion paper we show that the decomposition trees proposed by Hsu are not constructed correctly; in particular, we showed that there are circular-arc graphs whose all normalized models do not follow the description given by Hsu.

Figures

Figures reproduced from arXiv: 2411.13374 by the authors.

**Figure 2.1.** To the left: a collection B = {a1, a2, a3, c, p, q} consisiting of three arcs a1, a2, a3, a chord c, and two points p, q is represented by the circular word τ (B) ≡ a 0 2pa1 1 ca0 3a 1 2a 1 3 qa0 1 c. The word τ (BR) ≡ ca1 1 qa0 3a 0 2a 1 3 ca0 1pa1 2 is the reflection of τ (B). To the right: the same collection in which the arcs are replaced by the corresponding oriented chords. Let τ be a circular word over the a… view at source ↗

**Figure 2.2.** To the left: intersection model ψ of a circular-arc graph G = (V, E), where V = {v1, . . . , v6} and E = {vivi+1 : i ∈ [5]} ∪ {v6v1}. We have ψk{v 0 1 , v1 1 , v0 6 , v1 6} ≡ v 0 6 v 0 1 v 1 6 v 1 1 (in red). The set {v 1 3 , v0 4 , v0 5} is contiguous in ψ (in blue) and we have ψ|{v 1 3 , v0 4 , v0 5} = v 0 4 v 1 3 v 0 5 . To the right: the corresponding oriented chord model. The notation we introduce below can be … view at source ↗

**Figure 2.3.** Intersection model (τ 0 , τ 1 ) = (abc, acb) of the permutation graph ({a, b, c}, {a ∼ b, a ∼ c)} corresponding to the transitive orientations {a ≺ b, a ≺ c} and {b < c} of (V, ∼) and (V, k}, respectively. See [PITH_FULL_IMAGE:figures/full_fig_p008_2_3.png] view at source ↗

Figures from the paper (56 more)

**Figure 2.4.** Figure 2.4: From left to right: ψ(v) and ψ(u) are disjoint, ψ(v) contains ψ(u), ψ(v) is contained in ψ(u), ψ(v) and ψ(u) cover the circle, and ψ(v) and ψ(u) overlap. In so-called normalized models, defined in [25, 14], the relative relation between the arcs reflects the closed n…

**Figure 3.1.** Figure 3.1: The transformation of the arc ψ(v) into the oriented chord φ(v). Now, we note some properties of the oriented chord models of Gov obtained from the normalized models of G. First, we associate with every vertex v ∈ V two sets, left(v) and right(v), where: left(v) = {u…

**Figure 3.2.** Figure 3.2: Relations between the arcs ψ(v) and ψ(u) and the corresponding oriented chords φ(v) and φ(u) for the cases: v is disjoint with u, v contains u, v is contained in u, v and u cover the circle, and v and u overlap, respectively. Our goal is to characterize the oriente…

**Figure 3.3.** Figure 3.3: To the left: the set U = {u1, u2, u3, u4} (in red) induces a consistent (oriented) permutation model (µ ′ , µ′′) = (u 0 1u 0 2u 1 3u 0 4 , u0 3u 1 1u 1 4u 1 2 ) in some conformal model φ. The chord u1 is directed from µ ′ to µ ′′. The set B (in black) does not induce…

**Figure 4.** Figure 4: for an illustration. Note that no arc from [PITH_FULL_IMAGE:figures/full_fig_p013_4.png]

**Figure 4.1.** Figure 4.1: for an illustration. Note that no arc from {ψ(v) : v ∈ V } contains both the points A and B as G has no universal vertices. Hence, each arc from {ψ(v) : v ∈ V } has one endpoint on the upper and one endpoint on the lower part of the circle. A normalized model of G is…

**Figure 5.1.** Figure 5.1: A conformal model φ of Gov and the circular order of the slots π(φ) in φ. The last component Π of the data structure DS contains the set of circular orders of the slots that might appear in the conformal models of Gov. In particular, Π is defined such that: (P2): For…

**Figure 5.** Figure 5: shows all non-equivalent conformal models of [PITH_FULL_IMAGE:figures/full_fig_p018_5.png]

**Figure 5.2.** Figure 5.2: All conformal models of some exemplary circular-arc graph. The rest of this section is organized as follows: • In Subsection 5.2 we show how to read the CA-modules, the slots, and the metachords of G from a given conformal model of Gov. • In Subsection 5.3 we describ…

**Figure 5.3.** Figure 5.3: To the left: the circular order of the slots π in some conformal model φ for the case when V is parallel in M(Gov). Q1, Q2, Q3, Q4, Q5 are the connected components of Gov, S(Q1) = {S1, S2} (metachords of Q1 are drawn in red) and S(Qi) = {Qi} for i ∈ [2, 5]. P-nodes P…

**Figure 5.4.** Figure 5.4: Two members π and π ′ of the set Π and the ordered PQStrees Tπ and Tπ′ representing π and π ′ for the case when V is serial in M(Gov). 5.3.2. V is prime in M(Gov). In this case, when M is a prime child of V we have S(M) = {M}, and when M is a serial/parallel child o…

**Figure 5.5.** Figure 5.5: Two members, π and its reflection π R, of the set Π and the ordered PQS-trees Tπ and TπR representing π and π R in the case when V is prime in M(Gov) [PITH_FULL_IMAGE:figures/full_fig_p022_5_5.png]

**Figure 5.6.** Figure 5.6: Reflection of Q1. Circular orders of the slots π and π ′ and the ordered PQS-trees Tπ and Tπ′ representing π and π ′ . The tree Tπ′ is obtained from Tπ by reflecting the node Q1: we have π|Q1 ≡ S 0 1P1S 1 2P2S 1 1S 0 2P3 and π ′ |Q1 ≡ (π|Q1 ) R ≡ P3S 1 2S 0 1P2S 0 2…

**Figure 5.** Figure 5: shows a modular decomposition tree [PITH_FULL_IMAGE:figures/full_fig_p024_5.png]

**Figure 5.7.** Figure 5.7: Permuting the neighbours of P1. Circular orders of the slots π and π ′ and the ordered trees Tπ and Tπ′ representing π and π ′ . The tree Tπ′ is obtained from Tπ by permuting the neigbours of P1: we have π|P1 ≡ Q1Q2Q3 and π ′ |P1 ≡ Q1Q3Q2, where S(Q1) = {S1, S2}. cor…

**Figure 5.8.** Figure 5.8: Admissible model τ = (τ 0 , τ 1 ) for S (to the left) and its reflection µ = (µ 0 , µ1 ) (to the right). We have τ|S = (A 0 1A 0 2A 0 3A 0 4 , A1 2A 1 4A 1 1A 1 3 ) and µ|S = (A0 3A0 1A0 4A0 2 , A1 4A1 3A1 2A1 1 ), τ|A2 = (B0 1B0 2B0 3 , B1 1B1 2B1 3 ) and µ|A2 = (B…

**Figure 5.9.** Figure 5.9: Modular decomposition tree M(S, ∼) of CA-module S (to the left) and an admissible model τ = (τ 0 , τ 1 ) for S. We have τ|S = (A 0 1A 0 2A 0 3A 0 4 , A1 2A 1 4A 1 1A 1 3 ) and τ|A2 = (B0 1B0 2B0 3 , B1 1B1 2B1 3 ). our convention, we say PQSM-tree T ∗ is ordered if e…

**Figure 6.1.** Figure 6.1: To the left: serial Q has four children M1, M2, M3, M4. To the right: an exemplary conformal model φ of (Q, ∼). all the letters from the words τ 0 i,φ and τ 1 i,φ, respectively. Note that M0 i,φ and M1 i,φ are superscripted copies of Mi and {M0 i,φ, M1 i,φ} forms a p…

**Figure 6.2.** Figure 6.2: Eventually, we set Π(Q) = π : π is a circular order of M0 1 , M1 1 , . . . , M0 t , M1 t such that for every two distinct i, j ∈ [t] the slots M0 i , M1 i overlap with the slots M0 j , M1 j We say a circular word φ on Q∗ is admissible for Π(Q) if φ arises from so…

**Figure 6.3.** Figure 6.3: To the left: prime Q has five children M1, . . . , M5; M1 is parallel and has three children L 1 1 , L2 1 , L3 1 , M5 is serial and has four children L 1 5 , L2 5 , L3 5 , L4 5 , and M2, M3, M4 are prime. To the right: schematic view of a conformal model φ of (M, ∼).…

**Figure 6.4.** Figure 6.4: To the left: a schematic view of a conformal model φ of G in which every component Q is represented by a closed curve encompassing all the chords from φ(Q). To the right: the tree T with the P-nodes P1, P2, P3 and Q-nodes Q1, Q2, Q3, Q4, Q5. Vertex v separates Q4 fro…

**Figure 6.5.** Figure 6.5: A conformal model φ of Gov and its contiguous subwords: φ|V ∗ T−Q1 (P1), φ|V ∗ T−Q1 (P2), and φ|V ∗ T−Q1 (P3) (to the left), and φ|V ∗ T−P1 (Q1), φ|V ∗ T−P1 (Q2), and φ|V ∗ T−P1 (Q3) (to the right). We have φ[Q1] ≡ τ1P1τ2P3τ3P2 and φ[P1] ≡ Q1Q3Q2. Now, our goal is t…

**Figure 6.6.** Figure 6.6: Extended conformal models φQ and φ R Q of (Q, ∼) for some prime component Q. We have τ (φQ, K1 1 ) = a 0 b 1P1c 0d1, τ (φQ, K0 1 ) = b 0a 1d 0 c 1 and τ (φ R Q, K0 1 ) = d 0 c 1P1b 0a 1 , τ (φ R Q, K1 1 ) = c 0d 1a 0 b 1 . We have inside(K1) = {P1}, inside(K2) = insi…

**Figure 6.7.** Figure 6.7: The words τ (φQ, K0 ), τ (φQ, K1 ) and the words τ (φ R Q, K0 ), τ (φ R Q, K1 ), where φQ and φ R Q are two extended models of (Q, ∼) and φ R Q is the reflection of φQ. We have |τ (φQ, K0 )| = |τ (φ R Q, K1 )| = 9. Claim 6.10. Suppose φQ, φ′ Q are two conformal model…

**Figure 6.8.** Figure 6.8: To the left: models admissible for γ 0 (Q), to the right: models admissible for γ 1 (Q). In particular, |τ (φQ, Kj )| = |τ (φ ′ Q, Kj )| and P occurs at position k in τ (φQ, Kj ) if and only if P occurs at position k in τ (φ ′ Q, Kj ). (2) If φ QkQ∗ is admissible for…

**Figure 6.** Figure 6: shows an example of the set [PITH_FULL_IMAGE:figures/full_fig_p039_6.png]

**Figure 6.9.** Figure 6.9: shows an example of the set S(K) for some K ∈ K(Q). For this specific case the set S(K) consists of the modules S1, . . . , S6; for example, the left-right partition of inside(K) for the vertices from S5 equals to ({P1, P3}, {P2, P4}). We easily check that the vertic…

**Figure 6.10.** Figure 6.10: The circular orders of the slots and the nodes π 0 (Q) and π 1 (Q) obtained from φQ and its reflection φ R Q are illustrated on the outer circles. Equivalently, we can imagine π 0 (Q) as it arises from γ 0 (Q) by replacing every slot K0 by the slots {S 0 : S ∈ S(K)}…

**Figure 6.11.** Figure 6.11: K0 and K1 in γ 0 (Q) are replaced by S 0 1S 0 2S 0 3P1S 0 4S 0 5P2S 0 6 and by S 1 3P4S 1 2S 1 5P3S 1 6S 1 1S 1 4 , respectively. K1 and K0 in γ 1 (M) are replaced by S 1 6P2S 1 5S 1 4P1S 1 3S 1 2S 1 1 and S 0 4S 0 1S 0 6P3S 0 2P4S 0 3 , respectively. Since S 1 6P2S…

**Figure 6.12.** Figure 6.12: An extended conformal model φQ of (Q, ∼) for a serial nonpermutation component Q with four children M1, M2, M3, M4. We have inside(M4) = {P3} and hence M4 is a member of K(Q). Every chord representing a vertex from M1 ∪ M2 has P1 on one side and P2, P3 on the othe…

**Figure 7.** Figure 7: illustrates the claim for the case where [PITH_FULL_IMAGE:figures/full_fig_p044_7.png]

**Figure 7.1.** Figure 7.1: illustrates the claim for the case where Q is prime and Mi is prime (to the left) and when Q is prime and Mi is parallel (to the right). τ τ ′ x 0 x 1 τ1 τ ′ 1 τ2 τ ′ 2 τ3 τ ′ 3 x 0 x 1 [PITH_FULL_IMAGE:figures/full_fig_p044_7_1.png]

**Figure 7.** Figure 7: to the left) [PITH_FULL_IMAGE:figures/full_fig_p045_7.png]

**Figure 7.2.** Figure 7.2: Chord models of (Q, ∼) for the cases when Q is prime and Mi is parallel (to the left) and when Q is prime and Mi is serial (to the right). Chords of the module Mi are in red, chords of the set N(Mi) are in bold. Proof. Since Q is prime, we can pick x ∈ Q r Mi such th…

**Figure 7.** Figure 7: to the right) [PITH_FULL_IMAGE:figures/full_fig_p046_7.png]

**Figure 8.1.** Figure 8.1: Split (α(A), A, α(B), B) in GU and two possible chord models of Gov: τAτBτ ′ Aτ ′ B and τ ′ AτBτAτ ′ B, where bτAbτ ′ A and aτBaτ ′ B are chord models of (A ∪ α(A) ∪ {b}, ∼) and (B ∪ α(B) ∪ {a}, ∼) for some a ∈ A and some b ∈ B, respectively. On the other hand, if G…

**Figure 8.2.** Figure 8.2: Maximal non-trivial split. Given a chord model viτiviτ ′ i of Gi for i ∈ [4], two non-equivalent chord models of GU , namely τ1τ ′ 4 τ ′ 2 τ3τ ′ 1 τ4τ2τ ′ 3 and τ3τ ′ 1 τ2τ ′ 4 τ ′ 3 τ1τ ′ 2 τ4, are shown to the right. Further, let Gi by a graph obtained from GU by c…

**Figure 8.3.** Figure 8.3: Maximal trivial split. Given chord models aτiaτ ′ i of Gi for i ∈ [3], two non-equivalent chord models of GU , namely aτ3τ ′ 2 τ1aτ ′ 1 τ2τ ′ 3 and aτ3τ1τ ′ 2aτ2τ ′ 1 τ ′ 3 , are shown to the right. the chord models of GU whenever GU contains some articulation point.…

**Figure 8.4.** Figure 8.4: The placements and the orientations of φ(u1) and φ(u4) for the case: u1 ∈ left(u3), u3 ∈ right(u1), u4 ∈ left(u2) and u2 ∈ left(u4). Now we are ready to prove the first step of Property (P1). Let U be the set containing a vertex from every child Mi of Q. In particula…

**Figure 8.5.** Figure 8.5: A probe (y, x, X, α(X)) in (U, ∼) and the vertices t1, t2, t3 from U r P. Claim 8.6. Let (y, x, X, α(X)) be a probe in (U, ∼) and let P = {x, y}∪X ∪α(X). Then, the graph (P, ∼) has a unique, up to reflection, conformal model. Proof. Let Z = {z ∈ X : z k (P r {x, z})}…

**Figure 8.6.** Figure 8.6: To the left: maximal non-trivial split (A, B) with A ∪ B = C1 ∪. . .∪ C4. We have I2 = {1, 2, 3}, I1 = {4}, (b3, a3, C2, α(C2)) is a probe in (U, ∼). In the middle: maximal trivial split (A, B) with A = {a} and B = C1 ∪ C2 ∪ C3. We have I2 = {1, 2}, I1 = {3}, (a1, a,…

**Figure 8.7.** Figure 8.7: Extending φ by the chord φ(a4). To the left: (A, B) is nontrivial, A∪B = C1 ∪. . .∪C4, I2 = {1, 2, 3}, and I1 = {4}. The chord φ(a4) induces a partition (X, Y ) = ({b3}, {b1, b2}). The only conformal model φ 0 of (U, ∼) extending φ 0 R is π1π ′ 3π2a 0 4π ′ 1π3π ′ 2a…

**Figure 8.8.** Figure 8.8: Probes (a2, a, M1, α(M1)) and (a2, a, M2, α(M2)) in ({a2, a}∪ C1 ∪ α(C1), ∼). Module M in ({a} ∪ C1 ∪ α(C1)) is surrounded by a red dashed line. The components of (α(C1), ∼) are are marked in dark gray. Now, note that for every component D of the graph (α(C1), ∼) we …

**Figure 8.9.** Figure 8.9: Examples of conformal models φ1, φ2 of (U, ∼) extending a 0a 1 2a 1a 0 2 : M1 = {x1, x2, x3}, α(M1) = {u1, u2}, M2 = {y1, y2, y3}, α(M2) = {v1, v2}. The chords representing the vertices from M1 ∪ α(M1) are in red, the chords representing the vertices from M2 ∪ α(M2) …

**Figure 8.10.** Figure 8.10: To prove (2) we need to show that for every v, w ∈ Mi the statements (8.8.3) and (8.8.4) are equivalent, where: (8.8.3) {left(v) ∩ (U r Mi), right(v) ∩ (U r Mi)} = {left(w) ∩ (U r Mi), right(w) ∩ (U r Mi)}. (8.8.4) {left(v) ∩ (Q r Mi), right(v) ∩ (Q r Mi)} = {left(w…

**Figure 8.** Figure 8: to the left. Since [PITH_FULL_IMAGE:figures/full_fig_p062_8.png]

**Figure 8.11.** Figure 8.11: Suppose φ(x) and φ(y) intersect – see [PITH_FULL_IMAGE:figures/full_fig_p063_8_11.png]

**Figure 8.12.** Figure 8.12: We claim that there is v ∈ Q r Mi such that φ(v) has both its ends either between l 3 and r 0 or between r 3 and l 0 . Assume otherwise. Let T be the set of all t ∈ Q such that φ(t) has one end between l 3 and r 0 and the other end between r 3 and l 0 . We show that…

**Figure 9.1.** Figure 9.1: are two different vertices rq, rp ∈ Rj−1 such that φ ′ Qk{rq, rp} ∗ ≡ φQk{rq, rp} ∗ ≡ r 0 p r 0 q r 1 p r 1 q , but the chords φQ(rj ) and φ ′ Q(rj ) have its endpoints in different sections r 0 p r 0 q , r 0 q r 1 p , r 1 p r 1 q , r 1 q r 0 q of the circular word r…

**Figure 9.** Figure 9: for an illustration. Note that there is no letter from [PITH_FULL_IMAGE:figures/full_fig_p068_9.png]

**Figure 9.2.** Figure 9.2: Suppose K is a member of K(Q) for some prime/serial component Q ∈ Q. For every strong module L in M(K, ∼) and every extended conformal model φQ of (Q, ∼) we denote by: • L 0 and L 1 the sets K0 ∩ L ∗ and K1 ∩ L ∗ , respectively, • τ (φQ, Lj ) the shortest contiguous …

**Figure 9.3.** Figure 9.3: L is prime. We replace L in S(K) by L1, L2, L3, L4; L1, L2 are active, L3, L4 are inactive. Suppose L is an active member in S(K) such that L is serial. Suppose R1, . . . , Rt are the children of L, enumerated such that for every i < j the letters from R0 i appear be…

**Figure 9.4.** Figure 9.4: L is serial, S(L) = {R1, R2, R3 ∪ R4, R5}. We replace L in S(K) by R1, R2, R3 ∪ R4, R5; R2 is active, R1, R3 ∪ R4, R5 are inactive. To show that Invariant (I2) is kept it is enough to show Li ≺φ′ Lj for every i < j. Suppose Rp, Rq are children of L such that Rp ⊆ Li …

**Figure 9.5.** Figure 9.5: L is parallel. We replace L in S(K) by R1, R2 ∪ R3, R4; R4 is active, R1, R2 ∪ R3 are inactive. First, we prove that the set S(K) satisfies Properties (R1)–(R3). Property (R1) is obviously satisfied. Property (R2) follows by Invariant (I2) and by the fact that, whene…

**Figure 10.1.** Figure 10.1: The letters P ′ 1 , P′ 2 , P′ 3 , P′ 4 are merged to a single P-node P = {Q1, Q2, Q3, Q4}. Given the set of P-nodes, the extended conformal models φ[Q], and the CA-modules of G, we can compute easily T and the sets Π(·) for all inner nodes of T. 11. Linear-time cano…

**Figure 11.1.** Figure 11.1: The pair (L 0 1 , L0 2 , L0 3 , L0 4 ),(L 1 2 , L1 4 , L1 1 , L1 3 ) is in Π(L 0 ). Assuming Num = 0 we have canon L, [PITH_FULL_IMAGE:figures/full_fig_p077_11_1.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Comments on "$\mathcal{O}(m\cdot n)$ algorithms for the recognition and isomorphism problems on circular-arc graphs"
cs.DS 2024-11 conditional novelty 6.0 of 10

Hsu's 1995 decomposition trees for circular-arc graphs do not correctly describe all normalized intersection models, and the paper supplies counterexamples.

Reference graph

Works this paper leans on

28 extracted references · 24 canonical work pages · cited by 1 Pith paper

[1]

Aho, John E

Alfred V. Aho, John E. Hopcroft, and Jeﬀrey D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974

1974
[2]

Graph isomorphism in quasipolynomial time [extende d abstract]

L´ aszl´ o Babai. Graph isomorphism in quasipolynomial time [extende d abstract]. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016 , pages 684–697. ACM, 2016

work page 2016
[3]

Kellogg S. Booth. Lexicographically least circular substrings. Inf. Process. Lett. , 10(4/5):240–242, 1980

work page 1980
[4]

Booth and George S

Kellogg S. Booth and George S. Lueker. Testing for the consecu tive ones property, interval graphs, and graph planarity using pq-tree algorithms. J. Comput. Syst. Sci. , 13(3):335–379, 1976

1976
[5]

Deciding circular-arc graph isomorphism in para meterized logspace

Maurice Chandoo. Deciding circular-arc graph isomorphism in para meterized logspace. In 33rd Sym- posium on Theoretical Aspects of Computer Science, STACS 20 16, February 17-20, 2016, Orl´ eans, France, volume 47 of LIPIcs, pages 26:1–26:13. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Info rmatik, 2016

work page 2016
[6]

Extending pa rtial representations of circle graphs

Steven Chaplick, Radoslav Fulek, and Pavel Klav ´ ık. Extending pa rtial representations of circle graphs. J. Graph Theory , 91(4):365–394, 2019

work page 2019
[7]

Cunningham

William H. Cunningham. Decomposition of directed graphs. SIAM J. Algebraic Discrete Methods , 3(2):214–228, 1982

work page 1982
[8]

Curtis, Min Chih Lin, Ross M

Andrew R. Curtis, Min Chih Lin, Ross M. McConnell, Yahav Nussbaum , Francisco J. Soulignac, Jeremy P. Spinrad, and Jayme Luiz Szwarcﬁter. Isomorphism of gr aph classes related to the circular- ones property. Discret. Math. Theor. Comput. Sci. , 15(1):157–182, 2013

2013

Show all 28 references

[9]

Ben Dushnik and E. W. Miller. Partially ordered sets. Amer. J. Math. , 63:600–610, 1941

1941
[10]

Circular-arc graph recognition and related problems

Elaine Eschen. Circular-arc graph recognition and related problems . ProQuest LLC, Ann Arbor, MI,
[11]

Gabor, Kenneth J

Csaba P. Gabor, Kenneth J. Supowit, and Wen-Lian Hsu. Recog nizing circle graphs in polynomial time. J. ACM , 36(3):435–473, 1989

1989
[12]

Transitiv orientierbare Graphen

Tibor Gallai. Transitiv orientierbare Graphen. Acta Math. Acad. Sci. Hung. , 18(1–2):25–66, 1967. 84 T. KRA WCZYK

1967
[13]

Garey, David S

Michael R. Garey, David S. Johnson, Gerald L. Miller, and Christo s H. Papadimitriou. The com- plexity of coloring circular arcs and chords. SIAM J. Algebraic Discret. Methods , 1(2):216–227, 1980

1980
[14]

O(m*n) algorithms for the recognition and isomor phism problems on circular-arc graphs

Wen-Lian Hsu. O(m*n) algorithms for the recognition and isomor phism problems on circular-arc graphs. SIAM J. Comput. , 24(3):411–439, 1995

1995
[15]

Circle graph isomorp hism in almost linear time

V ´ ıt Kalisz, Pavel Klav ´ ık, and Peter Zeman. Circle graph isomorp hism in almost linear time. In Theory and Applications of Models of Computation - 17th Annu al Conference, TAMC 2022, Tianjin, China, September 16-18, 2022, Proceedings , volume 13571 of Lecture Notes in Com...

2022
[16]

On the isomorphism problem for Helly circular-arc graphs

Johannes K¨ obler, Sebastian Kuhnert, and Oleg Verbitsky. On the isomorphism problem for Helly circular-arc graphs. Inf. Comput. , 247:266–277, 2016

2016
[17]

Testing isomorphism of circular-arc graphs - Hsu’s approach revisited

Tomasz Krawczyk. Testing isomorphism of circular-arc graphs - Hsu’s approach revisited. CoRR, abs/1904.04501, 2019

1904 arXiv
[18]

O(m·n) algorithms for the recognition and isomorphism problems on circular-arc graphs

Tomasz Krawczyk. Comments on“ O(m·n) algorithms for the recognition and isomorphism problems on circular-arc graphs”. CoRR, abs/2411.13708, 2024

2024 arXiv
[19]

Soulignac, and Jayme Luiz Szwarcﬁter

Min Chih Lin, Francisco J. Soulignac, and Jayme Luiz Szwarcﬁter. A simple linear time algorithm for the isomorphism problem on proper circular-arc graphs. In Algorithm Theory - SWAT 2008, 11th Scandinavian Workshop on Algorithm Theory, Gothenburg, Sw eden, July 2-4, 2008, Proc...

2008
[20]

Lueker and Kellogg S

George S. Lueker and Kellogg S. Booth. A linear time algorithm for deciding interval graph isomor- phism. J. ACM , 26(2):183–195, 1979

1979
[21]

McConnell

Ross M. McConnell. Linear-time recognition of circular-arc grap hs. Algorithmica, 37(2):93–147, 2003

2003
[22]

McConnell and Jeremy P

Ross M. McConnell and Jeremy P. Spinrad. Modular decompositio n and transitive orientation. Discret. Math., 201(1-3):189–241, 1999

1999
[23]

Graphes de cordes : une caract´ erisation et ses application s

Walid Naji. Graphes de cordes : une caract´ erisation et ses application s. (Chordal graphs: a charac- terization and its applications) . 1985

1985
[24]

Jeremy P. Spinrad. Circular-arc graphs with clique cover numbe r two. J. Comb. Theory B , 44(3):300– 306, 1988

1988
[25]

Alan C. Tucker. An eﬃcient test for circular-arc graphs. SIAM J. Comput. , 9(1):1–24, 1980

1980
[26]

T. Wu. An O(n3) isomorphism test for circular-arc graphs. 1983. Thesis (Ph.D.)

1983
[27]

Enumeration of noniso- morphic interval graphs and nonisomorphic permutation graphs

Kazuaki Yamazaki, Toshiki Saitoh, Masashi Kiyomi, and Ryuhei Uehara. Enumeration of noniso- morphic interval graphs and nonisomorphic permutation graphs. Theor. Comput. Sci. , 806:310–322, 2020. (T. Krawczyk) F aculty of Mathematics and Information Science, W arsaw Uni versity...

2020
[1997]

Thesis (Ph.D.)–Vanderbilt University

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.

[1] [1]

Aho, John E

Alfred V. Aho, John E. Hopcroft, and Jeﬀrey D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974

1974

[2] [2]

Graph isomorphism in quasipolynomial time [extende d abstract]

L´ aszl´ o Babai. Graph isomorphism in quasipolynomial time [extende d abstract]. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016 , pages 684–697. ACM, 2016

work page 2016

[3] [3]

Kellogg S. Booth. Lexicographically least circular substrings. Inf. Process. Lett. , 10(4/5):240–242, 1980

work page 1980

[4] [4]

Booth and George S

Kellogg S. Booth and George S. Lueker. Testing for the consecu tive ones property, interval graphs, and graph planarity using pq-tree algorithms. J. Comput. Syst. Sci. , 13(3):335–379, 1976

1976

[5] [5]

Deciding circular-arc graph isomorphism in para meterized logspace

Maurice Chandoo. Deciding circular-arc graph isomorphism in para meterized logspace. In 33rd Sym- posium on Theoretical Aspects of Computer Science, STACS 20 16, February 17-20, 2016, Orl´ eans, France, volume 47 of LIPIcs, pages 26:1–26:13. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Info rmatik, 2016

work page 2016

[6] [6]

Extending pa rtial representations of circle graphs

Steven Chaplick, Radoslav Fulek, and Pavel Klav ´ ık. Extending pa rtial representations of circle graphs. J. Graph Theory , 91(4):365–394, 2019

work page 2019

[7] [7]

Cunningham

William H. Cunningham. Decomposition of directed graphs. SIAM J. Algebraic Discrete Methods , 3(2):214–228, 1982

work page 1982

[8] [8]

Curtis, Min Chih Lin, Ross M

Andrew R. Curtis, Min Chih Lin, Ross M. McConnell, Yahav Nussbaum , Francisco J. Soulignac, Jeremy P. Spinrad, and Jayme Luiz Szwarcﬁter. Isomorphism of gr aph classes related to the circular- ones property. Discret. Math. Theor. Comput. Sci. , 15(1):157–182, 2013

2013