#
Monday Lecture and Colloquium

**Monday, February 10, 2014**

Technische Universität Berlin

Institut für Mathematik

Str. des 17. Juni 136

10623 Berlin

room MA 041

** Lecture - 14:15**

### Alexander Wolff -
Universität Würzburg

### Approximation Algorithms for Contact Representations of Rectangles

*Abstract:*

We study the following geometric representation problem: Given a graph
whose vertices correspond to axis-aligned rectangles with fixed
dimensions, arrange the rectangles without overlap in the plane such
that two rectangles touch if the graph contains an edge between them.
This problem is called CONTACT REPRESENTATION OF WORD NETWORKS (CROWN)
since it formalizes the geometric problem behind drawing word clouds in
which semantically related words are close to each other. CROWN is known
to be NP-hard, and there are approximation algorithms for certain graph
classes for the optimization version, MAX-CROWN, in which realizing each
desired adjacency yields a certain profit.

We present the first O(1)-approximation algorithm for the general case,
when the input is a complete weighted graph, and for the bipartite case.
Since the subgraph of realized adjacencies is necessarily planar, we
also consider several planar graph classes (namely stars, trees,
outerplanar, and planar graphs), improving upon known results. For some
graph classes, we also describe improvements in the unweighted case,
where each adjacency yields the same profit. Finally, we show
that the problem is APX-hard on bipartite graphs of bounded maximum degree.

** Colloquium - 16:00**

###
Udo Hoffmann - Technische Universität Berlin

### Grid Intersection Graphs and Order Dimension

*Abstract:*

We show that partial orders of height two whose comparability graph is a grid intersection graph have order dimension at most four.
Starting from this observation we look at various classes of graphs between grid intersection graph and bipartite permutations graphs
and the containment relation on these classes. Order dimension and planarity arguments play a role in many arguments.

Joint work with Steven Chaplick, Stefan Felsner and Veit Wiechert.

Letzte Aktualisierung:
30.01.2014