Anna Lubiw

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search
Anna Lubiw
Alma materUniversity of Toronto
Known forComputational geometry, graph theory
Spouse(s)Jeffrey Shallit
AwardsACM Distinguished Member, 2009

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.[1]


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


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


Lubiw was named an ACM Distinguished Member in 2009.[8]

Personal life[edit]

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

Selected publications[edit]

  • Lubiw, Anna (1981), "Some NP-complete problems similar to graph isomorphism", SIAM Journal on Computing, 10 (1): 11–21, doi:10.1137/0210002, MR 0605600.
  • Hutton, Michael D.; Lubiw, Anna (1996), "Upward planar drawing of single-source acyclic digraphs", SIAM Journal on Computing, 25 (2): 291–311, doi:10.1137/S0097539792235906, MR 1379303, S2CID 207078756. First presented at the 2nd ACM-SIAM Symposium on Discrete Algorithms, 1991.
  • Bose, Prosenjit; Buss, Jonathan F.; Lubiw, Anna (1998), "Pattern matching for permutations", Information Processing Letters, 65 (5): 277–283, doi:10.1016/S0020-0190(97)00209-3, MR 1620935. First presented at WADS 1993.
  • Demaine, Erik D.; Demaine, Martin L.; Lubiw, Anna (1999), "Folding and one straight cut suffice", Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '99), pp. 891–892.


  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:
  9. ^ "Love of music guides fledgling ensemble", Kitchener Record, November 29, 2005.
  10. ^ About the orchestra Archived 2013-06-05 at the Wayback Machine, Univ. of Waterloo, retrieved 2013-10-16.

External links[edit]