Will Evans's Papers

Representing Graphs and Hypergraphs by Touching Polygons in 3D
W. Evans, P. Rzążewski, N. Saeedi, C. Shin, A. Wolff
Proc. 27th Graph Drawing and Network Visualization
September, 2019.

Minimizing Interference Potential Among Moving Entities
D. Busto, W. Evans, D. Kirkpatrick
Proc. 30th ACMSIAM Symposium on Discrete Algorithms (SODA)
p. 24002418, January, 2019.
(paper)
(extended talk)

Visibility Representations of Boxes in 2.5 Dimensions
A. Arleo, C. Binucci, E. Di Giacomo, W. Evans, L. Grilli, G. Liotta,
H. Meijer, F. Montecchiani, S. Whitesides, S. Wismath
Computational Geometry: Theory and Applications
72:1933, 2018
from
Proc. 24th Graph Drawing and Network Visualization
LNCS p.251265, September 2016.
(arxiv pdf)

Table Cartogram
W. Evans, S. Felsner, M. Kaufmann, S. Kobourov, D. Mondal, R. Nishat,
K. Verbeek
Computational Geometry: Theory and Applications (Special Issue in Memory of
Ferran Hurtado)
68(Supplement C):174185, 2018.
(pdf)
Invited submission from ESA 2013.
(pdf)

New Results on Edge Partitions of 1plane Graphs
E. Di Giacomo, W. Didimo, W. Evans, G. Liotta, H. Meijer,
F. Montecchiani, S. Wismath
Theoretical Computer Science
713:7884,2018.
(arxiv pdf)

Column planarity and partiallysimultaneous geometric embedding
L. Barba, W. Evans, M. Hoffmann, V. Kusters, M. Saumell, B. Speckmann
Journal of Graph Algorithms and Applications
21(6):9831002, 2017.
(pdf)

Orthopolygon Visibility Representations of Embedded Graphs
E. Di Giacomo, W. Didimo, W. Evans, G. Liotta, H. Meijer,
F. Montecchiani, S. Wismath
Algorithmica
80:23452383, 2018
from
Proc. 24th Graph Drawing and Network Visualization
LNCS p.280294, September 2016.
(arxiv pdf)

Covering Points with Convex Sets of Minimum Size
S.W. Bae, H. Cho, W. Evans, N. Saeedi, C. Shin
Theoretical Computer Science
718:1423, 2018.
(paper)
from
Covering Points with Convex Sets of Minimum Size
H. Cho, W. Evans, N. Saeedi, C. Shin
WALCOM: Algorithms and Computation
LNCS, p. 166178, March, 2016.
(paper)

Minimizing Colocation Potential of Moving Entities
W. Evans, D. Kirkpatrick, M. Löffler, F. Staals
SIAM Journal on Computing
45(5):18701893, 2016.
(paper)

Minimum Rectilinear Polygons for Given Angle Sequences
W. Evans, K. Fleszar, P. Kindermann, N. Saeedi, C. Shin, A. Wolff
Proc. 18th Japan Conference on Discrete and
Computational Geometry and Graphs (JCDCG^{2} 2015)
LNCS 9943, p. 105119, May, 2016.
(arxiv pdf)

Recognizing a DOG is Hard but not when it is Thin and Unit
W. Evans, M. van Garderen, M. Löffler, V. Polishchuk
Proc. 8th International Conference on Fun with Algorithms
LIPICS 49, 16:112, June, 2016.
(pdf)

Recognizing and Drawing ICplanar Graphs
F. Brandenburg, W. Didimo, W. Evans, P. Kindermann,
G. Liotta, F. Montecchiani
Proc. 23rd Graph Drawing and Network Visualization
LNCS, p. 295308, September, 2015.
(arxiv pdf)

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
Theoretical Computer Science
645:100111, 2016.
(pdf)
from
Workshop on GraphTheoretic Concepts in Computer Science (WG)
LNCS, p. 252265, June, 2015.
(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
from
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
Proc. 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)

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
from
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
from
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
from
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.
(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
from
Proceedings of the Fifth Latin American Symposium on Theoretical
Informatics (LATIN), volume 2286 of LNCS,
p. 479493, April 2002.
(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
from
Proceedings of the Eleventh Annual ACMSIAM Symposium on Discrete
Algorithms (SODA), January 2000.
(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.
(pdf)
 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.
(pdf)
 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.
(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), LNCS 2826, p. 1732,
2003.
(pdf)
 Triangle guarding,
J. Smith and W. Evans,
Proceedings of the 15th Canadian Conference on Computational
Geometry (CCCG), p. 7680, 2003.
(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
from
Univ. of British Columbia Tech. Report 9601, 1996.
(pdf)
 Profileguided code compression,
S. Debray and W. Evans,
Proceedings SIGPLAN '02 Conference on Programming Language Design and
Implementation (PLDI), p. 95105, 2002.
(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.
(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
from
Right triangular irregular networks,
Univ. of Arizona, Dept. of C.S., Tech. Report 9709, 1997.
(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.
(pdf)
from
Compiler techniques for code compression,
S. Debray, W. Evans, and R. Muth,
in Workshop on Compiler Support for System Software (WCSSS),
1999.
(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.
(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.
(pdf)
 Signal propagation and noisy circuits,
W. Evans and L. J. Schulman,
IEEE Transactions on Information Theory,
45(7), November 1999, p. 23672373.
(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.
(pdf)
 Averagecase lower bounds for noisy boolean decision trees,
W. Evans and N. Pippenger,
SIAM Journal of Computation, 28(2), July 1998, p. 433446.
from
28th Symposium on the Theory of Computation (STOC), 1996.
(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.
(pdf)
 Compression via guided parsing,
W. Evans,
Proceedings of the 1998 Data Compression Conference (poster
session), March 1998.
(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.
(pdf)
 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.
(pdf)
 Information Theory and Noisy Computation,
W. Evans,
PhD Thesis, University of California at Berkeley, 1994.
(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.
(pdf)
 Choosing a reliable hypothesis,
W. Evans, S. Rajagopalan, and U. Vazirani,
Proceedings of the 6th Workshop on Computational Learning
Theory (COLT), 1993.
(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.
(pdf)
 Parallel random number generation,
W. Evans and B. Sugla,
Proceedings of the Fourth Conference on Hypercubes, Concurrent
Computers and Applications, 1989.