On the Structure of Normalized Models of Circular-Arc Graphs I. Hsu’s Approach

Krawczyk, Tomasz

doi:10.4230/LIPIcs.GD.2025.3

On the Structure of Normalized Models of Circular-Arc Graphs I. Hsu’s Approach

Tomasz Krawczyk

Faculty of Mathematics and Information Science, Warsaw University of Technology, Poland

Abstract

In the work [ $\mathcal{O}(m\cdot n)$ algorithms for the recognition and isomorphism problems on circular-arc graphs, SIAM J. Comput. 24(3), 411–439, (1995)], Wen-Lian Hsu claims three results concerning the class of circular-arc graphs:

$\blacksquare$

the design of so-called decomposition trees that represent the structure of all normalized intersection models of circular-arc graphs,
$\blacksquare$

an $\mathcal{O}(nm)$ -time recognition algorithm for circular-arc graphs,
$\blacksquare$

an $\mathcal{O}(nm)$ -time isomorphism algorithm for circular-arc graphs.

In [Discrete Math. Theor. Comput. Sci., 15(1), 157–182, 2013] Curtis, Lin, McConnell, Nussbaum, Soulignac, Spinrad, and Szwarcfiter showed that Hsu’s isomorphism algorithm is incorrect. In this note, we show that the other two results – namely, the construction of decomposition trees and the recognition algorithm – are also flawed.

We also present the main ideas that made it possible to construct a data structure that maintains normalized models of circular-arc graphs.

Keywords and phrases:

intersection graphs and models, circular-arc graphs and circular-arc intersection models

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Data structures design and analysis ; Theory of computation

\rightarrow

Graph algorithms analysis

Funding:

Partially supported by grant no. 2024/53/B/ST6/02558 from National Science Centre, Poland.

DOI:

10.4230/LIPIcs.GD.2025.3

Event:

33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)

Editors:

Vida Dujmović and Fabrizio Montecchiani

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

One of the most important and widely studied models of geometric graph representation is the intersection model, in which vertices are represented by geometric sets and edges correspond to pairs of intersecting sets. Formally, the intersection model or the representation of a graph $G$ within a family of geometrical objects $\mathcal{R}$ is a mapping $\phi:V(G)\to\mathcal{R}$ that maps the vertices of $G$ into objects in $\mathcal{R}$ such that for every two distinct vertices $u$ and $v$ in $G$ we have $uv\in E(G)$ if and only if $\phi(u)\cap\phi(v)\neq\emptyset$ . Graphs which admit such a representation are called intersection graphs of objects from $\mathcal{R}$ or $\mathcal{R}$ -intersection graphs. By considering families containing some specific kinds of objects we obtain different intersection graph classes, such as:

$\blacksquare$

interval graphs, which are intersection graphs of intervals on a line,
$\blacksquare$

permutation graphs, which are intersection graphs of segments spanned between two disjoint parallel lines,
$\blacksquare$

circular-arc graphs, which are intersection graphs of arcs of a circle,
$\blacksquare$

circle graphs, which are intersection graphs of chords of a circle.

Clearly, every interval graph is a circular-arc graph. Since permutation graphs can be equivalently defined as the intersection graphs of chords spanned between two disjoint arcs of a circle, every permutation graph is a circle graph. A graph $G$ is a comparability graph if its edges can be oriented ${\prec}$ such that $(V(G),{\prec})$ is a transitive and irreflexive relation on $V(G)$ . A co-comparability graph is the complement of a comparability graph. Notably, every interval graph (permutation graph, respectively) $G$ is a co-comparability graph. Indeed, given an intersection model of an interval (permutation, respectively) graph $G$ , the pairs of non-intersecting intervals (segments, respectively) can be ordered naturally from left to right. This ordering induces a transitive orientation of the edges in the complement $\overline{G}$ of $G$ .

For a given intersection graph class, a fundamental combinatorial problem is to characterize all intersection models of a graph in that class and to design a data structure that efficiently represents all such models. Such data structures play a central role in algorithmic applications, where the task is to construct, for a given abstract graph specified by its vertices and edges, an intersection model satisfying prescribed criteria (see, e.g., partial representation extension problems). When these data structures also possess a tree-like structure, they can be leveraged to design graph isomorphism algorithms: testing whether two graphs are isomorphic then reduces to checking isomorphism between the tree-like data structures representing their intersection models. For each graph class introduced above – except for circular-arc graphs – such a data structure is known: we have PQ-trees for interval graphs, modular decomposition trees for permutation graphs, and split decomposition trees for circle graphs.

In the work [ $\mathcal{O}(m\cdot n)$ algorithms for the recognition and isomorphism problems on circular-arc graphs, SIAM J. Comput. 24(3), 411–439, (1995)] [5], Wen-Lian Hsu claims three results concerning the class of circular-arc graphs. The first claims a construction of a decomposition tree, a data structure intended to represent the set of all normalized intersection models of a circular-arc graph (an analogue of the PQ-tree for an interval graph). Normalized intersection models (formally defined in Section 2) 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. Based on these decomposition trees, Hsu claims $\mathcal{O}(nm)$ -time algorithms for both the recognition and isomorphism problem for circular-arc graphs.

In this work, we show that the description of the normalized intersection models given by Hsu in [5] is not correct. Specifically, we show the following:

Counterexample 1.

There are circular-arc graphs whose all normalized models do not follow the description given by Hsu.

As a consequence, the decomposition trees proposed by Hsu, along with his polynomial-time algorithms for recognizing and testing isomorphism of circular-arc graphs, are also incorrect. We note that Curtis, Lin, McConnell, Nussbaum, Soulignac, Spinrad, and Szwarcfiter [1] had already identified a different flaw in Hsu’s isomorphism algorithm in 2013. Hsu’s approach – based on the modular decomposition by Gallai (see Section 3) – determines the main steps required to describe the structure of normalized models of circular-arc graphs. In this paper, we identify several errors in Hsu’s work, showing that some key steps of his work were incorrectly carried out.

Although Hsu’s work [5] contains flaws, the overall approach it takes is appropriate. In [6], we modify several crucial definitions within Hsu’s framework, which allows us to develop a data structure that represents all normalized models of circular-arc graphs. We want to mention that, despite the errors in Hsu’s original work, his ideas had a strong influence on the work done in [6]. We refer the reader to [6] for more details.

