Anna Lubiw
# 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.

## 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

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