Anna Lubiw's Research

Papers are grouped by topic: Computational Geometry, Graph Drawing, Graph Algorithms, Music Information Retrieval, Folding and Unfolding, Combinatorial Optimization, Others.

Computational Geometry

• Shortest descending paths through given faces,
  with Mustaq Ahmed,
  Computational Geometry Theory and Applications 42 (5) 2009, 464-470
  also 18th Canadian Conference on Computational Geometry, 2006. pdf

• Morphing polyhedra with parallel faces: Counterexamples,
  T. Biedl, M. Spriggs,
  Computational Geometry: Theory and Applications 42 (5), 2009, 395-402.
  also 17th Canadian Conference on Computational Geometry, 2005. ps file

• Approximation Algorithms for Shortest Descending Paths in Terrains,
  with Mustaq Ahmed, S. Das, S. Lodha, A. Maheshwari, S. Roy,
  accepted to Journal of Discrete Algorithms, 2009.
  also (in part) Third Annual Workshop on Algorithms and Computation (WALCOM), 2009. pdf

• A lower bound on the area of a 3-coloured disc packing, arXiv
  with Peter Brass, Ferran Hurtado, Ben Lafreniere
  accepted to International Journal on Computational Geometry, 2008, 19 pages.
  also 19th Canadian Conference on Computational Geometry (CCCG) 2007, 101--104.
  

• Shortest Anisotropic Paths with Few Bends is NP-complete,
  with Mustaq Ahmed,
  18th Fall Workshop on Computational Geometry, Rensselaer Polytechnic Institute, 2008.
  

• The Steiner Ratio for Obstacle-Avoiding Steiner Trees,
  with Mina Razaghpour,
  20th Canadian Conference on Computational Geometry (CCCG) 2008.

• Modelling Gateway Placement in Wireless Networks: Geometric k-Centres of Unit Disc Graphs,
  with S. Durocher, K.R. Jampani, L. Narayanan,
  Proceedings of the Fifth ACM SIGACT-SIGOPS International Workshop on Foundations of Mobile Computing (DIAL M-POMC) 2008, ACM, 79-86, 2008.

• Equiprojective polyhedra,
  with M. Hasan,
  Computational Geometry Theory and Applications 40 (2), 148-155, 2008.
  also 15th Canadian Conference on Computational Geometry, 2003, 47-50.
  pdf of slides

• Properties of shortest descending paths,
  with Mustaq Ahmed,
  17th Annual Fall Workshop on Computational and Combinatorial Geometry, IBM T.J. Watson Research Center, November 2007.
  

• Optimal schedules for 2-guard room search,
  with Stephen Bahun,
  19th Canadian Conference on Computational Geometry (CCCG) 2007, 245-248.
  

• Cauchy's theorem and edge lengths of convex polyhedra, pdf
  with T. Biedl, M. Spriggs,
  Workshop on Algorithms and Data Structures (WADS) 2007, Lecture Notes in Computer Science 4619, F. Dehne, J-R. Sack and N. Zeh, eds., 2007, 398--409.
  

• Computing homotopic shortest paths efficiently,
  with A. Efrat, S. Kobourov,
  Computational Geometry: Theory and Applications, 35 (3) 2006, 162-172.
  10th Annual European Symposium on Algorithms, Algorithms - ESA 2002, R. Moehring, R. Raman, eds., Lecture Notes in Computer Science 2461, 2002, 411-423.
  ps file

• Angles and lengths in reconfigurations of polygons and polyhedra,
  with T. Biedl, M. Spriggs,
  Lecture Notes in Computer Science, Volume 3153, Mathematical Foundations of Computer Science 2004: 29th International Symposium, (MFCS), 2004, 748 - 759.
  ps file

• Parallel morphing of trees and cycles,
  with T. Biedl, M. Spriggs,
  15th Canadian Conference on Computational Geometry, 2003, 29-32.
  ps file

• Touring a sequence of polygons,
  with M. Dror, A. Efrat, J. Mitchell,
  Symposium on Theory of Computing (STOC), 2003, 473 -- 482.
  ps file, pdf of slides

• Efficient visibility queries in simple polygons,
  with P. Bose, J.I. Munro,
  Computational Geometry Theory and Applications, Volume 23, Issue 3, 2002, 313-335.

• The floodlight problem,
  with P. Bose, L. Guibas, M. Overmars, D. Souvaine, J. Urrutia,
  International J. of Computational Geometry and Applications 7, 1997, 153-163.

• Decomposing polygonal regions into convex quadrilaterals,
  Proc. ACM Symp. on Computational Geometry, 1985, 97-106.

Graph Drawing

• Morphing Planar Graph Drawings with Bent Edges,
  with M. Petrick,
  Topological and Geometric Graph Theory, 2008.
  Electronic Notes in Discrete Mathematics 31, 2008, 45-48.
  doi:10.1016/j.endm.2008.06.007i, pdf video of talk

