67 citations · 145 across the 10 of their papers we have counts for
16 papers
Beyond circular-arc graphs -- recognizing lollipop graphs and medusa graphs
Deniz Ağaoğlu Çağırıcı, Onur Çağırıcı, Jan Derbisz +5
In 1992 Biró, Hujter and Tuza introduced, for every fixed connected graph , the class of -graphs, defined as the intersection graphs of connected subgraphs of some subdivisio…
Grounded L-graphs are polynomially -bounded
James Davies, Tomasz Krawczyk, Rose McCarty +1
A grounded L-graph is the intersection graph of a collection of "L" shapes whose topmost points belong to a common horizontal line. We prove that every grounded L-graph with clique…
Colouring polygon visibility graphs and their generalizations
James Davies, Tomasz Krawczyk, Rose McCarty +1
Curve pseudo-visibility graphs generalize polygon and pseudo-polygon visibility graphs and form a hereditary class of graphs. We prove that every curve pseudo-visibility graph with…
Vertex deletion into bipartite permutation graphs
Łukasz Bożyk, Jan Derbisz, Tomasz Krawczyk +2
A permutation graph can be defined as an intersection graph of segments whose endpoints lie on two parallel lines and , one on each. A bipartite permutation graph is a p…
Testing isomorphism of circular-arc graphs -- Hsu's approach revisited
Tomasz Krawczyk
Circular-arc graphs are intersection graphs of arcs on the circle. The aim of our work is to present a polynomial time algorithm testing whether two circular-arc graphs are isomorp…
On-line partitioning of width w posets into w^O(log log w) chains
Bartłomiej Bosek, Tomasz Krawczyk
An on-line chain partitioning algorithm receives the elements of a poset one at a time, and when an element is received, irrevocably assigns it to one of the chains. In this paper,…