Circle Graph Isomorphism in Almost Linear Time

Pavel Klav\'ik; Peter Zeman; V\'it Kalisz

REVIEW 2 major objections 4 minor 44 references

Circle Graph Isomorphism in Almost Linear Time

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

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

Pith's one-line read Circle graph isomorphism now solvable in almost linear time

desk verdict A solid almost-linear isomorphism algorithm for circle graphs, but the tree-canonization lemma has an unpatched edge case that invalidates the theorem as written; worth a round of revision. read the letter →

arxiv 1908.09151 v1 pith:KISJFHEK submitted 2019-08-24 cs.DS cs.DMmath.CO

Vít Kalisz , Pavel Klavík , Peter Zeman This is my paper · ORCID

classification cs.DScs.DMmath.CO MSC 05C6005C6268R10

keywords circlegraphsgraphisomorphismcanonizationsplitdecompositionminimaltreerepresentationsalmostlineartimeinverseAckermannfunction

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 establishes that the graph isomorphism problem for circle graphs, the intersection graphs of chords of a circle, can be solved in time $O((n+m)\alpha(n+m))$, where $n$ and $m$ are the numbers of vertices and edges and $\alpha$ is the inverse Ackermann function. It also produces a canonical string for each circle graph in the same time, so two circle graphs are isomorphic exactly when their canonical strings are equal. The result matters because it replaces the previous $O(nm)$ algorithm and brings isomorphism testing in line with the fastest known recognition algorithm for the class. The argument works by decomposing a circle graph into its unique minimal split tree, canonizing the small prime pieces, and assembling their canonical forms bottom-up.

What carries the argument

The load-bearing object is the minimal split tree of a graph: the unique graph-labeled tree obtained by recursively cutting a connected graph along splits (complete-bipartite cuts) until only prime and degenerate graphs remain, with no two neighboring pieces joinable back into a degenerate graph. Each node carries a graph, and neighboring nodes are linked through marker vertices; the original graph is recovered by joining marker-adjacent nodes. The algorithm also uses a canonical rotational encoding of a circle representation: for each chord endpoint it records the color of its vertex and the clockwise gap to the other endpoint of the same chord, producing a circular string whose lexicographically minimal rotation is invariant under relabeling. The canonization of the whole graph is assembled by processing the tree layer by layer from the leaves to the root, replacing each node by an encoding that summarizes its entire rooted subtree.

What would settle it

The decisive test is to search for two non-isomorphic connected circle graphs whose minimal split trees are isomorphic; any such pair would produce identical canonical strings and refute the claimed equivalence.

Watch

Extended reading notes

Core claim

The central discovery is a reduction: two connected circle graphs are isomorphic if and only if their minimal split trees are isomorphic, and this tree is unique for each connected graph. A circle graph's minimal split tree has only two kinds of nodes, prime circle graphs, each of which has at most one circle representation up to reversal, and degenerate graphs (complete graphs and stars), whose canonization is immediate. The paper gives a linear-time canonization of circle representations themselves, encodes the unique minimal split tree node by node, and then runs a bottom-up color refinement on the tree whose final color word is a canonical string for the whole graph. Because the minimal split tree can be computed in $O((n+m)\alpha(n+m))$ time, the whole canonization, and hence isomorphism testing, runs in the same bound; with a circle representation supplied as input, the bound improves to $O(n+m)$.

Load-bearing premise

The load-bearing premise is that the minimal split tree is a perfect fingerprint: two connected graphs are isomorphic exactly when their uniquely determined minimal split trees are isomorphic.

Editorial extensions

If this is right

Circle graph isomorphism and canonization can be tested in $O((n+m)\alpha(n+m))$ time for all inputs, and in $O(n+m)$ time when a circle representation is given.
The output is a true canonical form: the same circle graph always produces the same string, so repeated or distributed isomorphism queries reduce to string comparison.
The canonical-form algorithm doubles as a recognition test: if any prime node fails to have a circle representation, the input graph is not a circle graph.
Because proper circular-arc graphs form a subclass of circle graphs, their isomorphism also becomes decidable in almost linear time.
The bottom-up tree canonization is generic: any graph class closed under split decomposition and supplied with a linear-time canonization for its prime and degenerate pieces inherits an almost linear-time isomorphism test.

Reading between the lines

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