Our paper is organized as follows:

$\blacksquare$

in Section 2 we introduce notation and basic tools used throughout the paper,
$\blacksquare$

in Section 3 we describe the prior research that influenced Hsu’s work on the problem of characterizing normalized models of circular-arc graphs,
$\blacksquare$

in Section 4 we sketch the approach used by Hsu, we show the main errors in his work, and we prove Counterexample 1,
$\blacksquare$

in Section 5 we describe the main ideas used in [6] that allow, based on the same approach, to devise a data structure representing all normalized models of a circular-arc graph.

2 Preliminaries

All graphs discussed in this paper are finite and simple. The vertex set and edge set of a graph $G$ are denoted by, respectively, $V(G)$ and $E(G)$ . The neighborhood of a vertex $v$ , denoted by $N_{G}(v)$ , comprises vertices adjacent to $v$ , i.e., $N_{G}(v)=\{u\in V(G):uv\in E(G)\}$ , and the closed neighborhood of $v$ is $N_{G}[v]=N_{G}(v)\cup\{v\}$ . A vertex $u\in V(G)$ is universal in $G$ if $N_{G}[u]=V(G)$ . Vertices $u,v\in V(G)$ are twins in $G$ if $N_{G}[u]=N_{G}[v]$ . For a subset $U\subseteq V(G)$ , we denote by $G[U]$ the graph induced by the set $U$ .

Let $(V(G),{\prec})$ be a transitive orientation of a comparability graph $G$ . For subsets $M_{1},M_{2}\subseteq V(G)$ we write $M_{1}\prec M_{2}$ if we have $u\prec v$ for every $u\in M_{1}$ and $v\in M_{2}$ .

2.1 Modular decomposition tree

The definitions that follow are due to Gallai [4].

Let $G$ be a graph and let $\overline{G}$ be the complement of $G$ . A non-empty set $M\subseteq V(G)$ is a module of $G$ if every vertex outside $M$ is adjacent to all or to none of the vertices in $M$ . The singleton sets and the whole set $V(G)$ are the trivial modules of $G$ . A module $M$ of $G$ is strong if $M\subseteq N$ , $N\subseteq M$ , or $M\cap N=\emptyset$ for every other module $N$ in $G$ . In particular, two strong modules of $G$ are either nested or disjoint. The modular decomposition tree of $G$ , denoted by ${\mathcal{M}}(G)$ , consists of all strong modules of $G$ . The set ${\mathcal{M}}(G)$ , ordered by inclusion, forms a tree in which $V(G)$ is the root, the maximal proper strong submodules of a strong module $M$ are the children of $M$ (they form a partition of $M$ ), and the singleton modules $\{v\}$ for $v\in V(G)$ are the leaves. A strong module $M$ in $G$ is parallel if $G[M]$ is disconnected, serial if $\overline{G[M]}$ is disconnected, and prime if both $G[M]$ and $\overline{G[M]}$ are connected. If $G[M]$ (respectively, $\overline{G[M]}$ ) is disconnected, then the children of $M$ in the modular decomposition tree of $G$ are the connected components of $G[M]$ ( $\overline{G[M]}$ , respectively).

Now assume that $G$ is a comparability graph. The relation between the transitive orientations of the graph $G$ and the modular decomposition tree of $G$ was described by Gallai [4].

Theorem 2 ([4]).

If modules $M_{1},M_{2}$ in ${\mathcal{M}}(G)$ are such that $uv\in E(G)$ for any $u\in M_{1}$ and $v\in M_{2}$ , then every transitive orientation $(V(G),{\prec})$ of $G$ satisfies either $M_{1}\prec M_{2}$ or $M_{2}\prec M_{1}$ .

For a strong module $M$ in $G$ let $G_{M}$ denote the graph on $M$ whose edge set $E(G_{M})$ contains all the edges from $G$ that join the vertices from two different children of $M$ . If $x y$ is an edge in $G$ , then $xy\in E(G_{M})$ for exactly one strong module $M\in{\mathcal{M}}(G)$ . Hence, the set $\{E(G_{M}):M\in{\mathcal{M}}(G)\}$ forms a partition of the edge set $E(G)$ of the graph $G$ .

Theorem 3 ([4]).

There is a one-to-one correspondence between the set of transitive orientations $(V(G),{\prec})$ of $G$ and the families

\big\{(M,{\prec_{M}}):M\in{\mathcal{M}}(G)\text{ and }{\prec_{M}}\text{ is a % transitive orientation of $G_{M}$}\big\}

given by $x\prec y\iff x\prec_{M}y$ , where $M$ is the module in ${\mathcal{M}}(G)$ such that $xy\in E(G_{M})$ .

The above theorem asserts that every transitive orientation of $G$ restricted to the edges of the graph $G_{M}$ induces a transitive orientation of $G_{M}$ , for every $M\in{\mathcal{M}}(G)$ , and that every transitive orientation of $G$ can be obtained by independent transitive orientations of the graphs $G_{M}$ , for $M\in{\mathcal{M}}(G)$ . Gallai [4] characterized all possible transitive orientations of the graph $G_{M}$ , where $M$ is a module of ${\mathcal{M}}(G)$ .

Theorem 4 ([4]).

Let $M$ be a prime module in ${\mathcal{M}}(G)$ . Then, $G_{M}$ has two transitive orientations, one being the reverse of the other.

If $M$ is parallel, then $E(G_{M})=\emptyset$ , and the graph $G_{M}$ has exactly one (empty) transitive orientation. If $M$ is serial, the transitive orientations of $G_{M}$ correspond to the total orderings of its children, that is, every transitive orientation of $G_{M}$ is of the form $M_{i_{1}}\prec_{M}\ldots\prec_{M}M_{i_{k}}$ , where $i_{1}\ldots i_{k}$ is a permutation of $[k]$ and $M_{1},\ldots,M_{k}$ are the children of $M$ in ${\mathcal{M}}(G)$ .

A graph $G$ is prime if every module of $G$ is trivial. By Theorem 4, every prime comparability graph admits a unique (up to reversal) transitive orientation.

2.2 Join decomposition

Since our counterexamples involve graphs that admit “join decompositions”, we reproduce the following definitions exactly as stated in Hsu’s paper [5] (see page 417, lines –7 to –1).

