CanaDAM 2011
Université de Victoria, 31 mai - 3 juin 2011

Geometric Representations of Graphs I
Org: Stefan Felsner (Technische Universitaet Berlin)

MATTHEW FRANCIS, Department of Computer Science, University of Toronto
On Segment graphs  [PDF]

Segment graphs are the intersection graphs of line segments in the plane. It was conjectured by Kratochvil and Kubena that the complement of every planar graph is a segment graph. We show that the counter-examples, if any, to this conjecture have to be somewhat complex planar graphs, as the complement of every partial 2-tree is a segment graph. We also look at some open problems regarding segment graphs.

JAN KRATOCHVIL, Charles University, Prague
Intersection graphs of homothetic polygons  [PDF]

Take a convex polygon and consider its homothetic copies in the plane, i.e. scaling and translation are allowed, no rotations. Several algorithmic, complexity, and structural results on intersection graphs of this type have recently been obtained. For instance the simplest case of a triangle results in the class of max-tolerance graphs, which has very recently been shown to contain all planar graphs. We will survey recent progress and discuss pertaining open problems.

TOBIAS MÜLLER, Centrum Wiskunde en Informatica
The smallest grid needed to represent a geometric intersection graph  [PDF]

Spinrad [2003] asked for the smallest $k = k(n)$ such that every disk graph on $n$ vertices can be represented by disks whose radii and coordinates of the centers are at most $k$ in absolute value.

We will show that $k = 2^{2^{\Theta(n)}}$.

On the other hand any intersection graph of homothets/translates of a fixed polygon $P$ can be represented on a $2^{\Theta(n)} \times 2^{\Theta(n)}$-grid and this is sharp.

TORSTEN UECKERDT, Technische Universitaet Berlin
Edge-Intersection Graphs of Grid Paths - the Bend Number  [PDF]

In 2007, Golumbic, Lipshteyn and Stern introduced \textit{edge-intersection graphs of grid paths}, EGP graphs for short. These can be viewed as intersection graphs of systems of intervals in the plane grid. This talk introduces EGP graphs, an associated parameter called the \textit{bend number}, its interrelations with the well-known interval number and track number, and a lot of open questions.

SUE WHITESIDES, Computer Science Department, University of Victoria BC
On Upward Topological Book Embeddings of Upward Planar Digraphs  [PDF]

We study topological book embeddings (spine crossings allowed), point-set embeddings, and simultaneous embeddings of upward planar digraphs. Our approach is based on a linear time algorithm for computing an upward planar drawing of an upward planar digraph, with all vertices collinear.

joint work with G. Giordano, G. Liotta, T. Mchedlidze, and A. Symvonis.

Handling of online submissions has been provided by the CMS.


Centre de recherches mathématiques Fields Institute MITACS Pacific Institute for the Mathematical Sciences Société mathématique du Canada University of Victoria