Algorithms for interval graphs and related families  Part I
Org:
Yixin Cao (Hong Kong Polytechnic University) et
Derek G. Corneil (University of Toronto)
[
PDF]
 AKANKSHA AGRAWAL, Indian Institute of Technology Madras
Polynomial Kernel for Interval Vertex Deletion [PDF]

Given a graph $G$ and an integer $k$, Interval Vertex Deletion (IVD) asks whether there exists $S \subseteq V(G)$ of size at most $k$, such that $G–S$ is an interval graph. The existence of polynomial kernel for IVD remained a wellknown open problem in Parameterized Complexity. In this talk we will look at a sketch of polynomial kernel for IVD. We will mainly focus on a kernel for IVD, when parameterized by the vertex cover number. The ideas that will be presented are (some of the) key ingredients in our kernel for IVD, when parameterized by the solution size.
 FLAVIA BONOMO, University of Buenos Aires
Algorithms for kthin and proper kthin graphs [PDF]

The (proper) thinness of a graph is a with parameter generalizing
(proper) interval graphs, which are exactly the (proper) 1thin
graphs. A wide family of problems (including list matrix partition
with bounded size matrix) can be polynomially solved for graphs
with bounded thinness, and it can be enlarged in the proper case.
We will survey these results, along with some structural
characterizations and algorithmic problems related to recognition,
which is open. We will also describe the behavior of both
parameters under some graph operations, and relate them to other
graph invariants in the literature.
 DEREK G. CORNEIL, University of Toronto
Early days of interval graph algorithms [PDF]

This talk presents a low teck, personal voyage into interval graphs and related graph families. The talk starts with needed definitions of various graph families and early interval graph recognition algorithms leading to a discussion of the Lekkerkerker Boland Theorem and Asteroidal Triplefree graphs. The voyage continues into the role played by graph searches, most notably LexBFS. Along the way, we encounter surprising observations, false steps and shifting perspectives.
 GUILLAUME DUCOFFE, University of Bucharest, Romania
Faster computation of graph diameter by using one (or two) properties of the interval graphs [PDF]

For communication networks, and many others, important characteristics such as maximum communication delays, and centralities of nodes, can be derived from the computation of classic graph parameters, such as diameter, radius, average distance and median. One can solve all these problems in linear time on interval graphs, but which of these properties of this graph class are the true reason? We will review whether similar computational results can be achieved by relaxing the definition of interval graphs and/or keeping only a few of their nice properties (say, Helly property of the balls, chordality, ATfreeness, bounded VCdimension, etc.).
 FRANCISCO SOULIGNAC, University of Buenos Aires
Representation problems for unit interval and unit circulararc graphs [PDF]

The last decade saw an increasing research on numerical representation problems for unit circulararc models (UCA) and related classes. In these problems we are given a proper circulararc model $\mathcal{M}$ and we have to find a UCA model $\mathcal{U}$, related to $\mathcal{M}$, that satisfies certain numerical constraints. In the classical representation problem, for instance, we are given a proper circulararc model and we have to find an equivalent unit circulararc model whose extremes are all integer and have a polynomial size. In this talk I present a common framework to efficiently solve different numerical representation problems for UCA models.