Will Evans's Papers

Recognizing and Drawing ICplanar Graphs
F. Brandenburg, W. Didimo, W. Evans, P. Kindermann,
G. Liotta, F. Montecchiani
Graph Drawing and Network Visualization
September, 2015.
12 pages.

Alternating Paths and Cycles of Minimum Length
W. Evans, G. Liotta, H. Meijer, S. Wismath
Computational Geometry: Theory and Applications
58:124135, 2016.
(pdf)
from
Graph Drawing and Network Visualization
September, 2015.
(pdf)

Simultaneous Visibility Representations of Plane
stgraphs Using Lshapes
W. Evans, G. Liotta and F. Montecchiani
Workshop on GraphTheoretic Concepts in Computer Science (WG)
accepted May, 2015.
12 pages.
(pdf)

Contact Representations of Graphs in 3D
Md. J. Alam, W. Evans, S. Kobourov, S. Pupyrev,
J. Toeniskoetter, T. Ueckerdt
WADS Algorithms and Data Structures Symposium
Aug. 2015.
12 pages.
(pdf)

On Characterizing Terrain Visibility Graphs
W. Evans and N. Saeedi,
Journal of Computational Geometry
6(1):108141,
2015.
(pdf)

SEFE without Mapping via Large Induced Outerplane Graphs in Plane Graphs
P. Angelini, W. Evans, F. Frati, J. Gudmundsson,
Journal of Graph Theory,
20 pages, online 30 Apr, 2015.
Preliminary version appeared in
24th International Symposium on Algorithms and Computation (ISAAC),
p. 185195,
December 2013.
(pdf)

Bar 1Visibility Graphs and their relation to other Nearly Planar Graphs
W. Evans, M. Kaufmann, W. Lenhart, G. Liotta, T. Mchedlidze, S. Wismath,
Journal of Graph Algorithms and Applications
18(5):721739,
2014.
(pdf),

Column Planarity and Partial Simultaneous Geometric Embedding
W. Evans, V. Kusters, M. Saumell, B. Speckmann
Proceedings of 22nd International Symposium on Graph Drawing (GD)
LNCS, p.~259271,
Sep. 2014.
(pdf)

Query Strategies for Minimizing the Ply of the Potential
Locations of Entities Moving with Different Speeds
W. Evans, D. Kirkpatrick, M. Löffler, F. Staals
30th European Workshop on Computational Geometry (EuroCG)
Mar. 2014.
(pdf)

Graphs admitting drealizers: treedecompositions and
boxrepresentations
W. Evans, S. Felsner, S. Kobourov, T. Ueckerdt
30th European Workshop on Computational Geometry (EuroCG)
Mar. 2014.
(pdf)

Table Cartograms
W. Evans, S. Felsner, M. Kaufmann, S. Kobourov, D. Mondal, R. Nishat,
K. Verbeek,
21st Annual European Symposium on Algorithms (ESA),
September 2013.
(pdf)

On kGuarding Polygons
D. Busto, W. Evans, D. Kirkpatrick,
Proceedings of the 25th Canadian Conference on Computational
Geometry (CCCG),
August 2013.
(pdf)

Competitive Query Strategies for Minimising the Ply of the Potential
Locations of Moving Points
W. Evans, D. Kirkpatrick, M. Löffler, F. Staals,
29th ACM Symposium on Computational Geometry (SoCG),
p. 155165,
June 2013.
(pdf)
 Approximate Proximity Drawings,
W. Evans, E. Gansner, M. Kaufmann, G. Liotta, H. Meijer and
A. Spillner,
Computational Geometry: Theory and Applications,
46(6):604614,
2013.
Preliminary version appeared in
Proceedings of 19th International Symposium on Graph
Drawing,
p. 166178, Sept. 2011.
(pdf)
 On Pointsets that Support Planar Graphs,
V. Dujmović, W. Evans, S. Lazard, W. Lenhart, G. Liotta,
D. Rappaport and S. Wismath,
Computational Geometry: Theory and Applications,
43(1):2950, 2013.
Preliminary version appeared in
Proceedings of 19th International Symposium on Graph
Drawing,
p. 6474, Sept. 2011.
(pdf)

