This a part of the Collaborative Research Project GraDR. It consists of two participating sites: Charles University in Prague and Masaryk University in Brno. The leader of this project is Jan Kratochvíl.

The team consists of the following people:

**Leader:**Jan Kratochvíl**Senior Researchers:**Jiří Matoušek, Jiří Fiala, Martin Pergel, Vít Jelínek**Post-docs:**Torsten Ueckerdt (1/9/2011-30/6/2012), Maria Saumell (1/10/2011-31/7/2012)**Students:**Pavel Klavík, Jan Kynčl, Michal Vaner**Past participants:**Tomáš Vyskočil (1/3/2011-30/6/2012), Bernard Lidický (1/3/2011-30/9/2011), Lukáš Mach (1/10/2011-30/9/2012)

The team is responsible for WP01 Slope number and participates in WP04, WP05, WP09, WP10 and WP12.

Jelinek et al. have improved their upper bound for planar slope number from and exponential bound (shown in their paper at GD'09) to a polynomial bound
O(Delta^5). This result will be published in the journal version which has
been accepted and is waiting for publication:

*Vit Jelinek, Eva Jelinkova, Jan Kratochvil, Bernard Lidicky, Marek Tesar, Tomas Vyskocil: The Planar Slope
Number of Planar Partial 3-Trees of Bounded Degree, to appear in Graphs and
Combinatorics.*

For outerplanar drawings of outerplanar graphs, Delta-1 directions suffice
for all graphs and are necessary for some, as shown in

*Kolja B. Knauer, Piotr Micek, Bartosz Walczak: Outerplanar Graph Drawings with Few Slopes. COCOON 2012, LNCS 7434, Springer 2012, pp. 323-334
*

Research in planarity of partially embedded graphs continued by showing a finite number of forbidden obstruction with respect to a minor-like ordering of partially embedded graphs. It has appeared in

*Vít Jelínek, Jan Kratochvíl, Ignaz Rutter:
A kuratowski-type theorem for planarity of partially embedded graphs,
Symposium on Computational Geometry 2011: pp. 107-116*

We have written several papers on the partial representation extension problem introduced by Klavík et al. (TAMC'11).
These papers are dealing with classes of function graphs, permutation graphs, chordal graphs, proper
and unit interval graphs and interval graphs.

*Pavel Klavík, Jan Kratochvíl, Tomasz Krawczyk, Bartosz Walczak:
Extending partial representations of function graphs and permutation graphs,
Algorithms - ESA 2012, Lecture Notes in Computer Science, vol. 7501, pp. 671-682 (2012).
*

*Pavel Klavík, Jan Kratochvíl, Yota Otachi, Toshiki Saitoh:
Extending partial representations of subclasses of chordal graphs,
Accepted to ISAAC 2012.
*

*Pavel Klavík, Jan Kratochvíl, Yota Otachi, Ignaz Rutter, Toshiki Saitoh, Maria Saumell, Tomáš
Vyskočil:
Extending partial representations of proper and unit interval graphs,
In preparation (2012).
*

*Pavel Klavík, Jan Kratochvíl, Yota Otachi, Toshiki Saitoh, Tomáš Vyskočil:
Linear-time algorithm for partial representation extension of interval graphs,
In preparation (2012).
*

We have some new results concerning bend-bounded path intersection representations.

*
Daniel Heldt, Kolja Knauer, Torsten Ueckerdt:
On the bend-number of planar and outerplanar graphs,
Lecture Notes in Computer Science, volume 7256, pages 458-469, LATIN 2012: Theoretical
Informatics - 10th Latin American Symposium, (2012).
*

*
Steven Chaplick, Vít Jelínek, Jan Kratochvil and Tomáš Vyskočil:
Bend-Bounded Path Intersection Graphs: Sausages, Noodles, and Waffles on a Grill,
accepted to WG 2012.
*

The team consists of the following people:

**Leader:**Petr Hliněný**Students:**Martin Derka, Marek Derňár, Matěj Klusáček

The team is responsible for WP08 Crossing number and currently participates in WP04.

P. Hliněný collaborates with M. Chimani and partly P. Mutzel (IP2) on approximation algorithms for
the crossing number of restricted graph classes. Namely, they have shown that a constant factor
approximation exists on apex graphs *(European J. Combinatorics 33, 2012, 326-335)*, and more
generally on graphs being a small number of edges from planarity *(ICALP 2011, journal paper in
preparation)*.

P. Hliněný with his doctoral student M. Derňár and D. Bokal and M. Bračič from Maribor study degree-related properties of crossing critical graph families, extending their previous separate works. A paper is in preparation. P. Hliněný with Z. Dvořák and L. Postle give new structural properties of any k-crossing-critical graph families. Again, a paper is in preparation.

M. Chimani (IP2), M. Derka, P. Hliněný, and M. Klusáček have discovered
conceptually new planar emulators of several non-projective graphs. This
shows that the planar emulators problem is very different from the
better known Negami's planar cover conjecture. *(IWOCA 2011, journal
version Advances in Applied Mathematics 50, 2013, 46-68.)*