CanaDAM 2013 Université Memorial de Terre-Neuve, 10 - 13 juin 2013 www.smc.math.ca//2013f

Geometric Representations of Graphs
Responsable et prÃ©sident: Steven Chaplick (Charles University, Prague, Czech Republic)
[PDF]

STEVEN CHAPLICK, Charles University, Prague, Czech Republic
Max Point-Tolerance Graphs  [PDF] [SLIDES]

A graph $G$ is \emph{max point-tolerance (MPT)} when each vertex $v$ of $G$ can be mapped to a \emph{pointed-interval} $(I_v,~p_v)$ where $I_v$ is an interval of $\mathbb{R}$ and $p_v \in I_v$ such that $uv$ is an edge of $G$ iff $I_u~\cap~I_v~\supseteq~\{p_u,p_v\}$. MPT graphs arise naturally as a way to model relationships among DNA fragments in genome-wide association studies. We characterize these graphs by a geometric representation and a vertex ordering condition. We also show how to find a maximum weighted independent set in polynomial time, and demonstrate that it is NP-complete to find the chromatic number.

ANNA LUBIW, University of Waterloo
Morphing Planar Graph Drawings  [PDF]

Given two straight-line planar drawings of a graph, is there a \emph{morph} between them, i.e. a continuous transformation that preserves straight-line planarity?

In 1944, Cairns proved that the answer is yes, but his morph used an exponential number of discrete steps. I will present a polynomial time morph (this is joint work with a group of people). Furthermore, the morph is composed of \emph{unidirectional} steps in which vertices move parallel to one line (this part is joint with Fidel Barrera-Cruz and Penny Haxell).

MARCUS SCHAEFER, DePaul University
Toward a Theory of Planarity: An algorithm for simultaneous planarity?  [PDF] [SLIDES]

We study relationships between various notions of planarity and show how some recent results on Hanani-Tutte style theorems for those planarity notions suggest a uniform algebraic approach to all these notions. As a result, we can exhibit a polynomial-time algorithm that may decide simultaneous planarity, c-planarity, partially embedded planarity, etc., with the one caveat that we can only prove correctness of the algorithm relative to some redrawing conjectures. The algorithm is self-aware in the sense that it would recognize a counterexample to its correctness.

TORSTEN UECKERDT, Karlsruhe Institute of Technology
Various Applications of L  [PDF]

We are interested in collections of L-shapes, L-collections for short, in the plane and in particular the intersection and contact graphs defined by such an L-collection. It turns out that L-collections show up in various seemingly unrelated representability problems, such as contact/intersection representations by boxes, triangles or segments.

We present an overview over recent results and ongoing work in the area of L-collections, including several open problems.

RYUHEI UEHARA, Japan Advanced Institute of Science and Technology
The graph isomorphism problem on graphs with geometric representations  [PDF] [SLIDES]

The computational complexity of the graph isomorphism problem is a long standing open problem. One of approaches is investigation of the boundary of the difficulty. That is, what the graph class that is easy/hard from the viewpoint of the graph isomorphism. In this talk, we concentrate on the graph classes that have geometric representations. In some case, such a representation helps us to solve the graph isomorphism problem in polynomial time. However, sometimes, the graph isomorphism is as hard as in general case even if they have a simple intersection model. We summarize the recent results about this area.