Universal Point Subsets for Planar Graphs
P. Angelini, C. Binucci, W. Evans, F. Hurtado, G. Liotta,
T. Mchedlidze, H. Meijer, Y. Okamoto,
23rd International Symposium on Algorithms and Computation
(ISAAC),
p. 423432,
Dec. 2012.
(pdf)
 On Representing Graphs by Touching Cuboids
D. Bremner, W. Evans, F. Frati, L. Heyer, S. Kobourov,
W. Lenhart, G. Liotta, D. Rappaport and S. Whitesides,
Proceedings of 20th International Symposium on Graph
Drawing,
p. 187198,
Sept. 2012.
(pdf)
 The Possible Hull of Imprecise Points,
W. Evans and J. Sember,
Proceedings of the 23rd Canadian Conference on Computational
Geometry (CCCG),
p. 479484, August 2011.
(pdf)
 On Graphs Supported by Line Sets,
V. Dujmović, W. Evans, S. Kobourov, G. Liotta, C. Weibel,
and S. Wismath,
Proceedings of 18th International Symposium on Graph
Drawing,
p. 177182, Sept. 2010.
(pdf)
 Multiguard Covers for Polygonal Regions,
Z. Jabbari, W. Evans and D. Kirkpatrick,
Proceedings of the 22nd Canadian Conference on Computational
Geometry (CCCG),
p. 58, August 2010.
(pdf)
 kStarShaped Polygons,
W. Evans and J. Sember,
Proceedings of the 22nd Canadian Conference on Computational
Geometry (CCCG),
p. 215218, August 2010.
(pdf)
 Clone Detection via Structural Abstraction,
W. Evans, F. Ma, and C. W. Fraser,
Software Quality Journal,
17(4):309330, 2009.
Invited submission from
Fourteenth Working Conference on Reverse Engineering (WCRE),
p. 150159, October, 2007.
(pdf)
 Guaranteed Voronoi Diagrams of Uncertain Sites,
J. Sember and W. Evans,
Proceedings of the 20th Canadian Conference on Computational
Geometry (CCCG),
p. 207210, August 2008.
(pdf)
 Optimistic and Pessimistic Shortest Paths on Uncertain
Terrains,
Y. Kholondyrev and W. Evans,
Proceedings of the 19th Canadian Conference on Computational
Geometry (CCCG),
p. 197200, August 2007.
(pdf)
 PursuitEvasion Voronoi Diagrams in ℓ_{1},
W. Cheung and W. Evans,
Proceedings of the 4th International Symposium on Voronoi
Diagrams in Science and Engineering,
p. 5865, July 2007.
(pdf)
 Bar kVisibility Graphs,
A. Dean, W. Evans, E. Gethner, J. Laison, M. Safari, and
W. Trotter,
Journal of Graph Algorithms and Applications,
11(1):4559, 2007.
Preliminary version appeared as
Bar kVisibility Graphs: Bounds on the Number of
Edges, Chromatic Number, and Thickness,
Proceedings of 13th International Symposium on Graph
Drawing, Sept. 2005,
volume 3843 of LNCS,
p. 7382, 2006.
(pdf)
 Optimally scheduling
videoondemand to minimize delay when server and receiver bandwidth
may differ,
W. Evans and D. Kirkpatrick,
ACM Transactions on Algorithms,
2(4):661678, October 2006.
Invited submission from
14th Annual ACMSIAM Symposium
on Discrete Algorithms (SODA), p. 10341042, 2003.
(gzipped postscript)
(pdf)
 On the spanning ratio of Gabriel graphs and Betaskeletons,
P. Bose, L. Devroye, W. Evans, and D. Kirkpatrick,
SIAM Journal on Discrete Mathematics,
20(2):412427, 2006.
Preliminary version appeared in
Proceedings of the Fifth Latin American Symposium on Theoretical
Informatics (LATIN), volume 2286 of LNCS,
p. 479493, April 2002.
(gzipped postscript)
(pdf)
 Computing the set of all the distant horizons of a terrain,
