Geometric Representations of Graphs II
Org:
Jan Kratochvil (Charles University, Prague, Czech republic)
[
PDF]
 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 4connected 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 2connected (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 3Dspace [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 3Dspace, 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 straightline 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 levelplanarity.
Joint work with Fulek, Pelsmajer, Stefankovic.
Handling of online submissions has been provided by the CMS.