Geometric Intersection Graphs: Problems and Directions

CG Week Workshop, Eindhoven, June 25, 2015

**Organizers:** Piotr Micek and Bartosz Walczak

**Description:** Graphs represented by geometric objects have been studied in computational geometry from the very beginning, because of various practical applications as well as the beautiful combinatorics they give rise to. In recent years, a lot of progress has been made in the study of geometric intersection graphs. In this workshop, we would like to survey major open problems concerning various aspects of geometric intersection graphs, discuss promising approaches to them, and propose some directions for further research. The following topics are likely to be covered:

- computational complexity of recognition and partial representation extension,
- approximation algorithms for the maximum clique and maximum independent set problems,
- separators in geometric intersection graphs,
- colorings of geometric intersection graphs with bounded clique number,
- extremal problems on geometric and topological graphs (in particular, the
*k*-quasi-planar graph conjecture).

The workshop is part of CG Week 2015. It takes place on Thursday (June 25) afternoon in two sessions (14:00–15:30 and 16:00–17:30) separated by a break (15:30–16:00) that is common for all CG Week events. See the CG Week 2015 main page for information about the venue and about other CG Week events.

Tentative Program

Session I: 14:00–15:30

**14:00–14:30**

Sergio Cabello, *Interval Graphs in Data Streaming*

In this talk we will advocate that basic graph problems should be considered for geometric intersection graphs in the data streaming model. We will look in some detail at the interval selection problem, that is, finding a largest independent set in an interval graph, in the data streaming model. This part is joint work with Pablo Perez-Lantero. Towards the end of the talk I will restate a couple of unrelated problems that, I think, should get some attention.

**14:30–15:00**

Parinya Chalermsook, *Coloring and Independent Sets of Rectangles: Recent Developments and New Challenges*

This talk will focus on two problems on rectangle intersection graphs: (i) approximating the independence number of rectangle intersection graphs and (ii) upper bounding the chromatic number of a graph in terms of its clique number. The former question has received a lot of attention from the approximation algorithms community due to its close connections to other optimization problems, such as map labeling and network resource allocation. The latter question was raised in 1948 and there has been essentially no progress since 1960 (i.e. for about half a century). There is a close connection between (i) and (ii). I will start by giving a survey of recent developments on both problems. Then I will present some intermediate open problems that would help in gaining further insights for (i) and (ii). These intermediate problems could be of independent interest.

**15:00–15:30**

Stefan Felsner, *Intersection Graphs and Order Dimension*

Containment graphs are comparability graphs and have, for a long time, been related to the notion of order dimension. In this talk we focus on connections between intersection graphs and order dimension. The starting point of the story is the observation that partial orders of height two whose comparability graph is a grid intersection graph have order dimension at most four. Refinements of this argument allow to distinguish between various classes of graphs that are sandwiched between grid intersection graph and bipartite permutations graphs. A construction involving grid intersection graphs is used for a new simple proof of the Brightwell-Trotter Theorem. Finally we use intersection and containment graphs of triangles to show that recognition of partial orders of height two and dimension three is NP-complete. This resolves a long standing complexity question.

Session II: 16:00–17:30

**16:00–16:30**

Andrew Suk, *"No k Pairwise Crossing" vs "No k Pairwise Disjoint"*

We will survey several problems surrounding an old conjecture which states that the number of edges in a graph drawn in the plane with no *k* pairwise crossing edges is at most linear in the number of vertices. We will also make comparisons to its "dual" counterpart, which is a conjecture of Pach and Tóth, stating that the number of edges in a graph drawn in the plane with no *k* pairwise disjoint edges is at most linear in the number of vertices. Both conjectures are still open, and in this talk, we will discuss several partial results and tools used in tackling these problems.

**16:30–17:00**

Bartosz Walczak, *Colorings of Geometric Intersection Graphs and Related Problems*

This talk will survey some recent results and open problems concerning proper colorings and *K _{k}*-free colorings (i.e. colorings in which every color class is required to induce a

**17:00–17:30**

Open Problem Session