The same pipeline suggests a route to a logarithmic-space isomorphism test for circle graphs: if minimal split-tree construction and circular-string canonization can be implemented in logspace, the bottom-up encoding would likely carry through; the paper leaves this question open.
The paper's open question about partial representation extension could be attacked through minimal split trees: because the canonical encoding stores all node representations up to reversal, a partial representation might be checked against it by local consistency, potentially improving on the stated $O(n^3)$ benchmark.
The inverse-Ackermann factor is the exact cost of the recognition and minimal-split-tree subroutine; a future linear-time recognition algorithm would automatically upgrade the $O((n+m)\alpha(n+m))$ result to $O(n+m)$.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

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

First thing to know: this paper likely contains a correct O((n+m)α(n+m)) algorithm for circle graph isomorphism, improving Hsu's O(nm). The high-level architecture is sound: compute the minimal split tree, canonize the node labels, then canonize the tree. The meta-algorithm for graph-labeled trees (Lemma 3.2) is a genuine new tool, and the linear canonization of circle representations in Section 4 looks right.

The soft spots are in the proof details. The stress-test note is correct: Section 3's rooting step inserts a single-vertex node on a central edge, and that node is incident to two tree edges. That violates Definition 2.1 and, more concretely, breaks the coloring because two child subtrees would both write to the same parent marker vertex. So Lemma 3.2 as stated is undefined for edge-centered trees. Since minimal split trees of connected circle graphs can have two nodes joined by one edge, Theorem 1.1 is not established as written. This is a repair, not a fatal flaw—you could handle the edge center by rooting at the two sides and comparing carefully—but the manuscript doesn't include the patch.

Also, the converse direction of Lemma 2.5 skips the argument that the image of a minimal split decomposition under isomorphism is minimal. That's a short omission; minimality is isomorphism-invariant, so the step can be filled without difficulty. I would not call it a deep problem.

The paper depends on heavy external machinery (split decomposition, Gioan et al.), which makes verification slow, but the citations look appropriate, and I saw no circularity.

Who should read this: people working on graph isomorphism for structured classes and anyone who wants to use split decomposition as a canonicalization tool. I would bring it to my reading group. As a referee, I would ask for a fix to the edge-centered case and a clean statement of Lemma 2.5; after that, the result is publishable.

Referee Report

2 major / 4 minor

Summary. The paper presents an algorithm for testing isomorphism and computing canonical forms of circle graphs in time O((n+m)alpha(n+m)), improving the previous O(nm) bound of Hsu. The approach is to reduce the problem to canonizing the unique minimal split tree of the graph: for a connected graph the minimal split tree is unique (Cunningham), its nodes are prime or degenerate circle graphs, prime circle graphs have unique circle representations up to reversal, and the recognition algorithm of Gioan et al. computes the minimal split tree together with those representations in almost linear time. The authors give a meta-algorithm that canonizes graph-labeled trees when a linear canonization for the node labels is available, and provide linear-time canonizations for prime and degenerate circle graphs. For disconnected graphs the component encodings are sorted. The paper also gives an O(n+m) bound when a circle representation is supplied as input, and discusses open problems on Weisfeiler-Leman dimension, logspace algorithms, and partial representation extension.

Significance. If correct, the result is a substantial improvement: it gives an almost linear-time isomorphism test and canonical form for circle graphs, matching the complexity of circle graph recognition and providing a clean structural algorithm via minimal split decomposition. The paper is clearly written and builds on solid external results; the meta-algorithm for graph-labeled trees is a reusable tool. The claimed running time is concrete and falsifiable, and the algorithm is structured so that the only super-linear bottleneck is the recognition/decomposition subroutine. However, the proof as written contains a gap in the canonization of edge-centered graph-labeled trees, which affects the main theorem, and a smaller omission in Lemma 2.5. Both appear repairable, so the central approach seems sound.

major comments (2)