A graph $G$ is said to have a join if $V(G)$ can be partitioned into sets $V_{0}$ , $V_{1}$ , $V_{2}$ , and $V_{3}$ with $|V_{0}\cup V_{1}|\geqslant 2$ and $|V_{2}\cup V_{3}|\geqslant 2$ so that every possible edge exists between $V_{1}$ and $V_{2}$ , no edge exists between $V_{0}$ and $V_{2}\cup V_{3}$ , and no edge exists between $V_{3}$ and $V_{0}\cup V_{1}$ . In this case, we say that the graph $G$ is decomposable into graphs $H_{1}$ and $H_{2}$ where $H_{1}$ is the induced subgraph of $G[V_{0}\cup V_{1}]$ with an extra vertex $v$ adjacent to every vertex in $V_{1}$ and $H_{2}$ is the induced subgraph of $G[V_{2}\cup V_{3}]$ with an extra vertex $u$ adjacent to every vertex in $V_{2}$ . If the above holds, then $(V_{0},V_{1},V_{2},V_{3})$ is a join in $G$ and $H_{1}$ and $H_{2}$ is a decomposition of $G$ induced by the join $(V_{0},V_{1},V_{2},V_{3})$ . See Figures 6(c)-(d) for an illustration. A graph $G$ is said to be j-inseparable if it does not contain a join.

2.3 Normalized models of circular-arc graphs

Let $G$ be a circular-arc graph and let $\psi$ be a circular-arc model of $G$ such that all the arcs in the set $\{\psi(v):v\in V(G)\}$ have distinct endpoints. We refer to Figure 1 which shows possible relations between two arcs in $\{\psi(v):v\in V(G)\}$ .

Figure 1: From left to right:

\psi(v)

and

\psi(u)

are disjoint,

\psi(v)

contains

\psi(u)

,

\psi(v)

is contained in

\psi(u)

,

\psi(v)

and

\psi(u)

cover the circle, and

\psi(v)

and

\psi(u)

overlap.

In so-called normalized models, defined in [5], the relative relation between the arcs reflects the closed neighbourhood relation between the vertices of $G$ , as follows.

Definition 5.

Let $G$ be a circular-arc graph. A circular-arc model $\psi$ of $G$ is normalized with respect to $G$ (shortly, normalized) if all the arcs from $\{\psi(v):v\in V(G)\}$ have distinct endpoints and for every pair $(v,u)$ of distinct vertices in $G$ the following conditions are satisfied:

1.

if $uv\notin E(G)$ , then $\psi(v)$ and $\psi(u)$ are disjoint,
2.

if $N_{G}[u]\subsetneq N_{G}[v]$ , then $\psi(v)$ contains $\psi(u)$ ,
3.

if $N_{G}[v]\subsetneq N_{G}[u]$ , then $\psi(v)$ is contained in $\psi(u)$ ,
4.

if $N_{G}[v]\cup N_{G}[u]=V$ , $N_{G}[w]\subsetneq N_{G}[v]$ for every $w\in N_{G}[v]\smallsetminus N_{G}[u]$ , and $N_{G}[w]\subsetneq N_{G}[u]$ for every $w\in N_{G}[u]\smallsetminus N_{G}[v]$ , then $\psi(v)$ and $\psi(u)$ cover the circle,
5.

If none of the above condition holds, then $\psi(v)$ and $\psi(u)$ overlap.

Furthermore, for a pair $(v,u)$ of distinct vertices from $G$ , we say that $v$ and $u$ are disjoint in $G$ , $v$ contains $u$ in $G$ , $v$ is contained in $u$ in $G$ , $v$ and $u$ cover the circle in $G$ , and $v$ and $u$ overlap in $G$ if the pair $(v,u)$ satisfies the assumption of statement 1., 2., 3., 4., and 5., respectively.

Note that the relation between vertices $u$ and $v$ is symmetric, with one exception: $u$ is contained in $v$ if and only if $v$ contains $u$ . It is known that if $G$ has no universal vertices and no twins, every circular-arc model of $G$ can be transformed into a normalized model by possibly extending some of its arcs [5].

3 Modular decomposition tree as a data structure representing intersection models of some geometric intersection graphs

One of the most powerful tools for designing data structures that maintain intersection models of geometric graph classes is the modular decomposition tree, introduced by Gallai [4] to characterize the structure of all transitive orientations of a comparability graph $G$ – see Subsection 2.1 for details. In short, the structure of all transitive orientations of a comparability graph $G$ satisfies the following properties:

(G1): If $U\subseteq V(G)$ is such that $G[U]$ is a prime subgraph of $G$ , then $G[U]$ admits a unique transitive orientation (up to reversal).
(G2): The structure of all transitive orientations of $G$ can be described (and represented) by means of the modular decomposition tree of $G$ .

It turns out that the modular decomposition tree can be used to represent intersection models for various classes of geometric intersection graphs, in particular, permutation graphs and interval graphs.

Dushnik and Miller [2] proved that a graph $G$ is a permutation graph if and only if $G$ and its complement $\overline{G}$ admit transitive orientations. Furthermore, they showed that, if $G$ is a permutation graph, then the intersection models of $G$ correspond to the pairs of transitive orientations of $G$ and $\overline{G}$ . Formally, given an intersection model $\phi$ of $G$ we can derive transitive orientations ${\prec}$ of $G$ and ${<}$ of $\overline{G}$ , as follows (see Figure 2):

\begin{array}[]{lll}x\prec y&\iff&\phi(x)\text{ and }\phi(y)\text{ intersect % and $\phi(x)$ precedes $\phi(y)$ in the upper line.}\\ x<y&\iff&\phi(x)\text{ is to the left of }\phi(y)\text{ in }\phi.\\ \end{array}

(1)

On the other hand, given transitive orientations ${\prec}$ and ${<}$ of $G$ and $\overline{G}$ , respectively, one can construct a permutation model $\phi$ of $G$ such that

\begin{array}[]{lll}\phi(x)\text{ precedes }\phi(y)\text{ in the upper line}&% \iff&x\prec y\text{ or }x<y,\\ \phi(x)\text{ precedes }\phi(y)\text{ in the lower line}&\iff&y\prec x\text{ % or }x<y.\\ \end{array}

(2)

Figure 2: Intersection model

