Google Scholar Page

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 ACM-SIAM Symposium on Discrete Algorithms (SODA) p. 2400-2418, 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:19-33, 2018 from Proc. 24th Graph Drawing and Network Visualization LNCS p.251-265, 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):174-185, 2018.
  (pdf)
  Invited submission from ESA 2013.
  (pdf)

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

• Column planarity and partially-simultaneous geometric embedding L. Barba, W. Evans, M. Hoffmann, V. Kusters, M. Saumell, B. Speckmann Journal of Graph Algorithms and Applications 21(6):983-1002, 2017.
  (pdf)

• Ortho-polygon Visibility Representations of Embedded Graphs E. Di Giacomo, W. Didimo, W. Evans, G. Liotta, H. Meijer, F. Montecchiani, S. Wismath Algorithmica 80:2345-2383, 2018 from Proc. 24th Graph Drawing and Network Visualization LNCS p.280-294, 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:14-23, 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. 166-178, March, 2016.
  (paper)

• Minimizing Co-location Potential of Moving Entities W. Evans, D. Kirkpatrick, M. Löffler, F. Staals SIAM Journal on Computing 45(5):1870-1893, 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² 2015) LNCS 9943, p. 105-119, 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:1-12, June, 2016.
  (pdf)

• Recognizing and Drawing IC-planar Graphs F. Brandenburg, W. Didimo, W. Evans, P. Kindermann, G. Liotta, F. Montecchiani Proc. 23rd Graph Drawing and Network Visualization LNCS, p. 295-308, 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:124--135, 2016.
  (pdf)
  from Graph Drawing and Network Visualization September, 2015.
  (pdf)

• Simultaneous Visibility Representations of Plane st-graphs Using L-shapes W. Evans, G. Liotta and F. Montecchiani Theoretical Computer Science 645:100-111, 2016.
  (pdf)
  from Workshop on Graph-Theoretic Concepts in Computer Science (WG) LNCS, p. 252-265, 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):108--141, 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. 185-195, December 2013.
  (pdf)

• Bar 1-Visibility 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):721--739, 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.~259-271, 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 d-realizers: tree-decompositions and box-representations W. Evans, S. Felsner, S. Kobourov, T. Ueckerdt 30th European Workshop on Computational Geometry (EuroCG) Mar. 2014.
  (pdf)

• On k-Guarding 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. 155-165, 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):604-614, 2013 from Proceedings of 19th International Symposium on Graph Drawing, p. 166-178, Sept. 2011.
  (pdf)

• On Point-sets 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):29-50, 2013 from Proceedings of 19th International Symposium on Graph Drawing, p. 64-74, 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. 423-432, 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. 187-198, 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. 479-484, 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. 177-182, Sept. 2010.
  (pdf)

• Multi-guard Covers for Polygonal Regions, Z. Jabbari, W. Evans and D. Kirkpatrick, Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG), p. 5-8, August 2010.
  (pdf)

• k-Star-Shaped Polygons, W. Evans and J. Sember, Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG), p. 215-218, August 2010.
  (pdf)

• Clone Detection via Structural Abstraction, W. Evans, F. Ma, and C. W. Fraser, Software Quality Journal, 17(4):309-330, 2009. Invited submission from Fourteenth Working Conference on Reverse Engineering (WCRE), p. 150-159, 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. 207-210, 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. 197-200, August 2007.
  (pdf)

• Pursuit-Evasion Voronoi Diagrams in ℓ₁, W. Cheung and W. Evans, Proceedings of the 4th International Symposium on Voronoi Diagrams in Science and Engineering, p. 58-65, July 2007.
  (pdf)

• Bar k-Visibility Graphs, A. Dean, W. Evans, E. Gethner, J. Laison, M. Safari, and W. Trotter, Journal of Graph Algorithms and Applications, 11(1):45-59, 2007 from Bar k-Visibility 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. 73-82, 2006.
  (pdf)

• Optimally scheduling video-on-demand to minimize delay when server and receiver bandwidth may differ, W. Evans and D. Kirkpatrick, ACM Transactions on Algorithms, 2(4):661-678, October 2006. Invited submission from 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), p. 1034-1042, 2003.
  (pdf)

• On the spanning ratio of Gabriel graphs and Beta-skeletons, P. Bose, L. Devroye, W. Evans, and D. Kirkpatrick, SIAM Journal on Discrete Mathematics, 20(2):412-427, 2006 from Proceedings of the Fifth Latin American Symposium on Theoretical Informatics (LATIN), volume 2286 of LNCS, p. 479-493, 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):547-563, December 2005. Invited submission from Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG), p. 76-79, August 2004.
  (pdf)

• Directed One-Trees, W. Evans, M. Safari, Proceedings 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), p. 67-72, 2005.
  (pdf)

• Voilà: Delivering Messages Across Partitioned Ad-Hoc Networks, R. Shah, N. Hutchinson, W. Evans, Proceedings 29th Annual IEEE International Conference on Local Computer Networks, p. 610-617, 2004.

• Optimistic shortest paths on uncertain terrains, C. Gray and W. Evans. Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG), p. 68-71, August 2004.
  (pdf)

• Restructuring binary search trees, W. Evans and D. Kirkpatrick, Journal of Algorithms, 50(2):168-193, February 2004 from Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), January 2000.
  (pdf)

• On the maximum tolerable noise of k-input gates for reliable computation by formulas, W. Evans and L. Schulman, IEEE Transactions on Information Theory, 49(11):3094-3098, 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. 54-60.
  (pdf)

• Grammar-based compression of interpreted code, W. Evans and C. W. Fraser, Communications of the ACM (special issue on program compaction), 46(8), August 2003, p. 61-66.
  (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. 17-32, 2003.
  (pdf)

• Triangle guarding, J. Smith and W. Evans, Proceedings of the 15th Canadian Conference on Computational Geometry (CCCG), p. 76-80, 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. 445-453 from Univ. of British Columbia Tech. Report 96-01, 1996.
  (pdf)

• Profile-guided code compression, S. Debray and W. Evans, Proceedings SIGPLAN '02 Conference on Programming Language Design and Implementation (PLDI), p. 95-105, 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)

• Right-triangulated irregular networks, W. Evans, D. Kirkpatrick, and G. Townsend, Algorithmica: Special Issue on Algorithms for Geographical Information, 30(2), 2001, p. 264-286 from Right triangular irregular networks, Univ. of Arizona, Dept. of C.S., Tech. Report 97-09, 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. 378-415.
  (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. 568-587.
  (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. 410-433.
  (pdf)

• Signal propagation and noisy circuits, W. Evans and L. J. Schulman, IEEE Transactions on Information Theory, 45(7), November 1999, p. 2367-2373.
  (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)

• Average-case lower bounds for noisy boolean decision trees, W. Evans and N. Pippenger, SIAM Journal of Computation, 28(2), July 1998, p. 433-446. 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. 1299-1305.
  (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. 406-413, 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. 225-244. 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.