Skip to content. Skip to navigation
McGill Home SOCS Home
Personal tools
You are here: Home Announcements and Events Seminars profile

Fall 2013 Schedule
Winter 2014 Schedule

2013/03/27, MC 437, 10:00 - 11:00

Graph Layouts
Vida Dujmovic , Assistant Professor, Carleton University, School of Mathematics and Statistics & Department of Syste

Area: Theory


A 3D grid drawing of a graph is a placement of the vertices at distinct gridpoints in 3D such that the straight line-segments representing the edges are pairwise non-crossing. 3D grid drawings of small volume are closely related to a graph parameter called queue number. I will present the state of the art on the topic focusing on the most recent result that planar graphs have O(n log n) volume 3D grid drawings and O(log n) queue number. This improves the result by Di Battista, Frati and Pach [FOCS’10, pp. 365–374].

Biography of Speaker:

Vida Dujmovic is an Assistant Professor at the School of Mathematics and Statistics & Department of Systems and Computer Engineering of Carleton University. She has obtained her PhD and MSc from McGill University and her BEng from University of Zagreb in Croatia. She is a recipient of NSERC Doctoral Prize and, more recently, Faculty Research Achievement Award of Carleton University.