D. Archambault, W. Evans, and D. Kirkpatrick,
International Journal of Computational Geometry
& Applications,
15(6):547563, December 2005.
Invited submission from
Proceedings of the 16th Canadian Conference on Computational
Geometry (CCCG),
p. 7679, August 2004.
(pdf)
 Directed OneTrees,
W. Evans, M. Safari,
Proceedings 2005 European Conference on Combinatorics, Graph
Theory and Applications (EuroComb '05), p. 6772, 2005.
(pdf)
 Voilà: Delivering Messages Across Partitioned AdHoc
Networks,
R. Shah, N. Hutchinson, W. Evans,
Proceedings 29th Annual IEEE International Conference on
Local Computer Networks, p. 610617, 2004.
 Optimistic shortest paths on uncertain terrains,
C. Gray and W. Evans.
Proceedings of the 16th Canadian Conference on Computational
Geometry (CCCG),
p. 6871, August 2004.
(pdf)
 Restructuring binary search trees,
W. Evans and D. Kirkpatrick,
Journal of Algorithms,
50(2):168193, February 2004.
Preliminary version appeared in
Proceedings of the Eleventh Annual ACMSIAM Symposium on Discrete
Algorithms (SODA), January 2000.
(gzipped postscript)
(pdf)
 On the maximum tolerable noise of kinput gates for
reliable computation by formulas,
W. Evans and L. Schulman,
IEEE Transactions on Information Theory,
49(11):30943098, November 2003.
(gzipped postscript)
(pdf)
 Predicated instructions for code compaction,
W. Cheung, W. Evans, and J. Moses,
Proceedings of the 7th International Workshop on
Software and Compilers for Embedded Systems (SCOPES),
volume 2826 of Lecture Notes in Computer Science,
SpringerVerlag,
p. 1732, 2003.
 Cold code decompression at runtime,
S. Debray and W. Evans,
Communications of the ACM (special issue on program compaction),
46(8), August 2003, p. 5460.
 Grammarbased compression of interpreted code,
W. Evans and C. W. Fraser,
Communications of the ACM (special issue on program compaction),
46(8), August 2003, p. 6166.
 Predicated instructions for code compaction,
W. Cheung, W. Evans, and J. Moses,
Proceedings of the 7th International Workshop on Software and
Compilers for Embedded Systems (SCOPES), LNCS 2826, p. 1732,
2003.
(gzipped postscript)
(pdf)
 Triangle guarding,
J. Smith and W. Evans,
Proceedings of the 15th Canadian Conference on Computational
Geometry (CCCG), p. 7680, 2003.
(gzipped postscript)
(pdf)
 Diamonds are not a minimum weight triangulation's best
friend,
P. Bose, L. Devroye, and W. Evans,
International Journal of Computational Geometry
and Applications,
12(6), 2002, p. 445453.
Preliminary version appeared as
Univ. of British Columbia Tech. Report 9601, 1996.
(gzipped postscript)
(pdf)
 Profileguided code compression,
S. Debray and W. Evans,
Proceedings SIGPLAN '02 Conference on Programming Language Design and
Implementation (PLDI), p. 95105, 2002.
(gzipped postscript)
(pdf)
 Bytecode compression via profiled grammar rewriting,
W. Evans and C. W. Fraser,
Proceedings SIGPLAN '01 Conference on Programming Language Design and
Implementation (PLDI), 2001.
(gzipped postscript)
(pdf)
(slides from PLDI'01)
 Righttriangulated irregular networks,
W. Evans, D. Kirkpatrick, and G. Townsend,
Algorithmica: Special Issue on Algorithms for Geographical
Information,
30(2), 2001, p. 264286.
Preliminary version appeared as
Right triangular irregular networks,
Univ. of Arizona, Dept. of C.S., Tech. Report 9709, 1997.
(gzipped postscript)
(pdf)
 Compiler techniques for code compaction,
S. Debray, W. Evans, R. Muth, and B. de Sutter,
Transactions on Programming Languages and Systems (TOPLAS),
22(2), 2000, p. 378415.
(gzipped postscript)
(pdf)
Preliminary version appeared as
Compiler techniques for code compression,
S. Debray, W. Evans, and R. Muth,
in Workshop on Compiler Support for System Software (WCSSS),
1999.
(gzipped postscript)
(pdf)
 Efficiently supporting temporal granularities,
C. Dyreson, W. Evans, H. Lin, and R. Snodgrass,
IEEE Transactions on Knowledge and Data Engineering,
12(4), July/August 2000, p. 568587.
(gzipped postscript)
(pdf)
 Broadcasting on trees and the Ising model,
W. Evans, C. Kenyon, Y. Peres, and L. J. Schulman,
Annals of Applied Probability,
10(2), 2000, p. 410433.
(gzipped postscript)
(pdf)
 Signal propagation and noisy circuits,
W. Evans and L. J. Schulman,
IEEE Transactions on Information Theory,
45(7), November 1999, p. 23672373.
(gzipped postscript)
(pdf)
 Recovering lines with fixed linear probes,
M. de Berg, P. Bose, D. Bremner, W. Evans, and Lata Narayanan,
Proceedings of the Tenth Canadian Conference on Computational
Geometry (CCCG), August 1998.
(gzipped postscript)
(pdf)
 Averagecase lower bounds for noisy boolean decision trees,
W. Evans and N. Pippenger,
SIAM Journal of Computation, 28(2), July 1998, p. 433446.
Preliminary version appeared in 28th Symposium on the Theory
of Computation (STOC), 1996.
(gzipped postscript)
(pdf)
 On the maximum tolerable noise for reliable computation by
formulas,
W. Evans and N. Pippenger,
IEEE Transactions on Information Theory, 44(3), May 1998,
p. 12991305.
(gzipped postscript)
(pdf)
 Compression via guided parsing,
W. Evans,
Proceedings of the 1998 Data Compression Conference (poster
session), March 1998.
(gzipped postscript)
(pdf)
 A glossary of time granularity concepts,
C. Bettini, C. E. Dyreson, W. Evans, R. T. Snodgrass, and X. S. Wang,
in Temporal Databases: Research and Practice,
O. Etzion, S. Jajodia, and S. Sripada (eds.), Springer, p. 406413,
1998.
 Code compression,
J. Ernst, W. Evans, C. W. Fraser, S. Lucco, and T. Proebsting,
Proceedings SIGPLAN '97 Conference on Programming Language Design and
Implementation (PLDI), 1997.
(pdf)
 Approximating shortest paths in arrangements of lines,
P. Bose, W. Evans, D. Kirkpatrick, M. McAllister, and J. Snoeyink,
Proceedings of the Eighth Canadian Conference on Computational
Geometry (CCCG), 1996.
(pdf)
 Regular polygons are most tolerant,
W. Evans,
Proceedings of the Seventh Canadian Conference on Computational
Geometry (CCCG), 1995.
(gzipped postscript)
(pdf)
 Information Theory and Noisy Computation,
W. Evans,
PhD Thesis, University of California at Berkeley, 1994.
(gzipped postscript)
(pdf)
 Signal propagation, with application to a lower bound
on the depth of noisy formulas,
W. Evans and L. J. Schulman,
34th Symposium on Foundations of Computer Science (FOCS), 1993.
(gzipped postscript)
(pdf)
 Choosing a reliable hypothesis,
W. Evans, S. Rajagopalan, and U. Vazirani,
Proceedings of the 6th Workshop on Computational Learning
Theory (COLT), 1993.
(gzipped postscript)
(pdf)
 Checking the correctness of memories,
M. Blum, W. Evans, P. Gemmell, S. Kannan, and M. Naor,
Algorithmica 12, 1994, p. 225244.
Extended abstract appeared in
32nd Symposium on Foundations of Computer Science (FOCS),
1991.
(gzipped postscript)
(pdf)
 Parallel random number generation,
W. Evans and B. Sugla,
Proceedings of the Fourth Conference on Hypercubes, Concurrent
Computers and Applications, 1989.