[Section 3, Lemma 3.2] The rooting step for edge-centered trees is invalid under the paper's own definitions. The sentence "If a tree edge is central, we insert there another node having a single vertex" produces a vertex incident to two tree edges, directly contradicting Definition 2.1 ("no vertex is incident to two tree edges"). The subsequent coloring mechanism also fails: a single-vertex root would be the parent marker vertex for both incident child subtrees, so the two children would assign their colors to the same vertex, and one assignment would overwrite the other. This case is not excluded by the application: a minimal split tree can have exactly two nodes joined by one tree edge (for example, the minimal split tree of K_{2,3} consists of two star nodes), and then the center is an edge. Since Section 5 applies Lemma 3.2 to every connected circle graph, Theorem 1.1 is not established as written for such graphs. The authors should add a treatment of central edges, for instance by canonizing the two rooted subtrees on either side of the central edge and combining their encodings in a canonical order; alternatively they may insert a two-vertex root gadget that satisfies Definition 2.1 and define the parent-marker mechanism for it.
[Section 2, Lemma 2.5] The converse direction of Lemma 2.5 begins with a minimal split decomposition D_G of G, applies an isomorphism pi to obtain a split decomposition D_H of H, and then invokes Theorem 2.3 to conclude that the minimal split tree of H is isomorphic to the constructed T_H. The missing step is the verification that D_H is minimal. This follows because isomorphism preserves the terminal-node types (prime/degenerate) and the condition that no two neighboring degenerate nodes can be joined, but the argument is not given. Since uniqueness of the minimal split tree applies only to minimal split decompositions, the converse direction of the lemma is currently incomplete.

minor comments (4)

[Section 4, Lemma 4.3] The statement of Lemma 4.3 needs a precondition: for prime circle graphs, the O(n) canonization uses a circle representation as auxiliary input. Without a representation, even reading a dense graph may require Omega(n+m) time. In Section 5 such representations are available from Theorem 2.4, but the interface to Lemma 3.2 should state that the canonization subroutine may depend on auxiliary data attached to the nodes.
[Section 3, Lemma 3.2] The final encoding is described as "an encoded concatenation" of variable-length sequences epsilon(2),...,epsilon(c); to make the encoding explicitly decodable, the paper should specify how the boundaries between entries are marked (for example, by prefixing each sequence by its length).
[Section 4, Canonization of Degenerate Graphs] A graph that is both complete and a star (such as K_2) can receive two different canonical encodings depending on whether it is classified as complete or star. The authors should specify a deterministic tie-breaking between the two degenerate types (or exclude such graphs from one of the cases) so that gamma is a well-defined function on isomorphism classes.
[Throughout] Typographical errors: "cannonical" for "canonical" (throughout), "Cunnigham" for "Cunningham" (abstract and reference [10]), "incidance" for "incidence" (Definition 2.1), "the the lexicographically minimal" (Section 4), "an cycle canonization" (Lemma 4.2), and "faster that O(n^3)" (Problem 6.4).

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: all load-bearing steps rest on external theorems and independent algorithmic subroutines.

full rationale

The derivation chain of Theorem 1.1 is self-contained rather than circular. The paper reduces circle graph isomorphism to isomorphism of minimal split trees, using Cunningham's uniqueness theorem for minimal split trees (Theorem 2.3), the Gioan et al. minimal split tree computation and circle graph recognition algorithm (Theorem 2.4), and the uniqueness of prime circle graph representations up to reversal, all as external prior results. The canonization meta-algorithm of Section 3 is proved by an explicit induction (Lemma 3.3) and complexity analysis (Lemma 3.4), and the node canonizations in Section 4 are direct combinatorial encodings of colored complete graphs, stars, and circle representations. No parameter is fitted to the target graphs, no predicted quantity is defined in terms of the output, and no load-bearing argument reduces to a self-citation; the self-references in the bibliography concern related open problems and prior work by the same authors on other graph classes, not the main theorem. The reviewer-identified issue with rooting at an edge center is a definitional gap in the graph-labeled tree formalism, not a circularity: it makes part of the proof incomplete as written, but it does not make the claimed result equivalent to its own inputs. Accordingly, no circular step is present and the appropriate score is 0.

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

No free parameters or invented entities are introduced; this is an algorithms paper. The central claim rests entirely on prior structural theorems about split decomposition and circle graph representations, listed above.

assumptions (5)

