Anna Lubiw

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]

Anna Lubiw
Alma mater	University of Toronto
Known for	Computational geometry, graph theory
Spouse	Jeffrey Shallit
Awards	ACM Distinguished Member, 2009
Website	https://cs.uwaterloo.ca/~alubiw/Site/Anna_Lubiw.html

Education

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

Research

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]

Awards

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

Personal life

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

• 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.