next up previous
Next: About this document ...

Curriculum Vitae



SUE HAYS WHITESIDES


Professor

School of Computer Science, McGill University



birthdate and place: May 26, 1946; Glen Cove NY, USA
citizenship: US citizen, landed immigrant in Canada
  SIN: 264 638 347 SSN: 228-60-5376



address: 3480 University St. #318
  Montreal, Quebec H3A 2A7 CANADA
email: sue@cs.mcgill.ca
web page: http://www.cs.mcgill.ca/~sue
telephone: +1 514-398-7071 (CS Office) +1-514-398-7080 (my office)
fax: +1 514-398-3883




EDUCATION
   
M.Sc. 1969 Electrical Engineering (combined undergraduate-M.Sc. program)
  Stanford University
Ph.D. 1975 Mathematics (thesis advisor Richard H. Bruck)
  ``Collineations of Projective Planes of Order 10''
  University of Wisconsin



ACADEMIC EXPERIENCE
   
1983 - Associate Professor, Computer Science, McGill University
1994-95 Visiting Researcher
  Institut National de Recherche en Informatique et en Automatique
  I.N.R.I.A.-Sophia Antipolis, France
1987-88 Visiting Associate Professor, Department of Computer Science
  University of Toronto
1981-82 Visiting Assistant Professor, Department of Computer Science
  Cornell University NY, USA
1977-83 Assistant Professor (Associate Professor 1983)
  Department of Mathematics, Dartmouth College NH, USA
1975-77 Assistant Professor, Mathematics Department
  Tufts University MA, USA

Summary1 of Courses Taught



McGill Courses

189-240 Mathematics for Computer Science
308-360 Algorithms
308-426 Automated Reasoning
308-506 Advanced Analysis of Algorithms
308-560 Graph Algorithms
308-531 Theory of Computation
308-648 Motion Planning
308-761 Topics: Fundamentals of Geometric Reasoning
308-761 Topics: Graph Drawing



Dartmouth (USA):

Calculus at various levels
Statistics for Social Science
Multivariable Calculus
Introduction to Computing
Discrete Probability
Combinatorics
Fourier Series and Partial Differential Equations
Linear Algebra
Modern Algebra for honors students
Linear Programming
Combinatorics for graduate students
Directed Reading for graduate students



Tufts University (USA):

Calculus
Linear Algebra
Combinatorics
Algorithms and Data Structures

Summary2 of Postgraduate Student Supervision



Postdoctoral Fellows

David Wood 2001-
Therese Biedl 1997-99
Sylvain Lazard 1996-98
Kathleen Romaniki 1992-94
Mark van Kreveld 1992-93
Hazel Everett 1989-91



Ph.D. students

Danielle Azar current
Steve Robbins current
Matthew Suderman current
Vida Dujmovíc current
Naixun Pei Ph.D. 1996
Paul Kruszewski Ph.D. 1996
Rongyao Zhao Ph.D. 1990
Michael Karasick Ph.D. 1989
William Lenhart Ph.D. 1982
E. Randy Shull Ph.D. 1980



M.Sc. Students

Matthew Kitching current
Vida Dujmovíc M.Sc. 2000
Constantin Siourbas M.Sc. 2000
François Labelle M.Sc. 1999
Mary Iarocci M.Sc. 1995
Luise Sander M.Sc. 1990
Jean-François Cloutier M.Sc. 1989
Ingrid Pitchen M.Sc. 1987
André Courtemanche M.Sc. 1987
Yuen Hsu M.Sc. 1987
Catherine Langton M.Sc. 1987
Paula Moser M.Sc. 1987
Nadine Ozkan M.Sc. 1987
Rongyao Zhao M.Sc. 1987
Christina Zanfino M.Sc. 1987
Platina Hum M.Sc. 1985
Michael Lee M.Sc. 1984


Refereed Journal Articles

1.
S. T. Brittain, O. J. A. Schueller, H. Wu, S. Whitesides, and G. Whitesides, ``Microorigami: Fabrication of small, three-dimensional, metallic structures'', J. of Physical Chemistry B, vol. 105, no. 2, 2001, pp. 347-350.

2.
H. Wu, S. Britain, J. Andersen, B. Grzybowski, S. Whitesides, and G. Whitesides, ``Fabrication of Topologically Complex Three-Dimensional Microstructures: Metallic Microknots'', J. Am. Chem. Soc., vol. 122, no. 51, 2000, pp. 12691-12699.

3.
P. Eades, A. Symvonis, and S. Whitesides, ``Three-dimensional orthogonal graph drawing algorithms'', Discrete Applied Mathematics, vol. 103, no. 1-3, 15 July 2000, pp. 55-87.

4.
J. Anderson, D. Chiu, C. McDonald, H. Wu, S. Whitesides, and G. Whitesides, ``Fabrication of topologically complex three-dimensional microfluidic systems in PDMS by rapid prototyping'', Analytical Chemistry (American Chemical Society), vol. 72, no. 14, 2000, pp. 3158-3164.

5.
R. Jackman, S. Brittain, A. Adams, H. Wu, M. Prentiss, S. Whitesides and G. Whitesides, ``Three-dimensional metallic microstructures fabricated by soft lithography and microelectrodeposition'', Langmuir (American Chemical Society), vol. 15, 826-836, 1999.