• On simultaneous planar graph embeddings,
  with P. Brass, E. Cenek, C.A. Duncan, A. Efrat, D. Ismailescu, S. Kobourov, and J. Mitchell,
  Computational Geometry Theory and Applications, Volume 36, Issue 2, 2007, 117-130.
  Proc. 8th Workshop on Algorithms and Data Structures ( WADS 2003),
  Lecture Notes in Computer Science 2748, Dehne, Sack, Smid, eds., Springer-Verlag, 2003, pp. 243-255.
  ps file

• Morphing orthogonal planar graph drawings,
  with M. Petrick, M. Spriggs,
  Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) 2006, 222--230.

• Morphing planar graphs while preserving edge directions,
  with T. Biedl, M. Spriggs,
  Proceedings Graph Drawing 2005, Lecture Notes in Computer Science 3843, P. Healy, N. Nikolov, eds., 2006, 13--24.

• Embedding problems for paths with direction constrained edges,
  with G. Di Battista, G. Liotta, S. Whitesides,
  Theoretical Computer Science, Volume 289, Issue 2, 2002, 897-917.
  The Sixth Annual International Computing and Combinatorics Conference, COCOON'2000, Lecture Notes in Computer Science 1858, ed. D.Z. Du, P. Eades, V. Estivill-Castro, X. Lin, A. Sharma, Springer 2000, 64-.
  version from Springer

• Orthogonal drawings of cycles in 3D space,
  with G. Di Battista, G. Liotta, S. Whitesides,
  Graph Drawing 2000, Lecture Notes in Computer Science 1984, ed. Joe Marks, Springer 2001,
  

• Elastic labels around the perimeter of a map,
  with Claudia Iturriaga
  Journal of Algorithms, 47, 2003 14-39.
  Workshop on Algorithms and Data Structures, WADS'99, Lecture Notes in Computer Science 1663, ed. F. Dehne, A. Gupta, J.-R. Sack, R. Tamassia, Springer-Verlag, 1999, 306-317.
  

• Elastic labels: the two-axis case,
  with Claudia Iturriaga
  Graph Drawing 1997, Lecture Notes in Computer Science 1353, ed. G. DiBattista, Springer-Verlag, 1997, 181-192.
  ps file;
  This was a preliminary version of the paper listed above.

• NP-hardness of some map labeling problems,
  with Claudia Iturriaga
  Technical Report CS-97-18, University of Waterloo, Canada, 1997. from citeseer

• A visibility representation for graphs in three dimensions,
  with P. Bose, H. Everett, S. Fekete, M. Houle, H. Meijer, K. Romanik, G. Rote, T. Shermer, S. Whitesides, C. Zelle.
  Journal of Graph Algorithms and Applications 2, no. 3, 1998, 1-16.

• The rectangle of influence drawability problem,
  with G. Liotta, H. Meijer, S. Whitesides,
  Computational Geometry Theory and Applications 10, 1998, 1-22.

• Recognizing rectangle of influence drawable graphs, with H. ElGindy, G. Liotta, H. Meijer, S. Whitesides,
  Graph Drawing 1994, ed.~R. Tamassia and I. Tollis, Lecture Notes in Computer Science 894, Springer-Verlag, 1995, 352-363.
  See the related paper above.

• Visibility graphs of towers,
  with P. Colley, J. Spinrad
  Computational Geometry Theory and Applications 7, 1997, 161-172.

• Upward planar drawing of single source acyclic graphs,
  with M. Hutton,
  SIAM J. on Computing 25, 1996, 291-311.
  

• Interval graphs as visibility graphs of simple polygons, Part I: parachutes,
  with N. Mouawad,
  Sixth Canadian Conference on Computational Geometry, University of Saskatchewan, 1994, 18-23.

• Recovery of convex hulls from external visibility graphs,
  with H. Everett, J. O'Rourke,
  Proc. Fifth Canadian Conference on Computational Geometry, University of Waterloo, 1993, 309-314.

• Maximal outerplanar graphs are relative neighbourhood graphs,
  with N. Sleumer,
  Proc. Fifth Canadian Conference on Computational Geometry, University of Waterloo, 1993, 198-203.
  

• Distance visibility graphs,
  with C. Coullard,
  International J. of Computational Geometry and Applications 2, 1992, 349-362.
  

• Non-crossing subgraphs in topological layouts,
  with J. Kratochvil, J. Nesetril,
  SIAM J. of Discrete Math 4, 1991, 223-244.
  

Graph Algorithms

• Shortest Paths Avoiding Forbidden Subpaths,
  with Mustaq Ahmed,
  accepted to 26th International Symposium on Theoretical Aspects of Computer Science (STACS), 2009.

• Efficient algorithms for Petersen's matching theorem,
  with T. Biedl, P. Bose, E. Demaine,
  Journal of Algorithms, 38, 2001, 110-134. Special issue of selected papers from the 10th Annual ACM-SIAM Symposium on Discrete Algorithms.
  Tenth ACM-SIAM Symp. on Discrete Algorithms, 1999, .
  ps file;

• Dominating cliques in chordal graphs,
  with D. Kratsch, P. Damaschke,
  Discrete Mathematics 128, 1994, 269-275.

• Some NP-complete problems similar to graph isomorphism,
  SIAM J. on Computing 10, 1981, 11-21.
  

Music Information Retrieval

