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:

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

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.

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.

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

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.

Bartosz Walczak, Colorings of Geometric Intersection Graphs and Related Problems


This talk will survey some recent results and open problems concerning proper colorings and Kk-free colorings (i.e. colorings in which every color class is required to induce a Kk-free graph) of geometric intersection graphs with bounded clique number. In particular, the following questions will be addressed: (i) In what classes of geometric intersection graphs is the (Kk-free) chromatic number bounded in terms of the clique number? (ii) How big can the (Kk-free) chromatic number be with respect to the number of vertices for other classes of geometric intersection graphs with bounded clique number? The talk will also discuss connections to other problems, in particular, to the well-known conjecture that the number of edges in k-quasi-planar graphs (i.e. graphs drawn in the plane with no k pairwise crossing edges) is linear with respect to the number of vertices.

Open Problem Session

Preliminary collection of open problems