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

Seminars
Fall 2014 Schedule
Winter 2015 Schedule
Archive


         
     
 
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

Abstract:

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.