CMS/SMC
CanaDAM 2013
Memorial University of Newfoundland, June 10 - 13, 2013 www.cms.math.ca//2013
       

Geometric Representations of Graphs
Organizer and Chair: 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.

This~is~joint~work~with~D.Catanzaro,~B.Halld\'orsson,~M.Halld\'orsson,~and~J.Stacho.

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.

Event Sponsors

Atlantic Association for Research in the Mathematical Sciences Centre de recherches mathématiques The Fields Institute Pacific Institute for the Mathematical Sciences Canadian Mathematical Society Memorial University of Newfoundland