• Pattern matching in polyphonic music as a weighted geometric translation problem,
  with L. Tanur,
  Proceedings 5th International Conference on Music Information Retrieval (ISMIR), 2004, 289-296.
  ps file, pdf

Folding and Unfolding

• Local Overlaps in Unfoldings of Polyhedra
  with Brendan Lucier, 15th Annual Fall Workshop on Computational Geometry and Visualization, University of Pennsylvania, November, 2005.

• When can a net fold to a polyhedron?
  with T. Biedl, J. Sun,
  Computational Geometry Theory and Applications, 31 (3), 2005, 207-218.
  Eleventh Canadian Conference on Computational Geometry, U. British Columbia, 1999, 1-4.
  pdf

• Enumerating foldings and unfoldings between polygons and polytopes,
  with E. Demaine, M. Demaine, J. O'Rourke,
  Graphs and Combinatorics 18, 2002, 93--104
  Proceedings of the Japan Conference on Discrete and Computational Geometry, Tokyo, Nov. 2000, 9-12.
  ps file; arXiv
  See also the longer technical report below.

• Examples, counterexamples, and enumeration results for foldings and unfoldings between polygons and polytopes,
  with E. Demaine, M. Demaine, J. O'Rourke,
  Smith Tech. Rep. 069, July 2000.
  ps file; arXiv

• A Note on Reconfiguring Tree Linkages: Trees can Lock,
  with T. Biedl, E. Demaine, M. Demaine, S. Lazard, J. O'Rourke, S. Robbins, I. Streinu, G. Toussaint, S. Whitesides,
  Discrete Applied Mathematics, 117, 2002, 293-297,
  Tenth Canadian Conference on Computational Geometry, McGill University, 1998.
  ps file; a longer version from arXiv;

• Locked and unlocked polygonal chains in 3D,
  with T. Biedl, E. Demaine, M. Demaine, S. Lazard, J. O'Rourke, M. Overmars, S. Robbins, I. Streinu, G. Toussaint, S. Whitesides,
  Discrete and Computational Geometry 26, 2001, 283-287.
  Tenth ACM-SIAM Symp. on Discrete Algorithms, 1999, 866-867.
  ps file; arXiv;

• Folding and one straight cut suffice,
  with E. Demaine, M. Demaine,
  Tenth ACM-SIAM Symp. on Discrete Algorithms, 1999, 891-892.
  ps file See also the longer related paper below.

• Folding and cutting paper,
  with E. Demaine, M. Demaine,
  Revised Papers from the Japan Conf. on Discrete and Computational Geometry , edited by J. Akiyama, M. Kano, and M. Urabe, Lecture Notes in Computer Science, Vol. 1763, 1998, 104-117.
  ps file; Erik Demaine's web page on fold-and-cut

• Metamorphosis of the cube,
  with E. Demaine, M. Demaine, J. O'Rourke, I. Pashchenko.
  in 8th Annual Video Review of Computational Geometry, Proc. of the 15th Annual ACM Symposium on Computational Geometry, 1999, 409-410.
  ps file of text in conference proceedings; Erik Demaine's web page on this topic, where you can see the video

• Unfolding some classes of orthogonal polyhedra,
  with T. Biedl, E. Demaine, M. Demaine, J. O'Rourke, M. Overmars, S. Robbins, S. Whitesides,
  Tenth Canadian Conference on Computational Geometry, McGill University, 1998.
  ps file;

• Hiding disks in folded polygons,
  with T. Biedl, E. Demaine, M. Demaine, G. Toussaint,
  Tenth Canadian Conference on Computational Geometry, McGill University, 1998.
  ps file

• When can a polygon fold to a polytope?,
  with J. O'Rourke,
  Technical Report 048, Dept. Comput. Sci., Smith College, June 1996.
  ps file;

Combinatorial Optimization

• A weighted min-max relation for intervals,
  J. Combinatorial Theory B 53, 1991, 151-172.
  

• Short-chorded and perfect graphs,
  J. Combinatorial Theory B 51, 1991, 24-33.
  

• The Boolean basis problem and how to cover some polygons by rectangles,
  SIAM J. on Discrete Math. 3, 1990, 98-115.
  

• A note on odd/even cycles,
  Discrete Applied Math. 22, 1988/89, 87-92.

• Doubly lexical orderings of matrices,
  SIAM J. on Computing 16, 1987, 854-879.
  

• Orderings and Some Combinatorial Optimization Problems with Geometric Applications,
  Ph.D. thesis, Department of Computer Science, University of Toronto, 1986.
  

Others

• Pattern matching for permutations,
  with P. Bose, J. Buss,
  Information Processing Letters 65, 1998, 277-283.
  

• Convergents of folded continued fractions,
  with J.-P. Allouche, M. Mendes France, A. van der Poorten, J. Shallit,
  Acta Arithmetica 77, 1996, 77-96.

• A lower bound for the integer element distinctness problem,
  with A. Racz,
  Information and Computation 94, 1991, 83-92.

• Counterexample to a conjecture of Symanski on hypercube routing,
  Information Processing Letters 35, 1990, 57-61.
  doi: 10.1016/0020-0190(90)90106-8