6.
T. Biedl, T. Shermer, S. Whitesides and S. Wismath, ``Orthogonal 3-D Graph Drawing'', J. Graph Algorithms and Applicaions, vol. 3, no. 4, pp. 63-79, 1999. Invited paper for a special issue on highlights of the Fifth Symposium on Graph Drawing (GD '97).

7.
H. Everett, I. Stojmenovic, S. Whitesides and P. Valtr, ``The Largest k-Ball in a d-Dimensional Box'', Computational Geometry, Theory and Applications, vol. 11, 59-67, 1998.

8.
P. Bose, H. Everett, S. Fekete, M. Houle, A. Lubiw, H. Meijer, K. Romanik, G. Rote, T. Shermer, S. Whitesides and C. Zelle, ``A Visibility Representation for Graphs in Three Dimensions'', J. Graph Algorithms and Applications, vol. 2, no. 3, pp. 1-16, 1998.

9.
Paul Kruszewski and Sue Whitesides, ``A General Random Combinatorial Model of Botanical Trees,'' J. Theoretical Biology, vol. 191, pp. 221-236, 1998.

10.
Gregory Dudek, Kathleen Romanik and Sue Whitesides, ``Localizing a Robot with Minimum Travel'', SIAM J. on Computing, vol. 27, no. 2, pp. 583-604, 1998.

11.
H. Alt, M. Godau and S. Whitesides, ``A Universal 3-Dimensional Visibility Representation for Graphs'', invited, refereed paper for Computational Geometry, Theory and Applications, Special Issue on Graph Drawing, R. Tamassia and G. Di Battista, eds., vol. 9, pp. 111-125, 1998.

12.
G. Liotta, A. Lubiw, H. Meijer and S. Whitesides, ``The Rectangle of Influence Drawability Problem,'' Computational Geometry, Theory and Applications, vol. 10, no. 1, pp. 1-22, 1998.

13.
Paul Tanenbaum and Sue Whitesides, ``Simultaneous Dominance Representation of Multiple Posets'', Order, vol. 13, pp. 351-364, 1996.

14.
P. Agarwal, N. Amato, D. Chen, D. Dobkin, R. Drysdale, S. Fortune, M. Goodrich, J. Hershberger, J. O'Rourke, F. Preparata, J. Sack, S. Suri, R. Tamassia, I. Tollis, J. Vitter and S. Whitesides, ``Strategic Directions in Computational Geometry'', ACM Computing Surveys, vol. 28, no. 4, pp. 591-606, 1996.

15.
P. Eades, C. Stirk and S. Whitesides, ``The Techniques of Kolmogorov and Barzdin for Three Dimensional Orthogonal Graph Drawings'', Information Processing Letters, vol. 60, no. 2, Dec. 1996, pp. 97-103.

16.
P. Eades and S. Whitesides, ``The Logic Engine and the Realization Problem for Nearest Neighbor Graphs'', Theoretical Computer Science vol. 169, no. 1, Nov., 1996, pp. 23-37.

17.
P. Eades and S. Whitesides, ``The Realization Problem for Euclidean Minimum Spanning Trees is NP-Hard'', Algorithmica vol. 16, no. 1, July 1996, pp. 60-82.

18.
M. van Kreveld, J. Snoeyink and S. Whitesides, ``Folding Rulers Inside Triangles'', Discrete and Computational Geometry vol. 15, 1996, pp. 265-285.

19.
W. Lenhart and S. Whitesides, ``Reconfiguring Closed Polygonal Chains in Euclidean d-Space'', Discrete and Computational Geometry, vol. 13, 1995, pp. 123-140.

20.
P. Eades and S. Whitesides, ``Drawing Graphs in Two Layers'', Theoretical Computer Science vol. 131, 1994, pp. 361-374.

21.
S. Bellantoni, I. Ben-Arroyo Hartman, T. Przytycka and S. Whitesides, ``Grid Intersection Graphs and Boxicity,'' Discrete Mathematics vol. 114, 1993, pp. 41-49.
22.
Sue Whitesides, ``Algorithmic Issues in the Geometry of Planar Linkage Movement,'' The Australian Computer Journal, invited, refereed contribution to Special Issue on Algorithms, May, 1992, pp. 42-50.

23.
W. Lenhart, R. Pollack, J. Sack, R. Seidel, M. Sharir, S. Suri, G. Toussaint, S. Whitesides, and C.Yap, ``Computing the Link Center of a Simple Polygon'', Discrete and Computational Geometry vol. 3, 1988, pp. 281-293.

24.
Sue Whitesides, ``Computational Geometry and Motion Planning'', invited, refereed chapter of original material not appearing elsewhere, in Computational Geometry, G. Toussaint, ed., Springer-Verlag, 1985, pp. 377-427.

25.
S. H. Whitesides, ``Fixed Point Free Collineations of Order 7 in Projective Planes of Order 9,'' Algebras, Groups and Geometries vol. 2, 1985, pp. 564-578.

26.
J. Hopcroft, D. Joseph, and S. Whitesides, ``On the Movement of Robotic Arms in 2-Dimensional Bounded Regions'', SIAM J. on Computing vol. 14, May 1985, pp. 315-333.

27.
S. H. Whitesides, ``A Classification of Certain Graphs with Minimal Imperfection Properties'', Annals of Discrete Math. vol. 21, 1984, pp. 281-297.

28.
J. Hopcroft, D. Joseph, and S. Whitesides, ``Movement Problems for 2-Dimensional Linkages'', SIAM J. on Computing vol. 13, Aug. 1984, pp. 610-629.

29.
Sue H. Whitesides, ``A Method for Solving Certain Graph Recognition and Optimization Problems, with Applications to Perfect Graphs'', Annals of Discrete Mathematics vol. 21, 1984, pp. 281-297.

30.
S. H. Whitesides, ``Edge-colored Complete Graphs with Alternating Cycles'', Discrete Math. vol. 46, 1983, pp. 299-304.

31.
S. H. Whitesides, ``A Classification of Graphs with Certain Minimal Imperfection Properties'', Discrete Math. vol. 38, 1982, pp. 303-310.

32.
S. H. Whitesides, ``An Algorithm for Finding Clique Cutsets'', Information Processing Letters vol. 12, 1981, pp. 31-32.

33.
V. Chvátal, R. Graham, A. Perold and S. Whitesides, ``Combinatorial Designs Related to the Strong Perfect Graph Conjecture'', Discrete Math. vol. 26, 1979, pp. 83-92.

34.
S. H. Whitesides, ``Collineations of Projective Planes of Order 10, Part II'', J. Combinatorial Theory A, vol. 26, 1979, pp. 269-277.

35.
S. H. Whitesides, ``Collineations of Projective Planes of Order 10, Part I '', J. Combinatorial Theory A vol. 26, 1979, pp. 249-268.

36.
Joan Hutchison and S. H. Whitesides, ``On a generalized regularity condition'', Theory and Application of Graphs, Lecture Notes in Mathematics vol. 642, Springer-Verlag, Berlin, 1978, pp. 304-308.



Book Chapters

$\bullet$ J. Hopcroft, D. Joseph and S. Whitesides, ``On the Movement of Robot Arms in 2-Dimensional Bounded Regions'', in Planning, Geometry and Complexity of Robot Motion, J. Schwartz, M. Sharir and J. Hopcroft, eds., Ablex Publishing Corp., 1987, pp. 304-329. (reprinted from [26])

$\bullet$ J. Hopcroft, D. Joseph and S. Whitesides, ``Movement Problems for 2-Dimensional Linkages'', in Planning, Geometry and Complexity of Robot Motion, J. Schwartz, M. Sharir and J. Hopcroft, eds., Ablex Publishing Corp, 1987, pp. 282-303. (reprinted from [28])

$\bullet$ V. Chvátal, R. Graham, A. Perold and S. Whitesides, ``Combinatorial Designs Related to the Strong Perfect Graph Conjecture'', in Topics on Perfect Graphs, C. Berge and V. Chvátal, eds. North Holland Mathematics Studies, Annals of Discrete Mathematics vol. 21, 1984, pp. 197-206, (reprinted from [33])

$\bullet$ S. H. Whitesides, ``A method for solving certain graph recognition and optimization problems, with applications to perfect graphs'', in Topics on Perfect Graphs, C. Berge and V. Chvátal, eds. North Holland Mathematics Studies, Annals of Discrete Mathematics vol. 21, 1984, pp. 281-298 (reprinted from [29])

$\bullet$ S. H. Whitesides, ``A Classification of Graphs with Certain Minimal Imperfection Properties'', in Topics on Perfect Graphs, C. Berge and V. Chvátal, eds. North Holland Mathematics Studies, Annals of Discrete Mathematics vol. 21, 1984, pp. 207-218 (reprinted from [31])




Edited Works

$\bullet$ J. of Graph Algorithms and Applications, Special Issue on Advances in Graph Drawing, G. Liotta and S. Whitesides, eds., vol. 4, no. 3, 2000.

$\bullet$ Graph Drawing. Sue Whitesides ed, Springer-Verlag LNCS vol. 1547, 1998.

$\bullet$ Data Structures and Algorithms (WADS '93). F. Dehne, J-R. Sack, N. Santoro and S. Whitesides, eds., Springer-Verlag LNCS, 1993.




Papers in Proceedings of Selective3 Conferences


1.
Vida Dujmovic and Sue Whitesides, ``On Validating Planar Worlds'', Proc. of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Washington DC, USA, Jan. 2001, pp. (talk given by Dujmovic)

2.
P. di Battista, G. Liotta, A. Lubiw, and S. Whitesides, Orthogonal Drawing of Cycles in 3D Space, Proc. of the Eighth Annual Symposium on Graph Drawing (GD 2000), Springer-Verlag, LNCS series, vol. 1984, pp. 272-283.

3.
P. di Battista, G. Liotta, A. Lubiw and S. Whitesides, ``Embedding Problems for Paths with Direction Constrained Edges'', Prod. of the Sixth Annual International Conference on Computing and Combinatorics (COCOON 2000), Springer-Verlag, LNCS series, vol. 1858, pp. 64-73.

4.
T. Biedl, E. Demaine, M. Demaine, S. Lazard, A. Lubiw, J. O'Rourke, M. Overmars, S. Robbins, I. Streinu, G. Toussaint, and S. Whitesides, ``Locked and Unlocked Polygonal Chains in 3D'', Proc. of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Baltimore MD, USA, Jan. 1999, pp. 866-867. (talk given by O'Rourke)

5.
T. Biedl, J. Marks, K. Ryall, and S. Whitesides, ``Graph Multidrawing: Finding Nice Drawings without Defining Nice'', Proc. of Graph Drawing 1998 (GD '98), Montreal, Aug. 13-15, 1998, Springer-Verlag LNCS series, vol. 1547, pp. 347-355.

6.
P. Agarwal, T. Biedl, S. Lazard, S. Robbins, S. Suri and S. Whitesides, ``Curvature-Constrained Shortest Paths in a Convex Polygon'', Proc. of the ACM Fourteenth Annual Symposium on Computational Geometry, Minneapolis, Minnesota, USA, June 7-10, 1998, published by the ACM, pp. 392-401. (talk given by Whitesides)

7.
T. Biedl, T. Shermer, S. Whitesides and S. Wismath, ``Orthogonal 3-D Graph Drawing'', in Proc. of the Fifth International Symposium on Graph Drawing, GD '97, Sept. 18-20, 1997, Rome, Italy, G. Di Battista, ed., Springer-Verlag Lecture Notes in Computer Science LNCS vol. 1353, pp. 76-86. (talk given by Wismath)

8.
S. Fekete, M. Houle and S. Whitesides, ``The Wobbly Logic Engine: Proving Hardness of Non-rigid Geometric Graph Representation Problems'', in Proc. of the Fifth International Symposium on Graph Drawing, GD '97, Sept. 18-20, 1997, Rome, Italy, G. Di Battista, ed., Springer-Verlag Lecture Notes in Computer Science LNCS vol. 1353, pp. 272-283. (talk given by Fekete)

9.
P. Eades, A. Symvonis and S. Whitesides, ``Two Algorithms for Three Dimensional Orthogonal Graph Drawing'', in Proc. of the Symposium on Graph Drawing, GD '96, Sept. 18-20, 1996, Mathematical Sciences Research Institute, Berkeley CA, USA, Springer Verlag Lecture Notes in Computer Science, in press. (talk given by Whitesides)

10.
Naixun Pei and Sue Whitesides, ``On the Reconfiguration of Chains'', in Computing and Combinatorics, Proc. of the Second Annual International Conference, COCOON '96, Hong Kong, June 17-19, 1996, J-Y Cai and C-K Wong, eds.), Springer-Verlag Lecture Notes in Computer Science LNCS vol. 1090, pp. 381-390. (talk given by Pei)
11.
G. Di Battista, G. Liotta and S. Whitesides, ``The Strength of Weak Proximity'', in Graph Drawing, Proc. of the Symposium on Graph Drawing, GD '95, Passau, Germany, Sept. 20-22, 1995, F. Brandenburg, ed., Springer-Verlag, Lecture Notes in Computer Science LNCS vol. 1027, pp. 178-189. (talk given by Whitesides)

12.
H. Alt, M. Godau and S. Whitesides, ``A Universal 3-Dimensional Visibility Representation for Graphs'', in Graph Drawing, Proc. of the Symposium on Graph Drawing, GD '95, Passau, Germany, Sept. 20-22, 1995, F. Brandenburg, ed., Springer-Verlag, Lecture Notes in Computer Science LNCS vol. 1027, pp. 8-19. (talk given by Godau)
13.
S. Fekete, M. Houle and S. Whitesides, ``New Results on a Visibility Representaion of Graphs in 3D'', in Graph Drawing, Proceedings of the Symposium on Graph Drawing, GD '95, Passau, Germany, Sept. 20-22, 1995, F. Brandenburg, ed., Springer-Verlag, Lecture Notes in Computer Science LNCS vol. 1027, pp. 234-241. (talk given by Fekete)

14.
P. Eades and S. Whitesides, ``Nearest Neighbor Graph Realizability is NP-hard,'' in Theoretical Informatics, Proc. of LATIN '95, Valparaiso, Chile, April 3-7, 1995, Springer-Verlag, Lecture Notes in Computer Science LNCS vol. 911, pp. 245-256. (talk given by Whitesides)
15.
G. Dudek, K. Romanik and S. Whitesides, ``Localizing a Robot with Minimum Travel'' in Proc. of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), San Francisco CA, USA, Jan. 22-24, 1995, pp. 437-446. (talk given by Romanik)

16.
H. ElGindy, G. Liotta, A. Lubiw, H. Meijer and S. Whitesides, ``Recognizing Rectangle of Influence Drawable Graphs,'' in Proc. of the DIMACS International Symposium on Graph Drawing, GD '94, Princeton NJ, USA, Oct. 10-12, 1994, Springer-Verlag Lecture Notes in Computer Science LNCS vol. 894, pp. 352-363. (talk given by Meijer)

17.
P. Eades and S. Whitesides, ``The Realization Problem for Euclidean Minimum Spanning Trees is NP-hard'', in Proc. of the ACM Tenth Annual Symposium on Computational Geometry, SUNY Stony Brook, Stony Brook, NY, USA, June 6-8, 1994, pp. 49-56. (presented by Whitesides)

18.
S. Whitesides and R. Zhao, ``Algorithmic and Complexity Results for Drawing Euclidean Trees,'' in Advanced Visual Interfaces, Proc. of the International Workshop AVI '92, Rome, Italy, May 25-29, 1992, T. Catarci, M. F. Costabile & S. Levialdi, eds.. World Scientific Series in Computer Science vol. 36, 1992, pp. 395-410. (talk given by Whitesides)

19.
W. Lenhart, R. Pollack, J. Sack, R. Seidel, M. Sharir, S. Suri, G. Toussaint, S. Whitesides and C. Yap, ``Computing the Link Center of a Simple Polygon'', in Proc. of the ACM Third Annual Symposium on Computational Geometry, Waterloo, Canada, June 1987, pp. 1-10. (talk given by Lenhart)
20.
J. Hopcroft, D. Joseph and S. Whitesides, ``On the Movement of Robot Arms in Two-dimensional Bounded Regions'', in Proc. of the IEEE 23rd Annual Symposium on the Foundations of Computer Science (FOCS), Chicago IL, USA, Nov. 3-5, 1982, pp. 280-289. (talk given by Whitesides)



Papers in Proceedings of Non-selective4 Conferences

1.
H. Everett, S. Lazard, S. Robbins, H. Schrø:der and S. Whitesides, ``Convexifying Star-shaped Polygons'', in Proc. of the Tenth Canadian Conference on Computational Geometry CCCG '98, McGill University, Montreal, Canada, Aug. 10-12, 1998, pp. 2-3.

2.
T. Biedl, E. Demaine, M. Demaine, S. Lazard, A. Lubiw, J. O'Rourke, S. Robbins, I. Streinu, G. Toussaint and S. Whitesides, ``On Reconfiguring Tree Linkages: Trees Can Lock'', in Proc. of the Tenth Canadian Conference on Computational Geometry CCCG '98, McGill University, Montreal, Canada, Aug. 10-12, 1998, pp. 4-5.

3.
T. Biedl, E. Demaine, M. Demaine, A. Lubiw, M. Overmars, J. O'Rourke, S. Robbins and S. Whitesides, ``Unfolding Some Classes of Orthogonal Polyhedra'', in Proc. of the Tenth Canadian Conference on Computational Geometry CCCG '98, McGill University, Montreal, Canada, Aug. 10-12, 1998, pp. 70-71.

4.
N. Pei and S. Whitesides, ``On Folding Rulers in Regular Polygons'', in Proc. of the Ninth Canadian Conference on Computational Geometry CCCG '97, Queen's University, Kingston, Ontario, Canada, Aug. 11-14, 1997, pp. 11-16. (talk given by Pei)

5.
N. Pei and S. Whitesides, ``On the Reachable Regions of Chains'', in Proc. of the Eighth Canadian Conference on Computational Geometry CCCG '96, Carleton University, Ottawa, Ontario, Canada, Aug. 12-15, 1996, pp. 161-166. (talk given by Whitesides)

6.
H. ElGindy, M. Houle, W. Lenhart, M. Miller, D. Rappaport, S. Whitesides, ``Dominance Drawings of Bipartite Graphs'', in Proc. of the Fifth Canadian Conference on Computational Geometry, U. of Waterloo, Waterloo, Ontario, Canada, Aug. 5-10, 1993, pp. 187-191. (talk given by Rappaport)

7.
M. van Kreveld, J. Snoeyink and S. Whitesides, ``Folding Rulers Inside Triangles'', in Proc. of the Fifth Canadian Conference on Computational Geometry, U. of Waterloo, Waterloo, Ontario, Canada, Aug. 5-10, 1993, pp. 1-6. (talk given by van Kreveld)

8.
W. Lenhart and S. Whitesides, ``Reconfiguration with Line Tracking Motions,'' in Proc. of the Fourth Canadian Conference on Computational Geometry, St. John's, Newfoundland, Canada, Aug. 10-14, 1992, pp. 198-203. (talk given by Whitesides)

9.
W. J. Lenhart and S. H. Whitesides, ``Turning a Polygon Inside-out," in Proc. of the Third Canadian Conference on Computational Geometry, Vancouver, British Columbia, Canada, Aug. 6-10, 1991, pp. 66-69. (talk given by Whitesides)

10.
H. Everett and S. Whitesides, ``Finding all the Largest Circles in a 3-Dimensional Box'', in Proc. of the Third Canadian Conference on Computational Geometry, Vancouver, British Columbia, Canada, Aug. 6-10, 1991, pp. 84-87. (talk given by Whitesides)

11.
S. Whitesides and R. Zhao, ``Offsets of Circular Arc Figures'', in Proc. of the Second Canadian Conference on Computational Geometry, Ottawa, Ontario, Canada, Aug. 6-10, 1990, pp. 362-365. (talk given by Whitesides)

12.
S. Whitesides, K. Abadjian, P. Hum, and N. Rodjanapiches, ``Computer-aided Instruction for a Theorem in Geometry'', in Proc. of the ISMM5 30th International Symposium on Mini and Microcomputers and their Applications, Montreal, Quebec, Canada, June 3-5, 1985. (talk given by Whitesides)

13.
J. Hutchinson and S. Whitesides, ``A Note on a Generalized Regularity Condition'', in Proc. of the International Graph Theory Conference, Kalamazoo, Michigan, USA, June 1976, pp. 304-308. (given by Hutchinson as an invited talk)

14.
S. H. Whitesides, ``Projective Planes of Order 10 have no Collineations of Order 11 '' in Proc. of the Seventh Southeastern Conference of Combinatorics, Graph Theory, and Computing, Baton Rouge, Louisiana, USA, Feb. 9-12, 1976, Hoffman, Lesniak, Mullin, Reid, Stanton eds., Congressus Numerantum XVII, Utilitas Mathematica, Winnipeg, 1976.

Research Summary


My research interests lie in combinatorial mathematics and theoretical computer science, including algorithmic and complexity issues in discrete and computational geometry, graph drawing, and motion planning. A package of papers sampling my research is available upon request. Brief descriptions of them appear below.


Fabrication of Microstructures

My work in this area has been ``in the news'': see Chemical and Engineering News, vol 79, no. 10, March 5, 2001, the news item on pp. 36-37 entitled ``Entering the Next Dimension'', reported in the Science and Technology column. (C&EN is the weekly professional news publication of the American Chemical Society. In addition to hard copy, it is available online to ACS members at http://pubs.acs.org/CEN.)



Paper [WB00] below represents my recent interest in geometric layout problems that arise in the fabrication of structures at the micron scale. This work was done in collaboration with a chemistry group headed by George Whitesides6 at Harvard University. The chemists describe their techniques to me, and pose questions of an open-ended nature, and I suggest interesting general structures that those techniques might be able to fabricate, together with mathematical ideas for obtaining the spatial layouts required. Together we develop the ideas in a collaborative and interactive way. This work in microfabrication technology provides an application area for my theoretical interest in 3D layouts for graphs, described further below.


$\bullet$ [WB00] H. Wu, S. Britain, J. Andersen, B. Grzybowski, S. Whitesides, and G. Whitesides, ``Fabrication of Topologically Complex Three-Dimensional Microstructures: Metallic Microknots'', J. Am. Chem. Soc., vol. 122, no. 51, 2000, pp. 12691-12699.



Graph Drawing

Graph Drawing is a relatively new research community that has emerged from topological graph theory and computational geometry. It seeks to produce good layouts outs for structures modelled as graphs. Here, what constitutes a good layout depends on the intended use, which might be visual (e.g., in the case of the diagram of a computer program) or electronic (e.g., in the case of a circuit layout), or for microfabrication applications.



Paper [BL+00a] below characterizes what regions of space a non-self-intersecting path can reach if it is only partially specified, as a sequence of directions without metric information. It lays the foundations for extension to 3D of the topology-shape-metrics approach used in 2D VLSI layout. The paper has been submitted to Algorithmica, where it was invited for a special issue on the highlights of COCOON 2000. Paper [BL+00b] gives a combinatorial characterization of direction sequences that can be realized in 3D as nonintersecting cycles.

$\bullet$ [BL+00a] P. di Battista, G. Liotta, A. Lubiw and S. Whitesides, ``Embedding Problems for Paths with Direction Constrained Edges'', Prod. of the Sixth Annual International Conference on Computing and Combinatorics (COCOON 2000), Springer-Verlag, LNCS series, vol. 1858, pp. 64-73.

$\bullet$ [BL+00b] P. di Battista, G. Liotta, A. Lubiw, and S. Whitesides, Orthogonal Drawing of Cycles in 3D Space, Proc. of the Eighth Annual Symposium on Graph Drawing (GD 2000), Springer-Verlag, LNCS series, vol. 1984, pp. 272-283.



Paper [ESW00] below studies trade-offs between bend minimization and volume minimization for 3D rectilinear layouts of graphs, and provides two methods for 3D layout.

$\bullet$ [ESW00] P. Eades, A. Symvonis, and S. Whitesides, ``Three-dimensional orthogonal graph drawing algorithms'', Discrete Applied Mathematics, vol. 103, no. 1-3, 15 July 2000, pp. 55-87.



Paper [AGW98] below shows how to represent any graph as a visibility graph of objects in 3D. It was invited to the special issue of Computational Geometry, Theory and Applications devoted to the highlights of the conference.

$\bullet$ [AGW98] Alt, M. Godau and S. Whitesides, ``A Universal 3-Dimensional Visibility Representation for Graphs'', invited, refereed paper for Computational Geometry, Theory and Applications, Special Issue on Graph Drawing, R. Tamassia and G. Di Battista, eds., vol. 9, pp. 111-125, 1998.



Paper [EW96a] below gives a paradigm for proving NP-hardness results for many geometric problems. In particular, it shows that mutual nearest neighbor graphs are apparently difficult to recognize. It also implies a result of Breu and Kirkpatrick, that contact graphs of unit disks are hard to recognize. A section of the book ``Graph Drawing'', by Di Battista, Eades, Tamassia, and Tollis, Prentice Hall, 1999, is devoted to explaining the technique.

$\bullet$ [EW96a] P. Eades and S. Whitesides, ``The Logic Engine and the Realization Problem for Nearest Neighbor Graphs'', Theoretical Computer Science vol. 169, no. 1, Nov., 1996, pp. 23-37.



Paper [EW96b] below proves that it is NP-hard to determine whether a combinatorial tree can be realized as the Euclidean minimum spanning tree of a set of points, settling an open problem. I presented the conference abstract version at the ACM Symposium on Computational Geometry in 1994.

$\bullet$ [EW96b] P. Eades and S. Whitesides, ``The Realization Problem for Euclidean Minimum Spanning Trees is NP-Hard'', Algorithmica vol. 16, no. 1, July 1996, pp. 60-82.



Motion Planning

Paper [AB+] below addresses the difficult problem of shortest path planning for mobile robots whose motion is subject to a bound on the radius of curvature of the path. Previous work in computational geometry typically proposed polygonal paths that could not be followed by such a robot. We found a surprising result, that in a convex polygonal environment, the complexity of the shortest feasible path (if indeed a feasible path exists) does not depend on the number of sides of the polygon. I presented a conference abstract version of this work to the ACM Symposium on Computational Geometry in 1998. The journal version has been submitted to SIAM J. Computing.

$\bullet$ [AB+] P. Agarwal, T. Biedl, S. Lazard, S. Robbins, S. Suri and S. Whitesides, ``Curvature-Constrained Shortest Paths in a Convex Polygon'', Proc. of the ACM Fourteenth Annual Symposium on Computational Geometry, Minneapolis, Minnesota, USA, June 7-10, 1998, published by the ACM, pp. 392-401.



Paper [DRW98] below studies a localization problem in which a mobile robot is to determine, with a minimum amount of travel, its location in a self-similar environment for which it has a map. The paper presents an approximation strategy that is in some sense best possible. This work represents a collabortion among my postdoctoral student at the time, Kathleen Romanik, my colleague, Greg Dudek, and myself. The conference abstract version was presented at the ACM-SIAM Symposium on Discrete Algorithms (SODA), 1995, and the full journal version appeared in the SIAM J. Computing. A section of Dudek's recent book (with Jenkin) on Mobile Robotics is devoted to a presentation of this work.

$\bullet$ [DRW98] Greg Dudek, Kathleen Romanik, and Sue Whitesides, ``Localizing a Robot with Minimum Travel'', SIAM J. on Computing, vol. 27, no. 2, pp. 583-604, 1998.



Paper [LW95] below is joint work with my former Ph.D. student Bill Lenhart. We studied reconfiguration problems for closed link chains, first in the plane, then in space of arbitrary dimension. We found extremely simple, algorithmic solutions to problems that had previously been studied by topological methods. In the context of this work, in 1991 we posed to the computational geometry community a problem that became very well known and remained open for ten years: can a non-crossing chain of segments, confined to the plane, be moved to a straightened configuration without introducing crossings during the motion? We circulated this question as an open problem at numerous seminars and international conferences, beginning in March 1991. It became a ``household'' problem. The question had still not been solved by the time our paper was published in 1995, and appears in our journal article as well as in an earlier 1993 School of Computer Science technical report version of that article. We eventually learned that the problem had been posed in the mathematics community earlier than our discovery of it; also, the problem was independently discovered in the computational geometry community by Joe Mitchell, sometime after we began circulating it in 1991. The question has now been answered in the affirmative by R. Connelly, E. Demaine, and G. Rote; their FOCS 2000 paper acknowledges this paper and our contribution to the history of the problem.

$\bullet$ [LW95] W. Lenhart and S. Whitesides, ``Reconfiguring Closed Polygonal Chains in Euclidean d-Space'', Discrete and Computational Geometry, vol. 13, 1995, pp. 123-140.



Technical Report [WZ00] below formed part of the Ph.D. thesis of my student Rongyao Zhao. It generalizes a well-known theorem of K. Kedem, R. Livne, J. Pach, and M. Sharir in their paper ``On the union of Jordan regions and collision- free translational motion amidst polygonal obstacles'', Discrete Comput. Geom. 1, 1986, p. 59-71. We were able to generalize this theorem significantly, by introducing a key new concept. Inspired by our work, Pach and Sharir revisited the original proof, and proved it in a different way that could be generalized via our new concept.

$\bullet$ [WZ00] Sue Whitesides and Rongyao Zhao, ``K-admissible collections of Jordan curves and offsets of circular arc figures''. Technical Report No. SOCS 90.08, 1990, School of Computer Science, McGill University.



The next two papers resulted from the year 1981-82, which I spent at Cornell University supported by a Junior Faculty Fellowship from Dartmouth. They were the beginning of my interest in algorithmic motion planning, and in particular, in the reconfiguration properties of chains of links. I presented a conference version at the IEEE Symposium on the Foundations of Computer Science (FOCS), 1982.



Paper [HJW85] gives polynomial time algorithms for certain reconfiguration problems for simple, open chains of links. It shows that while some motion planning problems of this kind are seemingly intractible, others can be solved in polynomial time in spite of having an unbounded number of degrees of freedom.

$\bullet$ [HJW85] J. Hopcroft, D. Joseph, and S. Whitesides, ``On the Movement of Robotic Arms in 2-Dimensional Bounded Regions'', SIAM J. on Computing vol. 14, May 1985, pp. 315-333.



Paper [HJW84] studies arbitrary planar linkages and shows that a reachability problem for them is PSPACE-hard. It was among the very early lower bound results in algorithmic motion planning.

$\bullet$ [HJW84] J. Hopcroft, D. Joseph, and S. Whitesides, ``Movement Problems for 2-Dimensional Linkages'', SIAM J. on Computing vol. 13, Aug. 1984, pp. 610-629.



Perfect Graphs

The next two papers represent my interest in the famous ``perfect graph'' conjecture of Claude Berge, a long-standing, still open problem. As described in the introduction to Topics on Perfect Graphs by C. Berge and V. Chv'atal, I proposed that all perfect graphs might be constructable from primitive perfect pieces by means of a finite set of operations that preserve perfection. If the operations could be undone and the primitive pieces recognized quickly, this could give a fast recognition algorithm for perfect graphs. Papers [Wh84] and [Wh81] explored that idea, studying the perfection preserving operation of ``gluing'' perfect graphs together at a clique, creating a clique cutset in the new graph. Paper [Wh81] studies how to undo the glueing operation in an arbitrary graph, and paper [Wh84] explores the applications of paper [Wh81]. The possible applications of [Wh81] were also explored in a 1985 Discrete Mathematics paper, pp. 221-232, entitled ``Decomposition by Clique Separators'', by Robert Tarjan, who referenced [Wh81] but was evidently not aware that I had published similar results to his, a year earlier, in [Wh84].

$\bullet$ [Wh84] Sue H. Whitesides, ``A Method for Solving Certain Graph Recognition and Optimization Problems, with Applications to Perfect Graphs'', Annals of Discrete Mathematics vol. 21, 1984, pp. 281-297.

$\bullet$ [Wh81] S. H. Whitesides, ``An Algorithm for Finding Clique Cutsets'', Information Processing Letters vol. 12, 1981, pp. 31-32.



Projective Planes

Paper [Wh79] below represents my research on finite projective planes. It contributed to a famous problem that arose with the appearance of the Bruck-Ryser Theorem in 1949, namely, the question of whether a projective plane of order 10 exists. My work showed that any plane of order 10 would have very little symmetry: the full automorphism group of such a plane would have order 1, 3, or 5.

This result, obtained by purely combinatorial and algebraic methods, represented the first concrete progress on the problem in 25 years. My work is referenced by R. Anstee, M. Hall and J. Thompson, who attacked the remaining small symmetry groups. Eventually, Clement Lam used massive amounts of supercomputer time to rule out the possibility of an order 10 plane. No purely mathematical solution is known. My work on the subject was purely mathematical. The general question of whether there exist projective planes of non-prime-power order has now been open for over fifty years.

$\bullet$ [Wh79] S. H. Whitesides, ``Collineations of Projective Planes of Order 10, Part II'', J. Combinatorial Theory A, vol. 26, 1979, pp. 269-277.

(Part I of the above work gave the result of my Ph.D. thesis, that the prime divisors of the automorphism group could be only 3 and 5; part II, which brought the order of the entire group down to 1, 3, or 5, was done after I graduated.)



Other Work

Not all my research fits into one of the categories above. A representative of this other work is the following paper [ES+98], which solves a problem posed by Victor Klee: to determine the largest radius sphere contained in an axis-aligned rectangular box, when the dimension of the sphere is strictly less than the dimension of the box. We solve this problem in arbitrary dimensional space.

$\bullet$ [ES+98] I. Stojmenovic, S. Whitesides and P. Valtr, ``The Largest k-Ball in a d-Dimensional Box'', Computational Geometry, Theory and Applications, vol. 11, 59-67, 1998.



evidence of impact: From the beginning, I have considered difficult problems (e.g., the existence of projective planes of order 10, the perfect graph conjecture). My work has appeared in excellent journals, has been cited by top people in the field, and has been included in major collected works. Evidence of this includes the following.

* My work on finite projective planes is cited by R. Anstee, M. Hall Jr., and J. Thompson, ``Planes of Order 10 do not have a Collineation of Order 5'', J. Combinatorial Theory A, vol. 29 (1), 1980, pp. 39-58. Marshall Hall Jr. was a Professor of Mathematics at Cal Tech, a leading combinatorialist of his time, and Ph.D. supervisor of Donald Knuth of computer science fame; John Thompson was the 1970 recipient of the Fields Medal. Other papers citing this work include N. J. A. Sloane and J. G. Thompson, ``The non-existence of a certain Steiner system S(3,12,122)'', J. Combinatorial Theory A, vol. 30 (3), 1981, pp. 209-236.

* Three of my papers on perfect graphs appear in the volume ``Topics in Perfect Graphs'', edited by Claude Berge and Vasek Chv'atal, North Holland, 1984. One of these papers is also described in the book "Algorithmic Graph Theory and Perfect Graphs'' by M. C. Golumbic, Academic Press, New York, 1980. The book ``Graph Coloring Problems'' by T. R. Jensen and B. Toft, John Wiley & Sons, New York, 1995, also cites my work on perfect graphs.

* My work on clique cut sets was cited by Robert Tarjan, a Turing award medalist list, in his paper ``Decomposition by Clique Separators'', Discrete Math. vol. 55 (2), 1985, pp. 221-232, where he independently rediscovered my results on applications of clique cut sets appearing in [WH84].

* Two of my papers on planar linkage movement ([HJW84] and [HJW85]) appear in the book ``Planning, Geometry and Complexity of Robot Motion'', J. Schwartz, M. Sharir, and J. Hopcroft, eds., Ablex Publishing Corp. 1987. The ``carpenter's rule problem'' from this work is also described in the textbook ``Computational Geometry in C'' by Joseph O'Rourke, Cambridge University Press, 1998, and in the graduate algorithms textbook ``The Design and Analysis of Algorithms'', by Dexter Kozen, Springer-Verlag, 1992.

* The book ``Robot Motion Planning'' by Jean-Claude Latombe, Kluwer, Boston, 1991 includes a section (pp. 234-242) that originally appeared in my early survey article on algorithmic motion planning entitled ``Computational Geometry and Motion Planning''. This survey appeared in the book ``Computational Geometry'', edited by Godfried Toussaint, Springer-Verlag, 1985, pp. 377-427.

* The Ph.D. thesis of my student Michael Karasick is frequently cited, and is described in the book ``Geometric and Solid Modeling'' by Christoph M. Hoffmann, Morgan & Kaufmann, 1989.

* My graph multi-drawing work with T. Biedl, J. Marks and K. Ryall, which appeared as a conference abstract in Graph Drawing '98 (see [5] on p. 7 of my CV), has led to a patent application put forward by Mitsubishi Electric Cambridge Research Lab.

* My collaboration with the chemistry group on geometric layout for microfabrication has led to a patent application put forward by Harvard University. It has attracted attention from the press (e.g., see Technology Research News, December 20/27, 2000, ``"3-D geometry adds twist to microfabrication''; and Chemical and Engineering News, pp. 36-37, March 5, 2001).

* The book "Graph Drawing" by G. Di Battista, P. Eades, R. Tamassia, and I. Tollis, Prentice Hall, 1999, cites five of my papers, and devotes the section on proving lower bounds to the paradigm presented in [EW96a] above.

* My work [DRW98] on robot localization is described in detail in the book ``Computational Principles of Mobile Robotics'' by Greg Dudek and Michael Jenkin, Cambridge U. Press, 2000.



a note on authorship: The tradition in the fields in which I normally work is to list authors in alphabetical order. However, the tradition in chemistry is different. The papers that I have coauthored in collaboration with chemists list the students who carry out the laboratory work first, and the lab director last. As a collaborator outside the group, my name is listed beween the students' names and that of the group's research director.


Research Support

My research has been continuously supported by individual grants from NSERC (National Science and Engineering Research Council, Canada) and team grants from FCAR (the Quebec science foundation). Before moving to Canada, I held an individual research grant from NSF (National Science Foundation, US); also, I held a grant from the Mellon Foundation (while at Tufts) and a Junior Faculty Fellowship (while at Dartmouth). Other agencies providing support have included the Quebec Minster of External Relations (for research exchange visits with France and Spain, in coorporation with government agencies from those countries), the Canadian Minister of State (for a Network of Centres of Excellence group grant), and SSHRC (Social Sciences and Humanities Research Council, Canada, for a collaboration with sociologists).




Grant and Program Selection Committees


NSF
Member, NSF Grant Selection Panel for the Numeric, Symbolic and Geometric Computation (NSG) Program of the Directorate of Computer and Information Science (CISE) Washington DC (Arlington VA), 2001

WADS
Member, Program Committee, WADS 2001 (Seventh Workshop on Data Structures and Algorithms), Brown U., Aug. 8-10, Jan. 2001

NSF
Member, NSF Grant Selection Panel for the Numeric, Symbolic and Geometric Computation (NSG) Program of the Directorate of Computer and Information Science (CISE) Washington DC (Arlington VA), Jan. 2000

GD
Member, Program Committee, GD '99 (Graph Drawing '99), Prague, Czech Republic, Sept. 15-19, 1999.

NSERC
Member, NSERC Grant Selection Committee, Computer Science, Ottawa 1998-99

GD
Chair, Program Committee, GD '98 (Graph Drawing '98), Montreal, Canada, August 13-15, 1998. Conference proceedings published in the Springer-Verlag LNCS series as vol. 1547

CCCG
Member, Organizing and Program Committees, Tenth Canadian Conference on Computational Geometry, Montreal, Aug. 10-12, 1998

CATS
Member, Program Committee, CATS '98 (Computing - the Australasian Theory Symposium), Perth, Australia, February 2-3, 1998

NSERC
Member, NSERC Grant Selection Committee, Computer Science, Ottawa, 1997-98

NSF
Member, NSF Grant Selection Panel for the Numeric, Symbolic and Geometric Computation (NSG) Program of the Directorate of Computer and Information Science (CISE) Washington DC (Arlington VA), 1997

CIAC
Member, Program Committee, CIAC '97 (Third Italian Conference on Algorithms and Complexity), Rome, Italy, March 12-14, 1997

NSERC
Member, NSERC Grant Selection Committee, Computer Science, Ottawa, 1996-97

ACM
Member, Program Committee, ACM Twelfth Annual Symposium on Computational Geometry, Philadelphia USA, May 24-26, 1996. Proceedings published by the Association for Computing Machinery.

ISAAC
Member, Program Committee, ISAAC '95 (Sixth Annual International Symposium on Algorithms and Computation), December 4-6, 1995, Cairns, Australia. Springer-Verlag LNCS series vol. 1004

WADS
Member, Program Committee, Fourth International Workshop on Algorithms and Data Structures (WADS '95), Kingston, Canada, August 16-18, 1995. Springer-Verlag LNCS series vol. 955

GD
Member, Program Committee, DIMACS International Symposium on Graph Drawing, GD '94, Princeton NJ, USA. Oct. 10-12, 1994. Springer-Verlag LNCS series vol. 894

WADS
Chair, and member of program committee, Workshop on Algorithms and Data Structures '93 (WADS '93), Montreal, August 11-13, 1993. Springer-Verlag LNCS series vol. 709

CCCG
Member, program committee, Fourth Canadian Conference on Computational Geometry, St. John's, Newfoundland, Canada, August 10-14, 1992

CCCG
Member, program committee, First Canadian Conference on Computational Geometry, Montreal, August, 1988




Invited Conference Talks


1.
Invited hour address Twelfth Annual International Symposium on Algorithms and Computation (ISAAC '01), Dec. 19-21, 2001, Christchurch, New Zealand

2.
Invited hour address Twelfth Australasian Workshop on Combinatorial Algorithms (AWOCA 2001), Bandung, Indonesia, July 14-17, 2001

3.
DSRC/DARPA Workshop on Self-Assembly in Manufacturing, Arlington VA, USA, Dec. 6-7, 2000, invited 20 minute talk: ``Shape Matters''

4.
Tenth SIAM Conference on Discrete Mathematics, Special Session on Combinatorial Geometry organized by Pavel Valtr and Günter Rote, Minneapolis MN, June 12-15, 2000, invited 20 minute talk: ``3D Embedding Problems for Paths and Cycles''

5.
Invited hour address Conference on Recent Trends in Geometry and Symmetry, Madison, Wisconsin, May 4-7, 2000: ``Geometry in Motion: a Survey of Linkage Movement Problems''

6.
Invited series of 3 hour talks The Fields Institute, Toronto, Mini-symposium on Geometric Representations of Graphs organized by Petr Hlineny, April 11-14, 2000:

April 11, 2000: ``Complexity Lower Bounds for Geometric Representations of Graphs''

April 12, 2000: ``Some 2D Visibility Representations of Graphs''

April 13, 2000: ``Some 3D Visibility Representations of Graphs''

7.
Invited hour address 24th Australasian Conference on Combinatorial Mathematics and Combinatorial Computingi (ACCMCC '99), Northern Territory University, Darwin, Australia, July 5-9, 1999: ``Geometric Representations of Graphs''

8.
Workshop on Graph Algorithms, Schloss Dagstuhl International Conference and Research Centre for Computer Science, July 26-31, 1998, invited 20 minute talk: ``Graph Multidrawing''

9.
Invited hour address Ninth SIAM (Society for Industrial and Applied Mathematics) Conference on Discrete Mathematics, Toronto, July 12-15, 1998: ``Graph Visibility''.

10.
Invited hour address CoNE Conference (Combinatorics of New England - a series of NSF sponsored one-day conferences), April 5,1997, Northampton MA, USA: ``On Geometric Representations of Graphs''.

11.
American Math Society Regional Meeting, Université de Montréal, Montreal, Canada, September 28, 1997, invited 20 minute talk, Special Session on Combinatorial and Computational Geometry, R. Pollack, D. Avis and E. Goodman, organizers: ``On the Reconfiguration of Chains in Disks'', presented by co-author N. Pei.
12.
Ph.D. Centennial Conference, Department of Mathematics, University of Wisconsin, Madison, Wisconsin, May 21-24, 1997, invited 20 minute talk, Mini-Symposium on Geometry, Don Crowe and Joe Malkevitch, organizers: ``On the Geometric Representations of Graphs''

13.
American Math Society Regional Meeting, Rider University, Lawrenceville NJ, USA, Oct. 5-6, 1996, invited 20 minute talk, Special Session on Combinatorial and Computational Geometry, W. Steiger and I. Streinu, organizers: ``The Logic Engine Approach to Geometric Lower Bounds''

14.
Workshop on Graph Drawing, Schloss Dagstuhl International Conference and Research Centre for Computer Science, Germany, May 13-17, 1996, invited 20 minute talk: ``Geometric and Visibility Representations of Graphs''

15.
Invited 90 minute address Journées Géométriques et Algorithmiques, St. Malo, France, May 18, 1995: ``Réprésentations géométriques des graphes (Geometric Representations of Graphs)''

16.
American Mathematics Society Regional Meeting, Brooklyn NY, USA, April 8, 1994, Special Session on Convexity, Discr. Geometry and Comput. Geometry, invited 20 minute talk: ``Geometric Drawings of Graphs''

17.
IX Coloquio de Teoria de las Graficas, Combinatoria y sus Aplicaciones, Universidad Autonoma de Yucatan, Facultad de Matematicas, invited 20 minute talk, Mérida, Mexico, Feb. 23, 1994: ``Geometric Embeddings of Trees''

18.
University of Newcastle Workshop Series in Computational Geometry, Hawk's Nest, New South Wales, Australia, Nov. 30-Dec. 4, 1992, invited 20 minute talk: ``Geometric Realizations of Abstract Graphs''

19.
Invited series of three 90 minute talks Fifth Australasian Workshop on Combinatorial Algorithms (AWOCA '92), Ubud, Bali, Indonesia, June 29-July 3, 1992, ``Algorithmic Motion Planning for Linkages''
20.
Invited hour address 7 Coloquio de Teoria de las Graficas, Combinatoria y sus Aplicaciones, Zacatecas, Mexico, Feb. 24-28, 1992: ``Problemas acerca del Movimiento/Movement Problems''
21.
Invited hour address WINDOWS Conference, University of British Columbia, Vancouver, British Columbia, Canada, Sept. 9, 1990: ``Getting from Here to There: a Computer Science View''
22.
Geometry Conference in Honor of Shreeram Abhyankar, Purdue University, West Lafayette, Indiana, USA, June 1-5, 1990, invited 20 minute talk: ``An Open Problem in Algebra and Geometry''
23.
Canadian Mathematical Society Summer Meeting, Special Session on Theoretical Computer Science, Kingston, Ontario, Canada, May 28, 1987, invited 20 minute talk: ``Motion Planning''

24.
American Mathematics Society Summer Meeting, Special Session on Computational Geometry, Toronto, Ontario, Canada, Aug. 1982, invited 20 minute talk: ``Motion Planning'' (given by coauthor D. Joseph)

25.
Invited hour address Annual Meeting, Mathassociates7, Waltham, Massachusetts, USA, April 1982, ``A Survey of Linear Programming - History and Applications''

26.
Invited hour address Annual Meeting, National Council of Teachers of Mathematics (USA), Toronto, Ontario, Canada, April 1982: ``Linear Programming, the New Calculus?''

27.
American Mathematics Society Regional Meeting, Special Session on Graph Theory, University of Massachusetts, Amherst, Massachusetts, USA, Oct. 1981, invited 20 minute talk: ``Finding Clique Cut Sets''

28.
Invited hour address Université de Montréal, Séminaire de Mathématiques Supérieures Conference, Montreal, Quebec, Canada, June 1978: ``Perfect Graphs''

29.
Invited hour address Mathematical Association of America, New England Section Meeting, Boston, Massachusetts, USA, Nov. 1978: ``Linear Programming''


Invited Research Seminars

1.
Queen's U., Kingston, March 9, 2001, CS Dept. Colloquium, ``Embedding Problems for Paths and Cycles''

2.
New York University (NYU), Courant Institute, New York, USA, Nov. 14, 2000, Geometry Seminar: ``Embedding Problems for Paths and Cycles with Direction Constrained Edges''

3.
Cornell U., Ithaca NY, USA, Aug. 2000, Math. Dept. Seminar: ``Embedding Problems for Paths and Cycles with Direction Constrained Edges''

4.
U. of Rochester, Rochester NY, USA, Aug. 2000, CS Dept. Seminar: ``Embedding Problems for Paths and Cycles with Direction Constrained Edges''

5.
Université de Montréal, Computer Science Colloquium, Oct. 26, 1999, ``La géométrie algorithmique et le déplacement d'un robot mobile''

6.
Universitá di Roma Tre, Rome, Italy, May 12, 1999, Dip. di Informatica e Automazione, Department Seminar: ``Bounded Radius of Curvature Motion Planning Problems''

7.
Université du Québec à Montréal, March 31, 1999, Computer Science Dept. Seminar: ``Planification des trajectoires de systémes articulés''

8.
University of British Columbia, Vancouver BC, Canada, Nov. 20, 1998, Computer Science Dept. Colloquium: ``Geometric Representations of Graphs''

9.
Simon Fraser University, Burnaby BC, Canada, Nov. 19, 1998, Computer Science Dept. Colloquiumr: ``Geometric Representations of Graphs''

10.
University of British Columbia, Vancouver BC, Canada, Nov. 18, 1998, Computer Science Dept. Colloquium: ``Bounded Radius of Curvature Motion Planning Problems''

11.
AT&T Laboratories, NJ, USA, May 22, 1998, ``Bounded Radius of Curvature Problems''

12.
Macalester College, St. Paul, Minnesota, USA, April 3, 1998, Dept. of Mathematics and Computer Science Seminar: ``Visibility Representations of Graphs''

13.
University of Newcastle, Callaghan, New South Wales, Australia, Dec. 5, 1997, Computer Science Dept. Colloquium: ``Bounded Radius of Curvature Problems''

14.
Dartmouth College, Hanover, New Hampshire, USA, Oct. 4, 1996, Mathematics Dept. Colloquium: ``The Logic Engine Approach to Geometric Lower Bounds''

15.
INRIA-Sophia Antipolis, France, Projet PRISME Seminar, May 7, 1996: ``New Results on the Reconfiguration of Chains''

16.
University of Newcastle, Callaghan, New South Wales, Australia, Computer Science Colloquium, Dec. 13, 1995: ``Robot Localization''

17.
Queen's University, Kingston, Ontario, Canada, Computer Science Colloquium, Nov. 3, 1995: ``Lower Bound Techniques for Geometric Representation Problems''

18.
Max Planck Institut für Informatik, Saarbrücken, Germany, Computer Science Colloquium, Sept. 15, 1995: ``Visibility Representations of Graphs''

19.
University of Rochester, Rochester NY, USA, Computer Science Seminar, Aug. 25, 1995: ``Visibility Representation of Graphs''

20.
Università di Roma ``La Sapienza'', Rome, Italy, Computer Science Colloquium, May 5, 1995: ``Robot Localization''

21.
Freie Universität-Berlin, Berlin, Germany, Computer Science Colloquium, March 29, 1995: ``Robot Localization''

22.
Universität zu Köln, Cologne, Germany, Center for Parallel Computing, Seminar, Feb. 10, 1995: ``Robot Localization''

23.
INRIA-Sophia Antipolis, France, KAFE seminar, Feb. 13, 1995: ``Geometric Problems for Graphs and Linkages''

24.
INRIA-Sophia Antipolis, France, Projet PRISME seminar, Jan. 24, 1995: ``Localizing a Robot with Minimum Travel''

25.
Universitat Politècnica de Catalunya (UPC), Barcelona, Spain, ALCOM8 Complexity Theory Group Seminar, Nov. 25, 1994: ``Complexity Results for Graph Representation''

26.
Universitat Politècnica de Catalunya (UPC), Barcelona, Spain, Applied Math II Computational Geometry Seminar, Nov. 23, 1994: ``Proximity Realizations of Graphs''

27.
Universdad Politècnica de Madrid, Spain, Computer Science Colloquium, Nov. 16, 1994: ``Geometric Representations of Graphs''

28.
Universitat Politècnica de Catalunya (UPC), Barcelona, Spain, Institute of Cybernetics Seminar, Nov. 11, 1994: ``Robot Localization''

29.
University of Rochester, Rochester NY, USA, Computer Science Dept. Colloquium, Oct. 3, 1994: ``Logic Engines and Proximity Graph Realizability''

30.
University of Rochester, Rochester NY, USA, Computer Science Dept., Introduction to Graduate Studies course, Sept. 23, 1994: ``The Joy of Research - a Case Study''

31.
University of Rochester, Rochester NY, USA, Computer Vision Seminar, Sept. 9, 1994: ``Minimum Spanning Trees''

32.
University of Rochester, Rochester NY, USA, Computer Vision Seminar, Aug. 31, 1994: ``Localizing a Robot with Minimum Travel''

33.
University of Newcastle, Callaghan, New South Wales, Australia, Computer Science Dept. Seminar, June 15, 1994: ``Graph Drawing in Three Dimensions''

34.
Tohoku University, Sendai, Japan, Computer Science Colloquium, Dec. 10, 1993: ``Drawing Graphs in Two Layers''

35.
Carleton College, Northfield, Minnesota, USA, Mathematics Dept. seminar/course, May 13, 1993: ``Motion Planning and Placement Planning for Linkages''

36.
University of Texas at Dallas, Richardson TX, USA, Computer Science Colloquium, May 11, 1993: ``Motion Planning and Placement Planning for Linkages''

37.
Udayana University, Singaraja, Bali, Indonesia, Mathematics Education Colloquium, July 9, 1992: ``Computational Geometry''

38.
Queen's University, Kingston, Ontario, Canada, Computer Science Colloquium, April 23, 1992: ``Algorithms for the Movement of Linkages''

39.
New York University, USA, Courant Institute Geometry Seminar, March 3, 1992: ``Algorithms for the Movement of Linkages''

40.
Université de Québec à Montréal, Montreal, Quebec, Canada, Computer Science, seminar/class, Nov. 11, 1991: ``Reconnaisance d'un ensemble d'articulation qui est une clique''

41.
Carleton University, Ottawa, Ontario, Canada, Computer Science Colloquium, Oct. 17, 1991: ``Circles in Boxes''

42.
McRCIM9. Montreal, Quebec, Canada, open house speaker, 1991-92: ``Reconfiguration of Linkages''

43.
University of Rochester, Rochester NY, USA, Computer Science Theory Seminar, Aug. 20, 1991: ``Algorithmic Motion Planning''

44.
McGill University, Montreal, Quebec, Canada, Student Undergraduate Mathematics Society, Oct. 31, 1990: ``Geometry and Motion Planning''

45.
University of Melbourne, Melbourne, Australia, Computer Science Dept. Colloquium, May 29, 1990: ``Motion Planning''

46.
University of Queensland, Brisbane, Australia, Dept. of Computer Science, May 1990: a mini-course series of six talks on motion planning

47.
University of Queensland, Brisbane, Australia, Computer Science Colloquium, May 22, 1990: ``Motion Planning''

48.
University of Rochester, Rochester NY, USA, Dept. of Computer Science, Aug. 1988: a series of three talks on motion planning:
Aug. 2: ``Computational Geometry and Motion Planning''; Aug. 9: ``Complexity Results in Motion Planning''; Aug. 16: ``Cell Decomposition and Motion Planning''

49.
University of Toronto, Ontario, Canada, Computer Science Dept. Colloquium, March 29, 1988: ``Geometric Motion Planning''

50.
York University, Toronto, Ontario, Canada, Mathematics and Computer Science Colloquium, Jan. 18, 1988: ``Geometric Motion Planning''

51.
Carleton University, Ottawa, Ontario, Canada, Computer Science Dept. Colloquium, Feb. 26, 1987: ``Default Positioning Problems for Composite Geometric Structures''

52.
McGill University, Montreal, Quebec, Canada, Cognitive Science Centre Seminar, March 11, 1987: ``Geometric Information in Machines and People''

53.
Smith College, Northampton, Massachusetts, USA, Mathematics Dept. Colloquium, April 23, 1985: ``A Survey of Motion Planning Techniques''

54.
Carleton University, Ottawa, Ontario, Canada, Computer Science Colloquium, Jan. 31, 1985: ``Motion Planning and Computational Geometry''

55.
Lehigh University, Bethlehem, Pennsylvania, USA, Mathematics Dept. Colloquium, Oct. 5, 1984: ``Motion Planning''

56.
Union College, Schenectedy NY, USA, Mathematics Dept. Colloquium, Feb. 1983: ``Motion Planning''

57.
Fitchburg State College, Massachusetts, USA, Public Lecture Series, May 1983: ``Motion Planning''

58.
Williams College, Williamstown, Massachusetts, USA, IBM Lecturer, April 1983: two lectures on robotics

59.
Cornell University, Ithaca NY, USA, Operations Research Dept. Colloquium, July 1982: ``Algorithmic Graph Theory and Perfect Graphs''

60.
University of Delaware, Newark, Delaware, USA, Computer Science Colloquium, May 1982: ``On Moving Robot Arms in 2-Dimensional Space''

61.
University of Delaware, Newark, Delaware, USA, Mathematics Dept. Colloquium, May 1982: ``A Method for Solving Certain Graph Recognition and Optimization Problems, with Applications to Perfect Graphs''

62.
State University of New York, Binghamton NY, USA, Mathematics and Computer Science Dept. Colloquium, March 1982: ``On Moving Robot Arms in 2-Dimensional Space''

63.
Cornell University, Ithaca NY, USA, Mathematics Dept. Geometry course, April 1982: ``Construction Techniques for Projective Planes''

64.
AT&T Bell Telephone Laboratories, Murray Hill, New Jersey, USA, seminar, April 1982: ``On Moving Robot Arms in 2-Dimensional Space''

65.
University of Nebraska, Lincoln, Nebraska, Computer Science Colloquium, Feb. 1982: ``On the Movement of Robot Arms''

66.
University of Nebraska, Lincoln, Nebraska, Mathematics Dept. Colloquium, Feb. 1982: ``Construction Techniques for Projective Planes''

67.
Cornell University, Ithaca NY, USA, Computer Science Seminar, Feb. 1982: ``Complexity Results for Moving Robot Arms''

68.
McGill University, Montreal, Quebec, Canada, Computer Science Seminar, Feb. 1982: ``Finding Clique Cut Sets''

69.
McGill University, Montreal, Quebec, Canada, Computer Science Seminar, Feb. 1982: ``Recognizing i-Triangulated Graphs''

70.
Wellesley College, Wellesley, Massachusetts, USA, Mathematics Dept. Colloquium, May 1980: ``Linear Programming''

71.
Williams College, Williamstown, Massachusetts, USA, Mathematics Colloquium, 1979: ``Linear Programming''

72.
McGill University, Montreal, Quebec, Canada, Computer Science Colloquium, Nov. 1978: ``Linear Programming''

73.
University of Rochester, Rochester NY, USA, Mathematics Dept. Colloquium, March 1977: ``Projective Planes''

74.
Princeton University, Princeton, New Jersey, USA, Mathematics Colloquium, April 1976: ``Projective Planes''

75.
MIT, Cambridge, Massachusetts, USA, Applied Mathematics Colloquium, Oct. 1975: ``Projective Planes''






U.S. Patent Applications


- for ``Graph Multi-drawing'', based on ideas described in item 5 (Biedl et al.) in the Selective Conference Proceedings section.

- for ``Three Dimensional Microstructures'', based on ideas described in item 5 (Jackman et al.) under Refereed Journal Articles.



Professional Societies10


American Mathematical Society (AMS)
Mathematical Association of America (MAA)
Society of Industrial and Applied Mathematics (SIAM)
Association for Computing Machinery (ACM)
Association for Women in Mathematics (AWM)
Institute of Electrical and Electronics Engineers (IEEE)
IEEE Computer Society

Reviewing for Journals


Algorithmica
Algebras, Groups and Geometries
The American Mathematical Monthly
Ars Combinatoria
Discrete Applied Mathematics
Discrete and Computational Geometry
Discrete Mathematics
European J. Combinatorics
IEEE Transactions on CAD/ICAS
IEEE Transactions on Pattern Matching and Machine Intelligence
Information and Computation
Information Processing Letters
Intelligence
International Journal of Computational Geometry and Applications
Discrete Mathematics
IEEE J. of Robotics and Automation
J. Algorithms
J. Combinatorial Theory, series A
J. Combinatorial Theory, series B
J. Computation Geometry, Theory and Applications
J. of Information and Computation
Information Processing Letters
Les Annales des Sciences Mathématiques du Québec
Rocky Mountain J. of Mathematics
SIAM J. on Computing
SIAM J. Discrete Mathematics
The Visual Computer
Theoretical Computer Science



Manuscript reviewer for Harvard University Press




Reviewing for Government Agencies

$\bullet$ FCAR: reviewer for proposals submitted to the program ``Actions spontaneées''

$\bullet$ NSERC: reviewer of research grant proposals

$\bullet$ Reviewer of the Queen's University School of Computer Science for the Ontario Council of Graduate Studies, Nov. 2000

$\bullet$ NSF: reviewer of research grant proposals (Algebra and Number Theory Program, including combinatorics; Computer Science Program, Program on Advanced Computational Research)

$\bullet$ Israeli National Science Foundation: proposals for research centre grants






External Thesis Examination



$\bullet$ Member, NSERC Doctoral Prize Selection Committee, Ottawa, Dec. 2000

$\bullet$ External examiner for Ph.D. thesis of David Wood, Monash University, Australia, ``Three-Dimensional Orthogonal Graph Drawing'', June, 2000.

$\bullet$ External examiner for Ph.D. thesis of Qingwen FENG, University of Newcastle, Australia, ``Algorithms for Drawing Clustered Graphs'', 1997. This thesis won the Australian Computing Society's prize for Ph.D. thesis of the year for 1997.

$\bullet$ External examiner (Rapporteur), candidat de doctorat, Sylvain Lazard, l'Université Paris VI (Paul et Marie Curie), ``Planification de trajectoires de robots nobiles non-holonomes et de robots à pattes'', May 9, 1996

$\bullet$ External examiner, Ph.D. thesis of Giuseppe Liotta, student of Giuseppe Di Battista, University of Rome ``La Sapienza'', title ``Computing Proximity Drawings of Graphs'', 1994. This thesis won the European Association for Theoretical Computer Science (EATCS) award for best Italian Ph.D. thesis in theoretical computer science, 1994-95.

$\bullet$ External examiner, Ph.D. thesis of Kelly Lyons, student of David Rappaport, Queen's University, ``Cluster Busting in Anchored Graph Drawing'', 1994

$\bullet$ External examiner, Ph.D. thesis of Xuemin LIN, University of Queensland, Australia, ``Analysis of Algorithms for Drawing Graphs'', 1992

$\bullet$ External examiner, M.Sc. thesis of Michael D. Junkin, student of Derek Corneil, University of Toronto, ``Clique Perfect Graphs'', May 1988

$\bullet$ External examiner, Ph.D. thesis of Augustine M. Moshi, student of Brian Mortimer, Department of Mathematics and Statistics, Carleton University, Canada, ``Matching and Stable Cutsets in Graphs'', August 12, 1987




Professional Society Activities


$\bullet$ ACM Strategic Directions Conference, Workgroup on Computational Geometry, MIT, Cambridge, Massachusetts, USA, June 14-15, 1996, 50th anniversary of the ACM, report on Computational Geometry

$\bullet$ AMS IMS11 and SIAM: Committee on Joint Summer Research Conferences, such as the 10 year retrospective conference on computational geometry: 1992-96

$\bullet$ SIAM Visiting Lectureship Program, 1981, 1982

$\bullet$ MAA
- National Membership Committee, 1980-1983
- Chair, Program Committee, New England Section Meeting, Williamstown MA, USA, June 1980

$\bullet$ NSF Panelist, NSF Spectrum of Careers for Women in Science Conference, Williams College, Williamstown MA, USA, April 12, 1980

$\bullet$ SWE Society for Women in Engineering, faculty co-sponsor of the charter chapter of SWE at Tufts University, USA, 1975-76

$\bullet$ IEEE Secretary, student chapter, Stanford University 1967-69



Organization of Major Conferences


$\bullet$ General Conference Chair, GD '98, Montreal, Canada, August 13-15, 1998. This is in addition to being chair of the program committee.

$\bullet$ Organizing Committee, 10th CCCG (Canadian Conference on Computational Geometry), Montreal, Canada, August 10-12, 1998

$\bullet$ General Conference Chair, WADS '93, Workshop12 on Algorithms and Data Structures '93

Organization of Small Workshops13


$\bullet$ Organizer, International Workshop on Fixed Parameter Tractability in Geometry and Graph Drawing, Bellairs Research Institute of McGill University, Barbados, February 9-16, 2001.


$\bullet$ Organizer, International Workshop on Similarity Measurement, Bellairs Research Institute of McGill University, Barbados, February 6 - 12, 1999.


$\bullet$ Organizer, International Workshop on Applications of Rigidity Theory to Motion Planning, Bellairs Research Institute of McGill University, Barbados, January 28 - February 4, 2000, invited speaker: Robert Connelly, Cornell U.

$\bullet$ Organizer, International Workshop on Similarity Measurement, Bellairs Research Institute of McGill University, Barbados, February 6 - 12, 1999

$\bullet$ Co-organizer, with A. Lubiw (U. Waterloo), International Workshop on Wrapping and Folding, Bellairs Research Institute of McGill University, Barbados, January 30 - February 6, 1998

$\bullet$ Organizer, International Workshop on Bounded Radius of Curvature Problems, Bellairs Research Institute of McGill University, Barbados, March 9-16, 1997

$\bullet$ Organizer, International Workshop on 3-Dimensional Graph Drawing, Bellairs Research Institute of McGill University, Barbados, February, 1996

$\bullet$ Co-organizer, with David Rappaport (Queen's U.), of an International Workshop on Geometric Representations of Graphs, Bellairs Research Institute of McGill University, Barbados, February 11-18, 1994

$\bullet$ Co-organizer, with Joan Hutchinson (Macalester College, MN), of an International Workshop on Visibility Representation, Bellairs Research Institute of McGill University, Barbados, February 1993

$\bullet$ Organizer, International Workshop on Algebraic Computational Geometry, Bellairs Research Institute of McGill University, Barbados, Shreeram Abhyankar, Marshall Distinguished Professor of Mathematics and Industrial Engineering, Purdue University, invited speaker, February 12-19, 1988




next up previous
Next: About this document ...
Prof. Sue WHITESIDES
2001-03-17