Anna Lubiw

Anna Lubiw
EducationUniversity of Toronto
Known forComputational geometry, graph theory
SpouseJeffrey Shallit
AwardsACM Distinguished Member
Websitehttps://cs.uwaterloo.ca/~alubiw/Site/Anna_Lubiw.html

Anna Lubiw is a computer scientist known for her work in computational geometry and graph theory. She is currently a professor at the University of Waterloo.

Education

Lubiw received her Ph.D from the University of Toronto in 1986 under the joint supervision of Rudolf Mathon and Stephen Cook.

Research

At Waterloo, Lubiw's students have included both Erik Demaine and his father Martin Demaine, with whom she published the first proof of the fold-and-cut theorem in mathematical origami. In graph drawing, Hutton and Lubiw found a polynomial time algorithm for upward planar drawing of graphs with a single source vertex. Other contributions of Lubiw include proving the NP-completeness of finding permutation patterns, and of finding derangements in permutation groups.

Awards

Lubiw was named an ACM Distinguished Member in 2009.

Personal life

As well her academic work, Lubiw is an amateur violinist, and chairs the volunteer council in charge of the University of Waterloo orchestra. She is married to Jeffrey Shallit, also a computer scientist.

Selected publications

References

  1. ↑ Faculty profile Archived 2013-07-22 at the Wayback Machine, University of Waterloo, retrieved 2013-10-16.
  2. ↑ Anna Lubiw at the Mathematics Genealogy Project
  3. ↑ "Maths star from outside the fold", Times Higher Education, March 29, 2002.
  4. ↑ Demaine, Demaine & Lubiw (1999); O'Rourke, Joseph (2013), How to Fold It, Cambridge University Press, p. 144, ISBN 9781139498548.
  5. ↑ Hutton & Lubiw (1996); Di Battista, Giuseppe; Eades, Peter; Tamassia, Roberto; Tollis, Ioannis G. (1998), "Optimal Upward Planarity Testing of Single-Source Digraphs", Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall, pp. 195–200, ISBN 978-0-13-301615-4.
  6. ↑ Bose, Buss & Lubiw (1998); Brignall, Robert (2010), "A survey of simple permutations", in Linton, Steve; Ruškuc, Nik; Vatter, Vincent (eds.), Permutation Patterns, London Mathematical Society Lecture Note Series, vol. 376, Cambridge University Press, pp. 41–66, ISBN 9781139488846, MR 2732823. See in particular pp. 61–62.
  7. ↑ Lubiw (1981); Babai, László (1995), "Automorphism groups, isomorphism, reconstruction", Handbook of combinatorics, Vol. 1, 2 (PDF), Amsterdam: Elsevier, pp. 1447–1540, MR 1373683, A surprising result of Anna Lubiw asserts that the following problem is NP-complete: Does a given permutation group have a fixed-point-free element?.
  8. ↑ ACM Distinguished member page: http://awards.acm.org/award_winners/lubiw_2950848.cfm
  9. ↑ Virginia Gold (November 9, 2009). "ACM Names 84 Distinguished Members for Advances in Computing Technology". Association for Computing Machinery. Retrieved January 12, 2026.
  10. ↑ "Love of music guides fledgling ensemble", Kitchener Record, November 29, 2005.
  11. ↑ About the orchestra Archived 2013-06-05 at the Wayback Machine, Univ. of Waterloo, retrieved 2013-10-16.