Anna LubiwResearch Interests

Professor Lubiw's research is in the area of algorithms, specifically computational geometry and graph algorithms.

One main focus is finding and manipulating geometric representations of graphs (social networks, database hierarchies, the internet, chemical molecular structures).  Currently she works on morphing graph drawings, and on finding "simultaneous" representations of graphs that share some vertices and edges, with the constraint that the shared part be represented consistently.

In a more geometric vein, Professor Lubiw has worked on folding and unfolding problems, for example finding the extra folds that are needed to flatten polyhedra (e.g., the creases that form on cereal boxes when you squash them for recycling).  

She has worked on shortest path problems both in the geometric setting and in graphs.  One example is
finding shortest paths on terrains, such as the earth's surface, while observing height constraints, such as going downhill but not too steeply.  Another example is finding shortest paths in graphs when some subpaths are forbidden but the forbidden set is not known in advance, which has applications in optical network routing and vehicle dispatching.
Professor Lubiw has also worked on such fun topics as map labelling, the Rubik's cube, music pattern matching, and design of pop-up cards.

Degrees and Awards

BSc (Toronto), MMath (Waterloo), PhD (Toronto)

ACM Distinguished Scientist (2009)

Ross and Muriel Cheriton Faculty Fellowship, University of Waterloo (2014 - 2017)

Industrial and Sabbatical Experience

Professor Lubiw has had sabbaticals at MIT, U. Arizona, Rutgers, and U. Wisconsin, Madison.  She worked on circuit extraction at Bell Northen Research before graduate studies.

Representative Publications

Zachary Abel, Erik D. Demaine, Martin L. Demaine, Jin ichi Itoh, Anna Lubiw, Chie Nara, and Joseph O’Rourke. Continuously Flattening Polyhedra Using Straight Skeletons. In: Proc. 30th Annual Symposium on Computational Geometry (SoCG), 2014, 396–405.

Mustaq Ahmed and Anna Lubiw. Shortest paths avoiding forbidden subpaths. Networks 61.4 (2013), 322–334.

Bernhard Haeupler, Krishnam Raju Jampani, and Anna Lubiw. Testing Simultaneous Planarity when the Common Graph is 2-Connected. J. Graph Algorithms Appl. 17.3 (2013), 147–171.

Soroush Alamdari, Patrizio Angelini, Timothy M. Chan, Giuseppe Di Battista, Fabrizio Frati, Anna Lubiw, Maurizio Patrignani, Vincenzo Roselli, Sahil Singla, and Bryan T. Wilkinson. Morphing Planar Graph Drawings with a Polynomial Number of Steps. In: Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA), 2013, 1656–1667.

Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Anna Lubiw, and Andrew Winslow. Algorithms for solving Rubik’s cubes. In: Proceedings of the 19th European Conference on Algorithms (ESA).  Springer-Verlag, 2011, 689–700.

M. Dror, A. Efrat, A. Lubiw, and J. Mitchell. Touring a sequence of polygons. ACM Symp. on Theory of Computing (STOC), pp. 473-482, 2003.

University of Waterloo
Contact information: 

Profiles by type