\phi

of the permutation graph

G=(\{a,b,c\},\{ab,ac\})

corresponding to the transitive orientations

\{a\prec b,a\prec c\}

and

\{b<c\}

of

G

and

\overline{G}

, respectively.

As for interval graphs, a reader familiar with PQ-trees may observe that the PQ-tree of an interval graph $G$ can be easily derived from the modular decomposition tree of $G$ . In particular, Properties (G1) and (G2) have the following impact on the structure of the intersection models of a permutation/interval graph $G$ :

(M1): If $U\subseteq V(G)$ is such that $G[U]$ is prime, then $G[U]$ admits a unique intersection model (up to certain normalizations and reflections).
(M2): The structure of the intersection models of $G$ is represented by the modular decomposition tree of $G$ .

Moreover, Theorem 2 asserts the following property of intersection models of permutation graphs:

(M3): In any segment intersection model of a permutation graph $G$ , for every strong module $M$ in $G$ , the lower (respectively, upper) endpoints of the segments representing vertices in $M$ lie within a contiguous interval on the lower (respectively, upper) line, containing no endpoints of segments corresponding to vertices outside $M$ .

Regarding circular-arc graphs, Spinrad’s work [7] was the first to describe the structure of normalized models for a specific subclass using the approach outlined above. Specifically, Spinrad focused on co-bipartite graphs, that is, graphs whose vertex set can be partitioned into two cliques.

Let us briefly outline the ideas of Spinrad. Let $G$ be a co-bipartite circular-arc graph whose vertex set can be partitioned into two cliques, $C_{A}$ and $C_{B}$ . We assume that $G$ has no universal vertices and no twins. Let $G_{c}$ denote the graph on the vertex set $V(G)$ in which two vertices are joined by an edge if and only if they overlap according to Definition 2.3. In particular, in any normalized model of $G$ , the arcs for $u$ and $v$ overlap exactly when $u v$ is an edge of $G_{c}$ . Let $\overline{G_{c}}$ be the complement of $G_{c}$ . First, Spinrad proves that each model of $G$ can be turned into a normalized model $\psi$ such that all the arcs from $\{\psi(x):x\in C_{A}\}$ contain the leftmost point $A$ of the circle, and all the arcs from $\{\psi(x):x\in C_{B}\}$ contain the rightmost point $B$ of the circle. Let us call such models of $G$ strongly normalized – see Figure 3 for an illustration. Note that no arc from $\{\psi(v):v\in V(G)\}$ contains both the points $A$ and $B$ as $G$ has no universal vertices. Hence, each arc from $\{\psi(v):v\in V(G)\}$ has one endpoint in the upper semicircle and one endpoint in the lower semicircle. Next, Spinrad introduces an orientation ${<}$ on the edges of $\overline{G_{c}}$ , as shown in Figure 3. Spinrad proves that ${<}$ is a transitive orientation of $\overline{G_{c}}$ and that ${<}$ can be represented by segments spanned between the upper and lower semicircle in such a way that the segment for $u$ is to the left of the segment for $v$ if and only if $u<v$ (note that that segments for $u$ and $v$ intersect if and only if vertices $u$ and $v$ overlap in $G$ ).

Figure 3: Spinrad sets

u<v

if and only if either

u,v\in C_{A}

and

u

is contained in

v

(left) or

u,v\in C_{B}

and

u

contains

v

(middle left) or

u\in C_{A}

,

v\in C_{B}

, and

u, v

are disjoint (middle right), or

u\in C_{B}

,

v\in C_{A}

, and

u, v

cover the circle (right).

The above observations were used by Spinrad to devise a polynomial-time recognition algorithm for co-bipartite circular arc graphs [7]. Given a co-bipartite graph $G$ as input, the algorithm constructs the overlap graph $G_{c}$ of $G$ and the orientation ${<}$ of the edges of $\overline{G_{c}}$ . The graph $G$ is accepted as a circular-arc graph if $G_{c}$ is a permutation graph and ${<}$ is a transitive orientation of $\overline{G_{c}}$ . Note that this approach allows us to conclude that the strongly normalized models of $G$ correspond to the transitive orientations of the graph $G_{c}$ . Indeed, $G_{c}$ is a permutation graph and hence its models correspond to the pairs of transitive orientations of $G_{c}$ and $\overline{G_{c}}$ . However, to obtain a model consistent with the relations between the vertices in $G$ , non-intersecting segments need to be placed consistently with the ${<}$ relation. Summing up, Properties (M1)–(M3) assert that:

(S1): If $U\subseteq V(G)$ is such that $G_{c}[U]$ is prime, then $G[U]$ admits a unique strongly normalized model.
(S2): The set of all strongly normalized models of $G$ is represented by the modular decomposition tree of the overlap graph $G_{c}$ of $G$ .
(S3): For every strong module $M$ of $G_{c}$ and every strongly normalized model of $G$ , the lower (upper) endpoints of the arcs for the vertices in $M$ lie within a contiguous arc on the lower (upper, respectively) semicircle, containing no endpoints of the arcs for the vertices from outside $M$ .

4 Hsu’s approach to the problem of characterizing normalized models of circular-arc graphs

To describe the structure of normalized models of circular-arc graphs, Hsu attempts to generalize Spinrad’s ideas to the entire class of circular-arc graphs [5]. For this purpose, Hsu introduces the overlap graph $G_{c}$ of $G$ :

Definition [page 420, lines 11 to 12].

Associate with each graph $G$ the graph $G_{c}$ that has the same vertex set as $G$ such that two vertices in $G_{c}$ are adjacent iff they are strictly but not strongly adjacent in $G$ .

In [5], two vertices $u$ and $v$ are said to be strictly but not strongly adjacent in $G$ if and only if they overlap in $G$ according to Definition 2.3. Then, Hsu transforms every normalized model $R$ of $G$ to a chord model $D$ by converting each arc $R(v)$ into a chord $D(v)$ with the same endpoints as $R(v)$ , for every $v\in V(G)$ . Hsu observes that $D$ is a chord model of the graph $G_{c}$ , regardless of the choice of a normalized model $R$ of $G$ . Next, Hsu lists some properties of the chord models $D$ of $G_{c}$ derived from the normalized models $R$ of $G$ . To state them, for every vertex $v\in V(G)$ let $I_{v}$ be the set of vertices not adjacent to $v$ in $G_{c}$ , and let

