Anna Lubiw is a

computer scientist A computer scientist is a person who is trained in the academic study of computer science. Computer scientists typically work on the theoretical side of computation, as opposed to the hardware side on which computer engineers mainly focus (al ...

known for her work in

computational geometry Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems ar ...

and

graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...

. She is currently a professor at the

University of Waterloo The University of Waterloo (UWaterloo, UW, or Waterloo) is a public research university with a main campus in Waterloo, Ontario Waterloo is a city in the Canadian province of Ontario. It is one of three cities in the Regional Municipality ...

Education

Lubiw received her

Ph.D A Doctor of Philosophy (PhD, Ph.D., or DPhil; Latin: or ') is the most common Academic degree, degree at the highest academic level awarded following a course of study. PhDs are awarded for programs across the whole breadth of academic fields ...

from the

University of Toronto The University of Toronto (UToronto or U of T) is a public research university in Toronto, Ontario, Canada, located on the grounds that surround Queen's Park. It was founded by royal charter in 1827 as King's College, the first institution ...

in 1986 under the joint supervision of Rudolf Mathon and

Stephen Cook Stephen Arthur Cook (born December 14, 1939) is an American-Canadian computer scientist and mathematician who has made significant contributions to the fields of complexity theory and proof complexity. He is a university professor at the Unive ...

Research

At Waterloo, Lubiw's students have included both

Erik Demaine Erik D. Demaine (born February 28, 1981) is a professor of computer science at the Massachusetts Institute of Technology and a former child prodigy. Early life and education Demaine was born in Halifax, Nova Scotia, to artist sculptor Martin ...

and his father

Martin Demaine Martin L. (Marty) Demaine (born 1942) is an artist and mathematician, the Angelika and Barton Weller artist in residence at the Massachusetts Institute of Technology (MIT). Demaine attended Medford High School in Medford, Massachusetts. After st ...

, with whom she published the first proof of the fold-and-cut theorem in mathematical origami. In

graph drawing Graph drawing is an area of mathematics and computer science combining methods from geometric graph theory and information visualization to derive two-dimensional depictions of graph (discrete mathematics), graphs arising from applications such a ...

, Hutton and Lubiw found a polynomial time algorithm for

upward planar drawing In graph drawing, an upward planar drawing of a directed acyclic graph is an embedding of the graph into the Euclidean plane, in which the edges are represented as non-crossing monotonic upwards curves. That is, the curve representing each edge ...

of graphs with a single source vertex. Other contributions of Lubiw include proving the

NP-complete In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryi ...

ness of finding

permutation pattern In combinatorial mathematics and theoretical computer science, a permutation pattern is a sub-permutation of a longer permutation. Any permutation may be written in one-line notation as a sequence of digits representing the result of applying the p ...

s, and of finding

derangement In combinatorial mathematics, a derangement is a permutation of the elements of a set, such that no element appears in its original position. In other words, a derangement is a permutation that has no fixed points. The number of derangements of ...

s in

permutation group In mathematics, a permutation group is a group ''G'' whose elements are permutations of a given set ''M'' and whose group operation is the composition of permutations in ''G'' (which are thought of as bijective functions from the set ''M'' to it ...

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.About the orchestra
, Univ. of Waterloo, retrieved 2013-10-16. She is married to

Jeffrey Shallit Jeffrey Outlaw Shallit (born October 17, 1957) is a computer scientist, number theorist, and a noted critic of intelligent design. He is married to Anna Lubiw, also a computer scientist. Early life and education Shallit was born in Philadelp ...

, also a computer scientist.

Selected publications

*. *. First presented at the 2nd ACM-SIAM Symposium on Discrete Algorithms, 1991. *. First presented at WADS 1993. *.

References

External links

Home page
at U. Waterloo * {{DEFAULTSORT:Lubiw, Anna Year of birth missing (living people) Living people Canadian computer scientists Canadian women computer scientists Researchers in geometric algorithms Graph drawing people University of Toronto alumni University of Waterloo faculty