Basser Seminar Series

Graph representations in a grid

Speaker: Tomas Vyskocil
Charles University, Prague

Time: Monday 20 February 2012, 2:00-3:00pm
Location: The University of Sydney, School of IT Building, Lecture Theatre (Room 123), Level 1
Add seminar to my diary

Abstract

The talk will be about two types of structures which we were interested recently. The first one is an island representation of graphs. A island is set of vertices in the extended grid—plane grid where into each square you add both diagonal edges—which induces connected sub-graph of grid. I will show a connection with the string graphs and show that if we bound size of islands then problem of recognizing such graphs is NP-hard. The second topic I want to talk about are intersection graphs of $k$-bend paths. A $k$-bend path is a simple path in plane grid, where there are at most $k$ 90 degree turns.

We showed that recognition of such graphs is NP-hard and even more that recognition of graphs representable by k-bend paths within graphs representable by $(k+1)$-bend paths is NP-hard as well.

Speaker's biography

Tomas is a PhD student of Prof. Jan Kratochvil at Charles University, Prague. His PhD thesis is about graph drawing and representations. His research interests include combinatorics and complexity theory.