5 papers
On the structure of normalized models of circular-arc graphs -- Hsu's approach revisited
Tomasz Krawczyk
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-a…
Characterization of Circular-arc Graphs: III. Chordal Graphs
Yixin Cao, Tomasz Krawczyk
We identify all minimal chordal graphs that are not circular-arc graphs, thereby resolving one of ``the main open problems'' concerning the structures of circular-arc graphs as pos…
Characterization of Circular-arc Graphs: II. McConnell Flipping
Yixin Cao, Tomasz Krawczyk
McConnell [FOCS 2001] presented a flipping transformation from circular-arc graphs to interval graphs with certain patterns of representations. Beyond its algorithmic implications,…
Circular-arc graphs and the Helly property
Jan Derbisz, Tomasz Krawczyk
In this paper we investigate some problems related to the Helly properties of circular-arc graphs, which are defined as intersection graphs of arcs of a fixed circle. As such, circ…
Characterization of Chordal Circular-arc Graphs: I. Split Graphs
Yixin Cao, Jan Derbisz, Tomasz Krawczyk
The most elusive problem around the class of circular-arc graphs is identifying all minimal graphs that are not in this class. The main obstacle is the lack of a systematic way of…