standard math Cunningham's theorem: every connected graph has a unique minimal split tree, and graph isomorphism is equivalent to minimal split tree isomorphism.
The paper's reduction in Lemma 2.5 and the uniqueness invoked in that proof come from Cunningham [10], Theorem 2.3, and are not reproved.
standard math Split decomposition preserves the property of being a circle graph in both directions (Lemma 2.2).
Used to conclude that every node of the minimal split tree of a circle graph is itself a circle graph; cited to Spinrad [43].
standard math Every prime circle graph has at most two circle representations, one the reversal of the other.
This is the basis for the linear canonization of prime nodes in Section 4; cited to [13]. If this theorem failed, the canonical encoding of prime nodes would be undefined.
domain assumption The Gioan et al. algorithm computes the minimal split tree of a circle graph, and the unique representation of each prime node, in O((n+m)α(n+m)) time.
This is Theorem 2.4 and is the bottleneck of the paper's main algorithm; correctness and complexity are adopted from [20,21].
domain assumption When a circle representation is supplied, a split decomposition and minimal split tree can be computed in O(n+m) time by the algorithm of Dahlhaus [13].
Used only for the strengthened O(n+m) bound when the input includes a representation.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Circle Graph Isomorphism in Almost Linear Time." pith.science (2026). https://pith.science/paper/KISJFHEK

@misc{pith2026190809151,
  author       = {Pith},
  title        = {Pith review of: Circle Graph Isomorphism in Almost Linear Time},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/KISJFHEK}},
  note         = {Machine review of arXiv:1908.09151}
}

abstract

Circle graphs are intersection graphs of chords of a circle. In this paper, we present a new algorithm for the circle graph isomorphism problem running in time $O((n+m)\alpha(n+m))$ where $n$ is the number of vertices, $m$ is the number of edges and $\alpha$ is the inverse Ackermann function. Our algorithm is based on the minimal split decomposition [Cunnigham, 1982] and uses the state-of-art circle graph recognition algorithm [Gioan, Paul, Tedder, Corneil, 2014] in the same running time. It improves the running time $O(nm)$ of the previous algorithm [Hsu, 1995] based on a similar approach.

Figures

Figures reproduced from arXiv: 1908.09151 by the authors.

**Figure 2.** On the left, a split in G between A and B. On the right, application of this split produces graphs GA and GB with newly created marker vertices denoted by big white circles. Outline. Section 2 gives an overview of minimal split decomposition and minimal split trees. In Section 3, we describe a meta-algorithm computing cannonical form of a general tree whose nodes are labeled by graphs for which a linear-time cannoni… view at source ↗

**Figure 3.** An example of a split tree T of a split decomposition D ending with highlighted prime and degenerate graphs (see the definition below). The split decomposition D is not minimal: the gray and purple stars can be joined in T to form the minimal split tree TG in the box. 5 [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗

Figures from the paper (1 more)

**Figure 4.** Figure 4: On the left, circle representations RA and RB of graphs GA and GB. They are combined into a circle representation R of G. Computation of Minimal Split Trees. The minimal split tree can be computed in time O(n+ m) using the algorithm of [13]. For the purpose of this pap…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

44 extracted references · 44 canonical work pages

[1]

A. V. Aho, J. E. Hopcroft, and J. D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley Publishing Company, 1974

work page 1974
[2]

L. Babai. Graph isomorphism in quasipolynomial time. In STOC, 2016

work page 2016
[3]

Completing orientations of partially oriented graphs

J. Bang-Jensen, J. Huang, and X. Zhu. Completing orientations of partially oriented graphs. CoRR, abs/1509.01301, 2015

work page Pith review arXiv 2015
[4]

Lexicographically least circular substrings

Kellogg S Booth. Lexicographically least circular substrings. Information Processing Let- ters, 10(4-5):240–242, 1980

work page 1980
[5]

A. Bouchet. Reducing prime graphs and recognizing circle graphs. Combinatorica, 7(3):243– 254, 1987

work page 1987
[6]

A. Bouchet. Unimodularity and circle graphs. Discrete Mathematics, 66(1-2):203–208, 1987

work page 1987
[7]

Deciding circular-arc graph isomorphism in parameterized logspace

Maurice Chandoo. Deciding circular-arc graph isomorphism in parameterized logspace. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016) . Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016

work page 2016
[8]

Extending Partial Representations of Circle Graphs

S. Chaplick, R. Fulek, and P. Klav´ ık. Extending partial representations of circle graphs. CoRR, abs/1309.2399, 2015. 11

work page Pith review arXiv 2015

Show all 44 references

[9]

C. J. Colbourn. On testing isomorphism of permutation graphs. Networks, 11(1):13–21, 1981

1981
[10]

Decomposition of directed graphs

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

1982
[11]

A combinatorial decomposition theory

William H Cunningham and Jack Edmonds. A combinatorial decomposition theory. Cana- dian Journal of Mathematics , 32(3):734–765, 1980

1980
[12]

