Geometric Representations of Graphs
Joint STOC/SoCG Workshop Day on Saturday June 18, 2016

Update after the event: Slides of our speakers are now available. See below.

Organizers: Steven Chaplick (Universität Würzburg) and Piotr Micek (Jagiellonian University)

Description: The study of graphs via geometric representations is a classical topic in both computational geometry and the theory of computing. This is due to many practical problems having natural models via geometric objects (e.g., for channel assignment, map labeling, VLSI design) and the fact that they give rise to beautiful combinatorial and algorithmic results. In recent years, a lot of progress has been made in the study of geometric intersection graphs. Some notable solved problems include Scheinerman’s conjecture, Erdos’s problem on chi-boundedness of segment graphs, and the hardness of the clique problem for segment graphs. Additionally, there has been a lot of work on settling many fascinating open questions, e.g., the k-quasi-planar graph conjecture, approximability of maximum independent sets in rectangle graphs, and understanding the existential theory of the reals complexity class. This area still continues to grow with new exciting problems every year. For example, regarding the existence of small separators in geometric intersection graphs, and the computational complexity of the find partial representation extensions and simultaneous representations.

We will gather researchers working on these topics in order to exchange the ideas for further research. The focus will be mainly on open problems and possible approaches to them rather than on particular known results. The talks will be 25-30-minutes in duration and will have a survey character which is accessible to both the SoCG and STOC audiences. We will conclude with a problem session summarizing the workshop and allowing other participants to propose their problems.

Program

3:30 - 4:00 Jean Cardinal Université Libre de Bruxelles
Geometric Representations of Graphs and the Existential Theory of the Reals [pdf]

Deciding the validity of sentences in the existential theory of the reals (ETR) amounts to checking the existence of a real solution to systems of polynomial equalities and inequalities. In the late eighties, Mnëv stated a theorem that led to a proof that the stretchability problem for pseudoline arrangements was ETR-complete. Since then, many more natural problems in computational geometry have been proven ETR-complete, in particular in the field of graph drawing and geometric graphs. We will describe the foundation of those proofs, some well-known results in this vein, and recent additions to the list.

4:00 - 4:30 Radoslav Fulek IST Austria
Strong Hanani-Tutte for radial drawings [pdf]

A drawing of a graph G is radial if the vertices of G are placed on concentric circles C_1,..., C_k with common center c, and edges are drawn radially: every edge intersects every circle centered at c at most once. G is radial planar if it has a radial embedding, that is, a crossing-free radial drawing. If the vertices of G are ordered or partitioned into ordered levels (as they are for leveled graphs), we require that the assignment of vertices to circles corresponds to the given ordering or leveling. A pair of edges e and f in a graph is independent if e and f do not share a vertex. We show that a graph G is radial planar if G has a radial drawing in which every two independent edges cross an even number of times; the radial embedding has the same leveling as the radial drawing. In other words, we establish the variant of the Hanani-Tutte theorem for radial planarity. Our result implies a very simple polynomial-time algorithm for radial planarity based on solving a system of linear equations over Z_2. This is a joint work with M. Pelsmajer and M. Schaefer.

4:30 - 5:00 Csaba Tóth California State University Northridge
Flexible Contact Representations [pdf]

Contact graph representations are easy to handle when the representations are unique or severely constrained. This talk summarizes recent results on highly flexible representations. Two models are considered: body-and-hinge frameworks and contact graphs of convex bodies in the plane. It is shown that it is strongly NP-hard to decide (1) whether a given body-and-hinge framework is realizable when the bodies are convex polygons in the plane and their contact graph is a tree; (2) whether a given tree is the contact graph of interior-disjoint unit disks in the plane. The main challenge in both cases is that any realization has a high degree of freedom, which raises several open problems about the realization space of contact representations.

5:00 - 5:30 Bartosz Walczak Jagiellonian University
Coloring geometric intersection graphs [pdf]

Colorings of graphs represented by geometric objects have been studied since the 1960s for purely aesthetic as well as practical reasons. In particular, geometric representations provide natural examples of classes of graphs that are χ-bounded (near-perfect), which means that their chromatic number is bounded by a function of their clique number. It was conjectured for many years that all classes of geometric intersection graphs in the plane are χ-bounded. However, in 2012, Pawlik et al. disproved this conjecture presenting a construction of triangle-free segment intersection graphs with arbitrarily large chromatic number. This result stimulated further research aimed at understanding how the chromatic number of geometric intersection graphs behaves under the assumption that their clique number is bounded. After introducing basic problems and results on colorings of geometric intersection graphs, I will briefly discuss some methods applied to obtain lower and upper bounds on their chromatic number, and connections to other graph-theoretic problems. I will also report on a very recent result, joint with Alexandre Rok (Ben-Gurion University of the Negev): the class of intersection graphs of curves in the plane each crossing a fixed line at least once and at most t times is χ-bounded, for every t.

5:30 - 6:00 Steven Chaplick Universität Würzburg
Open problem session