William Evans

Associate Professor

Office Phone #

Academic Information

Associate Professor (since 2004), Assistant Professor (2001-2004), University of British Columbia; Assistant Professor, University of Arizona (1996-2000); NSERC Postdoctoral Fellow, University of British Columbia (1994-1996); PhD Computer Science, University of California at Berkeley (1994); B.S. Computer Science, Yale University (1987).

Interest Keywords

graph drawing
computational geometry
information theory
program compression
theoretical computer science


My research interests are in the design of algorithms and the understanding of the fundamental limitations of various models of computation. I've pursued this interest in various areas of computer science:

* Graph Drawing - I study problems related to the geometric representation of graphs. For example, I'm interested in what graphs can be represented using contact or visibility between geometric objects, and how several graphs can be represented simultaneously using a shared set of objects.
* Algorithms that operate with uncertain input - What guarantees can an algorithm make if it knows that its input is uncertain but the uncertainty is bounded? How do we design and analyze algorithms that can gain more certainty at a price?
* Computational geometry - I'm interested in geometric problems or problems whose solution requires geometric techniques. I've been particularly interested in problems arising from geographic information systems. For example, problems in map drawing and concise surface (terrain) representation.
* Information theory - How is computation influenced by random noise? What price do you pay for using Boolean gates that produce the wrong output randomly with some small probability? I've been studying questions of this type using tools from information theory and computational complexity theory.
* Program compression - Software that is intended for palm-top computers, cell phones, and embedded controllers is getting more and more complicated, yet space, weight, price, and power consumption issues limit the amount of memory available to run this software. I'm interested in automatically reducing software's memory footprint without changing its function; essentially, exploring techniques that could be used in a very aggressive space-optimizing compiler. Software is also frequently downloaded across potentially slow network connections. I'm interested in how to represent and compress this software to reduce transmission time. In this case, I have the flexibility to choose a compressed form that may require decompression before execution.

Selected Publications

W. Evans and N. Saeedi, "On Characterizing Terrain Visibility Graphs", Journal of Computational Geometry 6(1):108--141, 2015.

W. Evans, V. Kusters, M. Saumell, and B. Speckmann, "Column Planarity and Partial Simultaneous Geometric Embedding", Proceedings of 22nd International Symposium on Graph Drawing, LNCS, p.~259-271, Sep. 2014.

W. Evans, D. Kirkpatrick, M. Löffler, and F. Staals, "Competitive Query Strategies for Minimising the Ply of the Potential Locations of Moving Points", 29th ACM Symposium on Computational Geometry (SoCG), p. 155-165, June 2013.

A. Dean, W. Evans, E. Gethner, J. Laison, M. Safari, and W. Trotter, "Bar k-Visibility Graphs", Journal of Graph Algorithms and Applications, 11(1):45-59, 2007.

Research Interests

computational geometry

Research Groups

Algorithms Lab

Latest Courses

2020 Winter

CPSC 221 - Basic Algorithms and Data Structures
CPSC 221 - Basic Algorithms and Data Structures

2018 Winter

CPSC 221 - Basic Algorithms and Data Structures

2017 Winter

CPSC 536E - Topics in Algorithms and Complexity

2016 Winter

CPSC 420 - Advanced Algorithms Design and Analysis