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

A graph $G$ is \emph{max pointtolerance (MPT)} when each vertex $v$ of $G$ can be mapped to a \emph{pointedinterval} $(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 genomewide 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 NPcomplete 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 straightline planar drawings of a graph, is there a \emph{morph} between them, i.e. a continuous transformation that preserves straightline 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 BarreraCruz 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 HananiTutte style theorems for those planarity notions suggest a uniform algebraic approach to all these notions. As a result, we can exhibit a polynomialtime algorithm that may decide simultaneous planarity, cplanarity, 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 selfaware 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 Lshapes, Lcollections for short, in the plane and in particular the intersection and contact graphs defined by such an Lcollection. It turns out that Lcollections 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 Lcollections, 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.