\begin{array}[]{rcl}L_{v}&=&\{u\in I_{v}:\quad\text{$u$ is contained in $v$ in% $G$}\quad\text{or}\quad\text{$v$ and $u$ cover the circle in $G$}\},\\ R_{v}&=&\{u\in I_{v}:\quad\text{$u$ and $v$ are not adjacent in $G$}\quad\text% {or}\quad\text{$u$ contains $v$ in $G$}\}.\end{array}

Hsu observes that for every $v\in V(G)$ the chords representing the vertices from the set $L_{v}$ are on one side of $D(v)$ and the chords representing the vertices from the set $R_{v}$ are on the other side of $D(v)$ . See Figure 4 for an illustration. Based on this observation, Hsu assumes the following definition:

Figure 4: Relations between the arcs

R(v)

and

R(u)

and the corresponding chords

D(v)

and

D(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.

Definition [page 424, lines 18 to 20].

A chord model $D$ of $G_{c}$ is conformal (to $G$ ) if for every vertex $v$ of $G$ the chords associated with vertices in $L_{v}$ are on one side of the chord of $D(v)$ and those associated with vertices in $R_{v}$ are on the other side of the chord of $D(v)$ .

Then, Hsu proves the correspondence between normalized models of $G$ and the conformal models of $G_{c}$ :

Theorem 5.6 [page 424, lines -18 to -17].

Let $G$ be a circular-arc graph […]. Then a model for $G_{c}$ is conformal if and only if it is a chord model corresponding to some normalized model for $G$ .

Eventually, Hsu tries to describe the structure of the chord models of $G_{c}$ that are conformal to $G$ . To this end, Hsu attempts to prove the properties similar to (S1) and (S2):

(H1): If $U\subseteq V(G)$ is such that $G_{c}[U]$ is prime, then $G_{c}$ has a unique conformal model (up to reflection).
(H2): The structure of the conformal models of $G_{c}$ can be described by the modular decomposition tree of $G_{c}$ .

To accomplish Property (H2), Hsu introduces so-called consistent modules in the graph $G_{c}$ (see Subsection 4.1.1 for more details) that were intended to satisfy the following properties:

(H3): For every conformal model $D$ and every consistent module $M$ of $G_{c}$ there are two disjoint arcs $A_{M}$ and $B_{M}$ of the circle such that each arc $A_{M}$ and $B_{M}$ contains one endpoint of every chord for the vertices of $M$ and no endpoint of any chord for the vertices from outside $M$ (in particular, it means that $G_{c}[M]$ is a permutation graph). Furthermore, the maximal consistent modules in $G_{c}$ form a partition of the set $V(G_{c})$ , and a possible placement of the arcs $A_{M}$ and $B_{M}$ for the maximal consistent modules $M$ in the conformal models of $G_{c}$ can be represented by the modular decomposition tree of $G_{c}$ .

Note that when $G$ is co-bipartite, Property (S3) asserts that every strong module of $G_{c}$ is a consistent module of $G_{c}$ . Moreover, the relative ordering of the endpoints of the maximal non-trivial consistent modules in the conformal models of $G_{c}$ is represented by the modular decomposition tree of $G_{c}$ .

First, we emphasize that Property (H1) is fundamental to the method, since the structure of conformal models is built upon the unique conformal models of the prime induced subgraphs of $G_{c}$ . In this context, Property (H1) plays a role analogous to the uniqueness of transitive orientations of prime subgraphs in the characterization of all transitive orientations of a comparability graph. In Subsection 4.1 we show that Hsu’s attempted proof of Property (H1) (Theorem 5.7 in [5]) is not correct – it relies on two claims, both of which are disproved in Section 4.1. However, the statement of Property (H1) holds true, which follows from the proof of an analogous property shown in [6] (proved for the oriented conformal models – see Section 5 for more details).

To establish Property (H2), Hsu divides the description of the structure of the conformal models of $G_{c}$ into three cases depending on whether $V(G_{c})$ is serial/prime/parallel in the modular decomposition tree of $G_{c}$ . Hsu’s work [5] correctly deals with the serial case (then, each component of $\overline{G_{c}}$ induces a co-bipartite circular-arc graph and we can use the results of Spinrad [7] to describe the normalized models of $G$ ), but is incorrect in the prime case, and is incomplete (and also incorrect) in the parallel case.

For the prime case, Hsu first attempts to prove Property (H1). Next, Hsu tries to partition the set $V(G_{c})$ into “maximal consistent modules” and tries to prove that there is a unique circular order (up to reflection) in which the arcs $A_{M}$ and $B_{M}$ for maximal consistent modules $M$ occur around the circle in the conformal models of $G_{c}$ . In Subsection 4.1.1 we show that the “maximal consistent modules” determined by Hsu do not satisfy Property (H3). This enables us, in particular, to construct a circular-arc graph claimed by Counterexample 1. Hence, the theorems from [5] that establish Property (H3) for the “maximal consistent modules” determined by Hsu are also not correct – see Subsection 4.1.1 for more details.

Finally, the description of Hsu is also not correct in the parallel case. First, the errors mentioned in the prime case (partition into consistent modules) are transferred to the description of the conformal models of prime components of $G_{c}$ (partition of the prime children of $V(G_{c})$ into maximal consistent modules is not correct). Moreover, this part of Hsu’s work seems to miss some important elements. For example, nowhere in his work we could find the description of maximal consistent modules for serial children of $V(G_{c})$ – we refer to Section 4.2 for more details.

4.1 Prime graphs

When $V(G_{c})$ forms a prime module in $G_{c}$ , Hsu first considers the case where $G_{c}$ is s-inseparable, which is equivalent to $G_{c}$ being prime (see p. 416, lines 24–30). For this case, Hsu first attempts to prove the following:

Theorem 5.7 [page 425, lines 16 to 17].

Let $G$ be a circular-arc graph. If $G_{c}$ is s-inseparable, then $G$ has a unique normalized model.

The Hsu’s proof of Theorem 5.7 is split into two cases depending on whether $G_{c}$ is j-inseparable (see Subsection 2.2). If $G_{c}$ is j-inseparable, then $G_{c}$ has a unique chord model, as proved by Gabor, Supowit, and Hsu [3], and hence $G$ has a unique normalized model.

So, the interesting case is when $G_{c}$ is not j-inseparable, that is, when $G_{c}$ has a join $(V_{0},V_{1},V_{2},V_{3})$ . First, Hsu observes that $V_{i}\neq\emptyset$ for all $i=0,\ldots,3$ as $G_{c}$ is s-inseparable. The remainder of the proof relies on two key claims, both of which we show to be false.

First, the proof of Theorem 5.7 tries to show the following property of the graph $G_{c}$ and the join $(V_{0},V_{1},V_{2},V_{3})$ of $G_{c}$ :

Claim A [page 425, line -23 to -18].

If $|V_{1}|>0$ and there exists a vertex $s$ in $V_{1}$ that is adjacent to all other vertices in $V_{1}\cup V_{2}$ , then it is easy to verify that $G_{c}\smallsetminus\{s\}$ is $s$ -inseparable. We can proceed with the construction below to show that $G_{c}\smallsetminus\{s\}$ has a unique conformal model, and, furthermore, there is a unique way to insert the chord of $s$ into this model. The argument is symmetric if such a vertex $s$ belongs to $V_{2}$ .

We show that Claim A is false. To show a counterexample, we first define an auxiliary circular-arc graph $G^{s}$ : the vertex set of $G^{s}$ is $\{s,s_{1},\ldots,s_{6}\}$ , the edges of $G^{s}$ can be read from the intersection model $R^{s}$ of $G^{s}$ shown in Figure 5(a). We leave the reader to verify that the model $R^{s}$ is normalized (the vertices $s_{1},\ldots,s_{6}$ induce a cycle in $G^{s}$ and hence every two consecutive vertices on this cycle overlap in $G^{s}$ ). The associated circle graph $G^{s}_{c}$ and the schematic view of the model $R^{s}$ are illustrated in Figures 5(b)-(c).

(a) Normalized model

R^{s}

of

G^{s}

.

(b) Ass. chord model of

G^{s}_{c}

.

(c) Schematic view of

R^{s}

.

(d) Schematic view of the model

R

of

G

.

(e) Graph

G_{c}

and its join decomposition.

Figure 5: Counterexample to Claim A.

Next, we define a circular-arc graph $G$ by taking $G^{s}$ and two isomorphic copies of $G^{s}$ , say $G^{v}$ and $G^{u}$ , over the vertex sets $\{v,v_{1},\ldots,v_{6}\}$ and $\{u,u_{1},\ldots,u_{6}\}$ , respectively. Again, we define the edges of $G$ by providing an intersection model $R$ of $G$ . Given the schematic view of the model $R$ , as shown in Figure 5(d), we construct the intersection model $R$ for $G$ as follows. We begin with the circular-arc model $R^{s}$ of $G^{s}$ and embed its arcs into the circle so that:

$\blacksquare$

The arc $R^{s}(s)$ shares its endpoints with the oriented chord $s^{0}s^{1}$ and lies to the left of this chord when traversed from $s^{0}$ to $s^{1}$ .
$\blacksquare$

The endpoints of the remaining arcs in $R^{s}$ are compressed so that they all fit within the colored arc adjacent to the head of the chord $s^{0}s^{1}$ (that is, the arc endpoints for $s_{1},\ldots,s_{6}$ , as well as the upper endpoint of $s$ , are placed on the colored (blue–red–green) upper arc in the order shown in Figures 5(a) and 5(b)).

We paste in the same way the models $R^{v}$ and $R^{u}$ , which represent $G^{v}$ and $G^{u}$ , along the chords $v^{0}v^{1}$ and $u^{0}u^{1}$ , respectively.

Once again, we leave it to the reader to verify that $R$ is a normalized model of $G$ . The associated circle graph $G_{c}$ , along with its join decomposition $(V_{0},V_{1},V_{2},V_{3})$ , is shown in Figure 5(e). Note that:

$\blacksquare$

$G_{c}$ is prime as $G_{c}$ has no non-trivial modules,
$\blacksquare$

vertex $s$ in $V_{1}$ is adjacent to all other vertices in $V_{1}\cup V_{2}$ .

That is, $G_{c}$ , $(V_{0},V_{1},V_{2},V_{3})$ , and $s$ satisfy the assumptions of Claim A. The graph $G_{c}\smallsetminus\{s\}$ , however, is not prime as $G_{c}\smallsetminus\{s\}$ is disconnected. So, Claim A is false.

Then, the proof assumes that $G_{c}$ has a join $(V_{0},V_{1},V_{2},V_{3})$ such that no vertex from $V_{1}\cup V_{2}$ is adjacent to all other vertices in $V_{1}\cup V_{2}$ . Let $H_{1}$ and $H_{2}$ be the decomposition of $G_{c}$ induced by $(V_{0},V_{1},V_{2},V_{3})$ . In this setting, the following property of $H_{1}$ and $H_{2}$ is claimed.

Claim B [page 425, line -19 to -16].

Therefore, assume no such vertex $s$ exists. Then it is easy to verify that the corresponding two component graphs, $H_{1}$ and $H_{2}$ of $G_{c}$ (the existence of the substitution in either $H_{1}$ or $H_{2}$ would imply the existence of one in $G_{c}$ ), are $s$ -inseparable.

(a) Normalized circular-arc model

R

of

G

.

(b) Associated chord model

D

of

G_{c}

.

(c) Graph

G_{c}

and its join decomposition.

(d) Decomposition of

G_{c}

into

H_{1}

and

H_{2}

.

Figure 6: Counterexample to Claim B.

Consider a circular-arc graph $G$ whose normalized model $R$ is shown in Figure 6(a). The associated circle graph $G_{c}$ and its join $(V_{0},V_{1},V_{2},V_{3})$ are shown in Figure 6(c), the chord model $D$ associated with $R$ is shown in Figure 6(b), and the decomposition $H_{1}$ and $H_{2}$ of $G_{c}$ induced by the join $(V_{0},V_{1},V_{2},V_{3})$ is shown in Figure 6(d). Note the following properties of $G_{c}$ , $H_{1}$ , and $H_{2}$ :

$\blacksquare$

$G_{c}$ is prime as $G_{c}$ has no non-trivial modules and there is no vertex $s$ in $V_{1}\cup V_{2}$ adjacent to all other vertices in $V_{1}\cup V_{2}$ ,
$\blacksquare$

$H_{1}$ contains a non-trivial module $\{u_{3},v\}$ and $H_{2}$ contains a non-trivial module $\{u,v_{3}\}$ .

In particular, Claim B is also false.

The proof of Theorem 5.4 by Hsu is concluded as follows. Since $H_{1}$ and $H_{2}$ are s-inseparable, they have unique chord models by induction. Eventually, there is a unique way to compose these models to get a conformal model of $G_{c}$ .

4.1.1 Consistent modules

The precise definition of the consistent modules (they are also called as T-submodules of $G_{c}$ is given in Section 6.1 of the Hsu’s work [5]). Since it is very technical, we list only their properties as proven by Hsu.

Lemma 6.5 [page 428, -2 – page 429, line 2].

Let $M$ be a T-submodule that gives rise to a permutation graph. Let $D$ be any conformal model for $G_{c}$ . Then the endpoints of chords of $M$ can be partitioned into two sets $A_{1}$ , $A_{2}$ such that each chord of $M$ has one endpoint in $A_{1}$ and the other in $A_{2}$ and those endpoints in $A_{1}$ (resp., $A_{2}$ ) are consecutive in $D$ .

Theorem 6.6 [page 429, lines -15 to -11].

Consider a neighborhood (that is, prime, according to our terminology) module $V(G_{c})$ . Let $V^{\prime}=\{v_{1},\ldots,v_{r}\}$ be a set of representatives from the maximal consistent submodules $M^{1},\ldots,M^{r}$ in the consistent partition of $V(G_{c})$ . Then there is a unique conformal model for $V^{\prime}$ . Furthermore, this model is independent of the $v_{i}$ selected (we shall refer to the subgraph induced on $V^{\prime}$ as the representative graph for $V(G)$ ).

In fact, the two lemmas above establish Property (H3) for the consistent modules of $G_{c}$ in the prime case. Notably, when $G$ is co-bipartite, $G_{c}$ is a permutation graph, and we can take the children of $V(G_{c})$ in the modular decomposition tree of $G_{c}$ as maximal consistent modules of $G_{c}$ (recall that strong modules in the modular decomposition tree of a permutation graph are consistent in all its segment models). Hence, to determine the consistent modules of $G_{c}$ Hsu focuses his attention on the children of $V(G_{c})$ in the modular decomposition tree of $G_{c}$ . Hsu rightly observes that they might be no longer consistent when $G_{c}$ is not a permutation graph. In fact, assuming that $M_{1},\ldots,M_{k}$ are the children of prime $V(G_{c})$ in the modular decomposition tree of $G_{c}$ , Hsu attempts to prove the following lemma:

Lemma 6.3 [Page 428, lines 11–12].

If a maximal submodule $M_{i}$ of $V(G_{c})$ is not consistent, then it is a serial module.

However, the above lemma is also false, as parallel children of $V(G)$ might also be non-consistent. This enables us to construct the graph claimed by Counterexample 1.

(a) A circular-arc graph

G

.

(b) Normalized model

R

of

G

.

(c) Associated chord model

D

of

G_{c}

.

(d) Graph

G_{c}

and its maximal non-trivial modules

M_{1},M_{2},M_{3},M_{4}

.

Figure 7: Counterexample 1:

V(G_{c})

is a neighbourhood module,

M_{1},M_{2},M_{3},M_{4}

are all parallel children of

V(G_{c})

in the modular decomposition tree of

G_{c}

, and

M_{1}

and

M_{4}

are not consistent.

Counterexample 1.

Consider a circular-arc graph $G$ shown in Figure 7(a). Its normalized model $R$ is shown in Figure 7(b), an associated chord model $D$ in Figure 7(c), and the circle graph $G_{c}$ associated to $G$ and its partition into maximal non-trivial modules $M_{1},\ldots,M_{4}$ in Figure 7(d). Note that $V(G_{c})$ is a prime module in the modular decomposition tree of $G_{c}$ , and each $M_{i}$ is a parallel child of $V(G)$ . Note that the modules $M_{1}$ and $M_{4}$ are not consistent in $D$ . One can also check that the model $R$ and its reflection are the only two normalized models of $G$ . Since both these models do not obey the description given by Hsu (it is claimed in [5] that only series children of $V(G)$ might be not consistent), the graph $G$ proves the statement of Counterexample 1.

The graph $G$ also shows that, assuming Hsu’s partition into “consistent modules”, Lemma 6.5 and Theorem 6.6 from [5] are also false.

4.2 Parallel case

In the case where $V(G_{c})$ is a parallel module, the description given by Hsu is incomplete (and also not correct). In particular, Hsu constructs so-called “consistent module tree” for each component $C$ of $G_{c}$ basing on the consistent modules of the component $C$ . As is written in [5] (see page 435, lines 27 to 29): We shall first construct a consistent decomposition tree $T$ for the subgraph $G_{c}[C]$ and then insert the vertices of $K$ into conformal models of appropriate T-submodules. For any T-submodule $M$ in $C$ , let ….. and then a description of the tree $T$ for the component $C$ follows. Each component $C$ of $G_{c}$ is either a prime or a serial module in $G_{c}$ . In the case when $C$ is a prime component in $G_{c}$ , the maximal consistent modules of $C$ , as we have seen in the previous section, are not determined correctly by Hsu. Nowhere in [5] we found a description of the maximal consistent modules for serial components of $G_{c}$ .

5 Oriented conformal models

The main difference between the approach used in [6] and Hsu’s approach lies in the definition of the conformal models. In [6], a normalized circular-arc model $\psi$ of $G$ is transformed into an oriented chord model $\phi$ by converting every arc $\psi(v)$ for $v\in V(G)$ into an oriented chord $\phi(v)$ such that the chord $\phi(v)$ has the same endpoints as $\psi(v)$ and $\phi(v)$ is oriented so that it has the arc $\psi(v)$ on its left side – see Figure 8 for an illustration. Then, the following definition of conformal models is used.

Figure 8: The transformation of the arc

\psi(v)

into the oriented chord

\phi(v)

.

Definition 6.

An oriented chord model $\phi$ of $G_{ov}$ is conformal to $G$ (shortly, conformal) if for every $v,u\in V$ :

$\blacksquare$

$u\in L_{v}$ if and only if $\phi(u)$ lies on the left side of $\phi(v)$ ,
$\blacksquare$

$u\in R_{v}$ if and only if $\phi(u)$ lies on the right side of $\phi(v)$ .

See Figure 9 for an illustration. Clearly, there is an obvious correspondence between the normalized models of $G$ and the oriented conformal models of $G_{c}$ .

Figure 9: Relations between the arcs

\psi(v)

and

\psi(u)

and the corresponding oriented chords

\phi(v)

and

\phi(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.

The lack of orientation in the chords of conformal models poses notable challenges in Hsu’s work.

Firstly, Hsu divides all the triples $(u,v,w)$ consisting of pairwise non-adjacent vertices in $G_{c}$ into two categories:

$\blacksquare$

$(u,v,w)$ is in parallel, written $u|v|w$ , if the vertex $v$ has the vertices $u$ and $w$ on its different sides (that is, either $u\in L_{v}$ and $w\in R_{v}$ or $w\in L_{v}$ and $u\in R_{v}$ ),
$\blacksquare$

$(u,v,w)$ is in series, written $u-v-w$ , if any vertex from $\{u,v,w\}$ has the remaining two vertices on the same side,

(see Section 5.1 of [5]). Then, Hsu is searching for chord models $\phi$ of $G_{c}$ that satisfy the conditions:

$\blacksquare$

if $u|v|w$ then the chord $\phi(v)$ has $\phi(u)$ and $\phi(w)$ on its different sides,
$\blacksquare$

if $u-v-w$ then every chord from $\{\phi(u),\phi(v),\phi(w)\}$ has the remaining two chords on the same side.

Hsu showed that such chord models correspond to conformal models (see Section 5.2 in [5]). Consequently, Hsu aims to describe the set of transformations between the chord models of $G_{c}$ that preserve the relationships between the triples of non-intersecting chords. By orienting the chords in the conformal models, we can concentrate on pairs of non-intersecting chords. Specifically, we seek transformations that maintain the relative (left/right) relationships between every pair of non-intersecting oriented chords. While this difference may seem minor, it significantly simplifies the task of identifying the set of operations that can transform one conformal model into another.

Secondly, reflecting two intersecting non-oriented chords $a$ and $b$ yields a pair of chords that intersect in exactly the same way. That is, reflection has no observable effect on two intersecting non-oriented chords; to detect a difference, additional chords must be involved. In contrast, when $a$ and $b$ are oriented chords corresponding to two overlapping arcs, reflection produces a different outcome. Indeed, if the head of $b$ lies to the right of $a$ before reflection, then after reflection, it lies to the left of $a$ . See Figure 10 for an illustration. Understanding the role of reflection – specifically, which components of the conformal models can be reflected independently of others – is crucial for identifying all conformal models of $G_{c}$ . In the case of oriented chords, the effects of the reflection can be at least easily described.

Figure 10: The result of the reflection of the arcs

a=a^{0}a^{1}

and

b=b^{0}b^{1}

.

References

[1] Andrew R. Curtis, Min Chih Lin, Ross M. McConnell, Yahav Nussbaum, Francisco J. Soulignac, Jeremy P. Spinrad, and Jayme Luiz Szwarcfiter. Isomorphism of graph classes related to the circular-ones property. Discret. Math. Theor. Comput. Sci., 15(1):157–182, 2013. doi:10.46298/DMTCS.625.
[2] Ben Dushnik and E. W. Miller. Partially ordered sets. Amer. J. Math., 63:600–610, 1941. doi:10.2307/2371374.
[3] Csaba P. Gabor, Kenneth J. Supowit, and Wen-Lian Hsu. Recognizing circle graphs in polynomial time. J. ACM, 36(3):435–473, 1989. doi:10.1145/65950.65951.
[4] Tibor Gallai. Transitiv orientierbare Graphen. Acta Math. Acad. Sci. Hung., 18(1–2):25–66, 1967.
[5] Wen-Lian Hsu. O(M*N) algorithms for the recognition and isomorphism problems on circular-arc graphs. SIAM J. Comput., 24(3):411–439, 1995. doi:10.1137/S0097539793260726.
[6] Tomasz Krawczyk. On the structure of normalized models of circular-arc graphs - Hsu’s approach revisited. CoRR, abs/2411.13374, 2024. doi:10.48550/arXiv.2411.13374.
[7] Jeremy P. Spinrad. Circular-arc graphs with clique cover number two. J. Comb. Theory B, 44(3):300–306, 1988. doi:10.1016/0095-8956(88)90038-X.

[bib.bib1] [1] Andrew R. Curtis, Min Chih Lin, Ross M. McConnell, Yahav Nussbaum, Francisco J. Soulignac, Jeremy P. Spinrad, and Jayme Luiz Szwarcfiter. Isomorphism of graph classes related to the circular-ones property. Discret. Math. Theor. Comput. Sci., 15(1):157–182, 2013. doi:10.46298/DMTCS.625.

[bib.bib2] [2] Ben Dushnik and E. W. Miller. Partially ordered sets. Amer. J. Math., 63:600–610, 1941. doi:10.2307/2371374.

[bib.bib3] [3] Csaba P. Gabor, Kenneth J. Supowit, and Wen-Lian Hsu. Recognizing circle graphs in polynomial time. J. ACM, 36(3):435–473, 1989. doi:10.1145/65950.65951.

[bib.bib4] [4] Tibor Gallai. Transitiv orientierbare Graphen. Acta Math. Acad. Sci. Hung., 18(1–2):25–66, 1967.

[bib.bib5] [5] Wen-Lian Hsu. O(M*N) algorithms for the recognition and isomorphism problems on circular-arc graphs. SIAM J. Comput., 24(3):411–439, 1995. doi:10.1137/S0097539793260726.

[bib.bib6] [6] Tomasz Krawczyk. On the structure of normalized models of circular-arc graphs - Hsu’s approach revisited. CoRR, abs/2411.13374, 2024. doi:10.48550/arXiv.2411.13374.

[bib.bib7] [7] Jeremy P. Spinrad. Circular-arc graphs with clique cover number two. J. Comb. Theory B, 44(3):300–306, 1988. doi:10.1016/0095-8956(88)90038-X.