A. R. Curtis, M. C. Lin, R. M. McConnell, Y. Nussbaum, F. J. Soulignac, J. P. Spinrad, and J. L. Szwarcﬁter. Isomorphism of graph classes related to the circular-ones property. Discrete Mathematics and Theoretical Computer Science , 15(1):157–182, 2013

2013
[13]

Dahlhaus

E. Dahlhaus. Parallel algorithms for hierarchical clustering and applications to split de- composition and parity graph recognition. Journal of Algorithms , 36(2):205–240, 1998

1998
[14]

de Fraysseix

H. de Fraysseix. Local complementation and interlacement graphs. Discrete Mathematics, 33(1):29–35, 1981

1981
[15]

de Fraysseix and P

H. de Fraysseix and P. O. de Mendez. On a characterization of gauss codes. Discrete & Computational Geometry, 22(2):287–295, 1999

1999
[16]

Forestal algebras and al- gebraic forests (on a new class of weakly compact graphs)

Sergei Evdokimov, Ilia Ponomarenko, and Gottfried Tinhofer. Forestal algebras and al- gebraic forests (on a new class of weakly compact graphs). Discrete Mathematics, 225(1- 3):149–172, 2000

2000
[17]

Even and A

S. Even and A. Itai. Queues, stacks, and graphs. Theory of Machines and Computation (Z. Kohavi and A. Paz, Eds.) , pages 71–76, 1971

1971
[18]

Fiala, P

J. Fiala, P. Klav´ ık, J. Kratochv´ ıl, and R. Nedela. 3-connected reduction for regular graph covers. CoRR, abs/1503.06556, 2017

2017 arXiv
[19]

C. P. Gabor, K. J. Supowit, and W. Hsu. Recognizing circle graphs in polynomial time. J. ACM, 36(3):435–473, 1989

1989
[20]

Gioan, C

E. Gioan, C. Paul, M. Tedder, and D. Corneil. Practical and eﬃcient circle graph recogni- tion. Algorithmica, 69(4):759–788, 2014

2014
[21]

Gioan, C

E. Gioan, C. Paul, M. Tedder, and D. Corneil. Practical and eﬃcient split decomposition via graph-labelled trees. Algorithmica, 69(4):789–843, 2014

2014
[22]

Descriptive complexity, canonisation, and deﬁnable graph structure theory , volume 47

Martin Grohe. Descriptive complexity, canonisation, and deﬁnable graph structure theory , volume 47. Cambridge University Press, 2017

2017
[23]

J. E. Hopcroft and J. Wong. Linear time algorithm for isomorphism of planar graphs. In STOC, pages 172–184. ACM, 1974

1974
[24]

W. L. Hsu. O(M·N) algorithms for the recognition and isomorphism problems on circular- arc graphs. SIAM Journal on Computing , 24(3):411–439, 1995

1995
[25]

Kawarabayashi, P

K. Kawarabayashi, P. Klav´ ık, B. Mohar, R. Nedela, and P. Zeman. Isomorphisms of maps on the sphere. to appear in Contemporary Mathematics AMS , 2019

2019
[26]

The weisfeiler-leman dimension of planar graphs is at most 3

Sandra Kiefer, Ilia Ponomarenko, and Pascal Schweitzer. The weisfeiler-leman dimension of planar graphs is at most 3. In 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) , pages 1–12. IEEE, 2017. 12

2017
[27]

Klav´ ık, D

P. Klav´ ık, D. Knop, and P. Zeman. Graph isomorphism restricted by lists. CoRR, abs/1607.03918, 2016

2016 arXiv
[28]

Klav´ ık, J

P. Klav´ ık, J. Kratochv´ ıl, Y. Otachi, I. Rutter, T. Saitoh, M. Saumell, and T. Vyskoˇ cil. Ex- tending partial representations of proper and unit interval graphs.Algorithmica, 77(4):1071– 1104, 2017

2017
[29]

Klav´ ık, J

P. Klav´ ık, J. Kratochv´ ıl, Y. Otachi, and T. Saitoh. Extending partial representations of subclasses of chordal graphs. Theoretical Computer Science, 576:85–101, 2015

2015
[30]

Klav´ ık, J

P. Klav´ ık, J. Kratochv´ ıl, Y. Otachi, T. Saitoh, and T. Vyskoˇ cil. Extending partial repre- sentations of interval graphs. Algorithmica, 2016

2016
[31]

