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

Geometric Representations of Graphs II
Org: Jan Kratochvil (Charles University, Prague, Czech republic)

STEFAN FELSNER, Technische Universität Berlin
Graphs and Rectangle Dissections  [PDF]

From a dissection of a rectangle into smaller rectangles we can get various planar graphs. We review links between these graphs and algorithmic ideas for constructing a corresponding dissection. Then we move on to additional restrictions, e.g., the requirement that all rectangles in the dissection are squares or that the areas of rectangles are prescribed. We survey parts of the existing theory and some related problems.

DANIEL GONÇALVES, LIRMM (CNRS and Univ. Montpellier 2)
Planar Graphs as Contact or Intersection Graphs of Homothetic Triangles  [PDF]

De Fraysseix, Ossona de Mendez and Rosenstiehl proved that every planar graph admits a contact representation by right triangles with an horizontal side. We cannot strengthen this by requirering the triangles to be homothetic. However we will show that such strengthening is possible for a large class of planar graphs, the subgraphs of 4-connected triangulations. We will also show that this implies that every planar graph is the intersection graph of homothetic triangles.

ANNA LUBIW, University of Waterloo
Simultaneous Graph Representations  [PDF]

Two graphs sharing some vertices and edges are {\it simultaneously planar} if they have planar embeddings with common vertices/edges represented by the same points/curves. We give a linear time recognition algorithm when the common graph is 2-connected (with B. Haeupler and K.R. Jampani).

{\it Simultaneous interval graphs} have common vertices represented by the same intervals. We give a polynomial time recognition algorithm (with K.R. Jampani). These are related to probe graphs and graph sandwich problems.

GEORGE MERTZIOS, Caesarea Rothschild Institute, University of Haifa, Israel
Geometric intersection models on the plane and the 3D-space  [PDF]

Some intersection models provide a natural and intuitive understanding of the structure of a class of graphs. In particular, they are very helpful in the design of efficient algorithms that solve optimization problems, as well as in proving hardness results. In this talk we provide a survey of recent algorithmic and structural results on several old and new intersection models on the plane and the 3D-space, namely for tolerance, multitolerance, trapezoid, and triangle graphs.

MARCUS SCHAEFER, DePaul University
Removing Monotone Crossings  [PDF]

Pach and Toth showed that if a graph has an $x$-monotone drawing in which every pair of edges crosses an even number of times, then the graph has a straight-line embedding in which the $x$-coordinates of all vertices are unchanged. We strengthen this by showing that the conclusion remains true if adjacent edges are allowed to cross oddly. This yields a new and simple algorithm to test level-planarity.

Joint work with Fulek, Pelsmajer, Stefankovic.

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