 |
|
||||
- STEVEN CHAPLICK, TU Berlin
Representing Planar Graphs By Homothets of Convex Sets [PDF]
-
We discuss the relationship between planar graphs and overlap and intersection graphs of homothetic copies of a fixed convex set $S$ (i.e., $S$-overlap and $S$-intersection graphs).
We show that for every convex set $S$, every planar graph is an $S$-overlap graph. Our overlap results further imply that for many convex sets $S$ (essentially those which are neither ``trapezoidal'' nor ``hexagonal''), every planar graph is an $S$-intersection graph.
The foundations of our results are the Convex and Square Packing Theorems of Schramm (1990,1993).
This is joint work with Torsten Ueckerdt.
- GRZEGORZ GUTOWSKI, Jagiellonian University
Extending Partial Bar Visibility Representations is Hard [PDF]
-
Bar visibility drawing of a graph represents vertices as horizontal line segments so that there is a clear, vertical line of sight between each pair of adjacent vertices.
This simple idea leads to at least three different definitions of bar visibilty representations.
Those representations are tightly connected with st-numberings of planar graphs.
In this talk we show that, independent of the defintion, it is NP-complete to decide if a given predrawing of some of the vertices of a graph can be extended into a drawing of the whole graph.
- JAN HUBICKA, Department of Mathematics and Statistics, University of Calgary
Ramsey lifts of classes of intersection graphs [PDF]
-
Class $\mathcal K$ of finite structures is Ramsey if for every $A,B\in \mathcal K$ there exists $C\in \mathcal K$ s.t. for every 2-coloring of its substructures isomorphic to $A$ with there exists an isomorphic copy of $B$ in $C$ where all copies of $A$ are monochromatic. For example the class of graphs is not Ramsey. Nešetřil\&Rödl proved that adding a linear order (lift) makes it Ramsey. A recent connection to topological dynamics motivated the classification programme of Ramsey classes. We extend the list by some intersection graphs classes.
This is joint work with Steve Chaplick, Jakub Jasiński and Jaroslav Nešetřil.
- GEORGE MERTZIOS, Durham University
New Geometric Representations and Domination Problems on Tolerance and Multitolerance Graphs [PDF]
-
In this talk we introduce two new geometric representations for tolerance and multitolerance graphs, given by points and line-segments in the plane. Using these representations, we surprisingly prove that the dominating set problem can be solved in polynomial time on tolerance graphs and that it is APX-hard on multitolerance graphs, thus solving a longstanding open problem. This is the first known problem with a different complexity status in these two graph classes. Furthermore we demonstrate the potential of these representations for further exploitation via sweep-line algorithms by presenting a polynomial-time algorithm for the independent dominating set problem on multitolerance graphs.