Klav´ ık and P

P. Klav´ ık and P. Zeman. Automorphism groups of geometrically represented graphs. In 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015 , volume 30 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 540–553, 2015

2015
[32]

Interval graphs: Canonical representations in logspace.SIAM Journal on Computing, 40(5):1292–1315, 2011

Johannes K¨ obler, Sebastian Kuhnert, Bastian Laubner, and Oleg Verbitsky. Interval graphs: Canonical representations in logspace.SIAM Journal on Computing, 40(5):1292–1315, 2011

2011
[33]

Helly circular-arc graph iso- morphism is in logspace

Johannes K¨ obler, Sebastian Kuhnert, and Oleg Verbitsky. Helly circular-arc graph iso- morphism is in logspace. In International Symposium on Mathematical Foundations of Computer Science, pages 631–642. Springer, 2013

2013
[34]

Krawczyk and B

T. Krawczyk and B. Walczak. Extending partial representations of trapezoid graphs. In WG 2017, Lecture Notes in Computer Science, 2017

2017
[35]

A simple linear time algorithm for the isomorphism problem on proper circular-arc graphs, 2008

Min Chih Lin, Francisco J Soulignac, and Jayme L Szwarcﬁter. A simple linear time algorithm for the isomorphism problem on proper circular-arc graphs, 2008

2008
[36]

G. S. Lueker and K. S. Booth. A linear time algorithm for deciding interval graph isomor- phism. Journal of the ACM (JACM) , 26(2):183–195, 1979

1979
[37]

W. Naji. Graphes de Cordes: Une Caracterisation et ses Applications . PhD thesis, l’Universit´ e Scientiﬁque et M´ edicale de Grenoble, 1985

1985
[38]

Testing isomorphism of circular-arc graphs in polynomial time

Roman Nedela, Ilia Ponomarenko, and Peter Zeman. Testing isomorphism of circular-arc graphs in polynomial time. arXiv preprint arXiv:1903.11062 , 2019

1903 arXiv
[39]

S. Oum. Rank-width and vertex-minors. J. Comb. Theory, Ser. B , 95(1):79–100, 2005

2005
[40]

Sch¨ oning

U. Sch¨ oning. Graph isomorphism is in the low hierarchy.Journal of Computer and System Sciences, 37(3):312–323, 1988

1988
[41]

Fast canonization of circular strings

Yossi Shiloach. Fast canonization of circular strings. Journal of algorithms , 2(2):107–121, 1981

1981
[42]

J. P. Spinrad. Recognition of circle graphs. J. of Algorithms , 16(2):264–282, 1994

1994
[43]

J. P. Spinrad. Eﬃcient Graph Representations. Field Institute Monographs, 2003

2003
[44]

Weisfeiler and A.A

B. Weisfeiler and A.A. Leman. A reduction of a graph to a canonical form and an algebra arising during this reduction. Nauchno-Technicheskaya Informatsiya, 9:12–16, 1968. 13

1968

Pith tools

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

[1] [1]

A. V. Aho, J. E. Hopcroft, and J. D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley Publishing Company, 1974

work page 1974

[2] [2]

L. Babai. Graph isomorphism in quasipolynomial time. In STOC, 2016

work page 2016

[3] [3]

Completing orientations of partially oriented graphs

J. Bang-Jensen, J. Huang, and X. Zhu. Completing orientations of partially oriented graphs. CoRR, abs/1509.01301, 2015

work page Pith review arXiv 2015

[4] [4]

Lexicographically least circular substrings

Kellogg S Booth. Lexicographically least circular substrings. Information Processing Let- ters, 10(4-5):240–242, 1980

work page 1980

[5] [5]

A. Bouchet. Reducing prime graphs and recognizing circle graphs. Combinatorica, 7(3):243– 254, 1987

work page 1987

[6] [6]

A. Bouchet. Unimodularity and circle graphs. Discrete Mathematics, 66(1-2):203–208, 1987

work page 1987

[7] [7]

Deciding circular-arc graph isomorphism in parameterized logspace

Maurice Chandoo. Deciding circular-arc graph isomorphism in parameterized logspace. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016) . Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016

work page 2016

[8] [8]

Extending Partial Representations of Circle Graphs

S. Chaplick, R. Fulek, and P. Klav´ ık. Extending partial representations of circle graphs. CoRR, abs/1309.2399, 2015. 11

work page Pith review arXiv 2015