GraDR Individual Project 1 - Czech Republic

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.

Prague team

The team consists of the following people:

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

Progress in WP01 Slope number

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

Contribution to WP04 Constrained Embeddings

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

Contribution to WP10 Intersection and contact representations

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.

Brno team

The team consists of the following people:

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

Progress in WP08 Crossing numbers

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.

Contribution to WP04 Constrained Embeddings

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.)