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: 228605376 
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 5143987071 (CS Office) +15143987080 (my office) 
fax: 
+1 5143983883 
EDUCATION 


M.Sc. 1969 
Electrical Engineering
(combined undergraduateM.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 
199495 
Visiting Researcher 

Institut National de Recherche en Informatique et en
Automatique 

I.N.R.I.A.Sophia Antipolis, France 
198788 
Visiting Associate Professor, Department of
Computer Science 

University of Toronto 
198182 
Visiting Assistant Professor,
Department of Computer
Science 

Cornell University NY, USA 
197783 
Assistant Professor (Associate Professor 1983) 

Department of Mathematics,
Dartmouth College NH, USA 
197577 
Assistant Professor,
Mathematics Department 

Tufts University MA, USA 
Summary^{1}
of Courses Taught
McGill Courses
189240 
Mathematics for Computer Science 
308360 
Algorithms 
308426 
Automated Reasoning 
308506 
Advanced Analysis of Algorithms 
308560 
Graph Algorithms 
308531 
Theory of Computation 
308648 
Motion Planning 
308761 
Topics: Fundamentals of Geometric Reasoning 
308761 
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
Summary^{2} of Postgraduate Student Supervision
Postdoctoral Fellows
David Wood 
2001 
Therese Biedl 
199799 
Sylvain Lazard 
199698 
Kathleen Romaniki 
199294 
Mark van Kreveld 
199293 
Hazel Everett 
198991 
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 
JeanFranç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, threedimensional,
metallic structures'', J. of Physical Chemistry B, vol. 105, no. 2,
2001, pp. 347350.
 2.
 H. Wu, S. Britain, J. Andersen, B. Grzybowski, S. Whitesides, and G.
Whitesides,
``Fabrication of Topologically Complex ThreeDimensional Microstructures:
Metallic Microknots'', J. Am. Chem. Soc., vol. 122, no. 51,
2000, pp. 1269112699.
 3.
 P. Eades, A. Symvonis, and S. Whitesides, ``Threedimensional orthogonal
graph drawing algorithms'',
Discrete Applied Mathematics, vol. 103, no. 13, 15 July 2000,
pp. 5587.
 4.
 J. Anderson, D. Chiu, C. McDonald, H. Wu, S. Whitesides,
and G. Whitesides, ``Fabrication of topologically complex
threedimensional microfluidic systems in PDMS by rapid
prototyping'',
Analytical Chemistry (American Chemical Society), vol. 72, no. 14,
2000, pp. 31583164.
 5.
 R. Jackman, S. Brittain, A. Adams, H. Wu, M. Prentiss, S.
Whitesides and G. Whitesides, ``Threedimensional metallic
microstructures fabricated by soft lithography and
microelectrodeposition'', Langmuir (American
Chemical Society), vol. 15, 826836, 1999.
 6.
 T. Biedl, T. Shermer, S. Whitesides and S. Wismath,
``Orthogonal 3D Graph Drawing'', J. Graph Algorithms
and Applicaions, vol. 3, no. 4, pp. 6379, 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 kBall in a dDimensional Box'', Computational
Geometry, Theory and Applications, vol. 11, 5967, 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. 116, 1998.
 9.
 Paul Kruszewski and Sue Whitesides, ``A General
Random Combinatorial
Model of Botanical Trees,''
J. Theoretical Biology, vol. 191, pp. 221236, 1998.
 10.
 Gregory Dudek, Kathleen Romanik and
Sue Whitesides, ``Localizing a Robot with
Minimum Travel'', SIAM J. on
Computing, vol. 27, no. 2, pp. 583604, 1998.
 11.
 H. Alt, M. Godau and S. Whitesides,
``A Universal 3Dimensional 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. 111125, 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. 122, 1998.
 13.
 Paul Tanenbaum and Sue Whitesides, ``Simultaneous
Dominance Representation of
Multiple Posets'', Order, vol. 13, pp. 351364, 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. 591606, 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. 97103.
 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. 2337.
 17.
 P. Eades and S. Whitesides,
``The Realization Problem
for Euclidean Minimum Spanning Trees is NPHard'',
Algorithmica vol. 16, no. 1, July 1996,
pp. 6082.
 18.
 M. van Kreveld, J. Snoeyink and S. Whitesides,
``Folding Rulers Inside Triangles'', Discrete
and Computational Geometry vol. 15, 1996, pp. 265285.
 19.
 W. Lenhart and S. Whitesides,
``Reconfiguring Closed Polygonal Chains
in Euclidean dSpace'',
Discrete and Computational Geometry,
vol. 13, 1995, pp. 123140.
 20.
 P. Eades and S. Whitesides, ``Drawing Graphs in
Two Layers'', Theoretical Computer Science
vol. 131, 1994, pp. 361374.
 21.
 S. Bellantoni, I. BenArroyo Hartman, T. Przytycka and
S. Whitesides, ``Grid Intersection Graphs and
Boxicity,'' Discrete Mathematics vol. 114,
1993, pp. 4149.
 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. 4250.
 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. 281293.
 24.
 Sue Whitesides, ``Computational Geometry
and Motion Planning'', invited, refereed chapter of
original material not appearing elsewhere, in
Computational Geometry, G. Toussaint, ed.,
SpringerVerlag, 1985, pp. 377427.
 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. 564578.
 26.
 J. Hopcroft, D. Joseph, and S. Whitesides,
``On the Movement of Robotic
Arms in 2Dimensional Bounded Regions'', SIAM J.
on Computing
vol. 14, May 1985,
pp. 315333.
 27.
 S. H. Whitesides, ``A Classification
of Certain Graphs with Minimal
Imperfection Properties'', Annals of Discrete Math.
vol. 21, 1984, pp. 281297.
 28.
 J. Hopcroft, D. Joseph, and S. Whitesides, ``Movement
Problems for
2Dimensional Linkages'', SIAM J. on Computing vol.
13, Aug. 1984, pp. 610629.
 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. 281297.
 30.
 S. H. Whitesides, ``Edgecolored Complete
Graphs with Alternating Cycles'',
Discrete Math. vol. 46, 1983, pp. 299304.
 31.
 S. H. Whitesides, ``A Classification of Graphs with Certain Minimal
Imperfection Properties'', Discrete Math. vol.
38, 1982, pp. 303310.
 32.
 S. H. Whitesides, ``An Algorithm for Finding
Clique Cutsets'', Information
Processing Letters vol. 12, 1981, pp. 3132.
 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. 8392.
 34.
 S. H. Whitesides, ``Collineations of
Projective Planes of Order 10, Part
II'', J. Combinatorial Theory A,
vol. 26, 1979, pp.
269277.
 35.
 S. H. Whitesides, ``Collineations of
Projective Planes of Order 10, Part I '',
J. Combinatorial Theory A vol. 26, 1979, pp. 249268.
 36.
 Joan Hutchison and S. H. Whitesides, ``On a generalized
regularity condition'', Theory and Application of Graphs,
Lecture Notes in Mathematics vol. 642, SpringerVerlag, Berlin, 1978,
pp. 304308.
Book Chapters
J. Hopcroft, D. Joseph and S. Whitesides,
``On the Movement of Robot Arms in
2Dimensional Bounded Regions'', in
Planning, Geometry and Complexity of
Robot Motion, J. Schwartz, M. Sharir and
J. Hopcroft, eds., Ablex
Publishing Corp., 1987, pp. 304329. (reprinted from [26])
J. Hopcroft, D. Joseph and S. Whitesides,
``Movement Problems for 2Dimensional Linkages'',
in Planning, Geometry and Complexity of
Robot Motion, J. Schwartz, M. Sharir
and J. Hopcroft, eds., Ablex
Publishing Corp, 1987, pp. 282303. (reprinted from [28])
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. 197206, (reprinted from [33])
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.
281298 (reprinted from [29])
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. 207218 (reprinted from [31])
Edited Works
J. of Graph Algorithms and Applications, Special Issue
on Advances in Graph Drawing, G. Liotta and S. Whitesides, eds.,
vol. 4, no. 3, 2000.
Graph Drawing. Sue Whitesides ed, SpringerVerlag
LNCS vol. 1547, 1998.
Data Structures and Algorithms (WADS '93). F. Dehne, JR. Sack,
N. Santoro and S. Whitesides, eds., SpringerVerlag
LNCS, 1993.
Papers in Proceedings of Selective^{3}
Conferences
 1.
 Vida Dujmovic and Sue Whitesides, ``On Validating Planar Worlds'',
Proc. of the Twelfth Annual ACMSIAM 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),
SpringerVerlag, LNCS series, vol. 1984, pp. 272283.
 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), SpringerVerlag,
LNCS series, vol. 1858, pp. 6473.
 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 ACMSIAM Symposium on Discrete
Algorithms (SODA), Baltimore MD, USA,
Jan. 1999, pp. 866867. (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. 1315, 1998,
SpringerVerlag LNCS series, vol.
1547, pp. 347355.
 6.
 P. Agarwal, T. Biedl, S. Lazard, S. Robbins, S. Suri and S. Whitesides,
``CurvatureConstrained Shortest Paths in a Convex Polygon'',
Proc. of the ACM Fourteenth Annual Symposium on Computational Geometry,
Minneapolis, Minnesota, USA, June 710, 1998, published by the ACM,
pp. 392401.
(talk given by Whitesides)
 7.
 T. Biedl, T. Shermer, S. Whitesides and S. Wismath, ``Orthogonal
3D Graph Drawing'', in Proc. of the
Fifth International Symposium on Graph Drawing, GD '97,
Sept. 1820, 1997, Rome, Italy, G. Di Battista, ed.,
SpringerVerlag Lecture Notes in Computer Science LNCS vol. 1353,
pp. 7686. (talk
given by Wismath)
 8.
 S. Fekete, M. Houle and
S. Whitesides, ``The Wobbly Logic Engine: Proving
Hardness of Nonrigid Geometric Graph Representation Problems'',
in Proc. of the
Fifth International Symposium on Graph Drawing, GD '97,
Sept. 1820, 1997, Rome, Italy, G. Di Battista, ed.,
SpringerVerlag Lecture Notes in Computer Science LNCS vol. 1353,
pp. 272283. (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. 1820, 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 1719, 1996, JY Cai and CK Wong, eds.),
SpringerVerlag Lecture Notes in Computer
Science LNCS vol. 1090, pp. 381390. (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. 2022, 1995, F. Brandenburg, ed.,
SpringerVerlag, Lecture Notes in Computer Science
LNCS vol. 1027, pp. 178189. (talk given by Whitesides)
 12.
 H. Alt, M. Godau and S. Whitesides,
``A Universal 3Dimensional Visibility Representation
for Graphs'',
in Graph Drawing,
Proc. of the
Symposium on Graph Drawing, GD '95, Passau, Germany,
Sept. 2022, 1995, F. Brandenburg, ed.,
SpringerVerlag, Lecture Notes in Computer Science
LNCS vol. 1027, pp. 819. (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. 2022, 1995, F. Brandenburg, ed.,
SpringerVerlag, Lecture Notes in Computer Science
LNCS vol. 1027, pp. 234241. (talk given by Fekete)
 14.
 P. Eades and S. Whitesides, ``Nearest
Neighbor Graph Realizability is NPhard,'' in
Theoretical Informatics, Proc. of LATIN '95, Valparaiso,
Chile, April 37, 1995,
SpringerVerlag, Lecture Notes in Computer
Science LNCS vol. 911, pp. 245256.
(talk given by Whitesides)
 15.
 G. Dudek, K. Romanik and
S. Whitesides, ``Localizing a Robot with
Minimum Travel'' in Proc. of the
Sixth Annual ACMSIAM Symposium on Discrete
Algorithms (SODA), San Francisco CA, USA,
Jan. 2224, 1995, pp. 437446.
(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. 1012, 1994,
SpringerVerlag Lecture Notes in Computer Science
LNCS vol. 894, pp. 352363. (talk given by Meijer)
 17.
 P. Eades and S. Whitesides, ``The Realization Problem
for Euclidean Minimum Spanning Trees is NPhard'', in
Proc. of the ACM Tenth Annual Symposium on
Computational Geometry, SUNY Stony Brook, Stony Brook, NY,
USA, June 68, 1994, pp. 4956. (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 2529,
1992, T. Catarci, M. F.
Costabile & S. Levialdi, eds.. World Scientific
Series in Computer Science vol. 36, 1992, pp. 395410. (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. 110.
(talk given by Lenhart)
 20.
 J. Hopcroft, D. Joseph and S. Whitesides, ``On the
Movement of Robot Arms
in Twodimensional Bounded Regions'', in
Proc. of the IEEE 23^{rd} Annual
Symposium on the Foundations of
Computer Science (FOCS), Chicago IL, USA,
Nov. 35, 1982, pp. 280289. (talk given
by Whitesides)
Papers in Proceedings of Nonselective^{4}
Conferences

 1.
 H. Everett, S. Lazard, S. Robbins, H. Schrø:der and S.
Whitesides, ``Convexifying Starshaped Polygons'',
in Proc. of the Tenth Canadian Conference on
Computational Geometry CCCG '98, McGill University,
Montreal, Canada, Aug. 1012, 1998, pp. 23.
 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. 1012, 1998, pp. 45.
 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. 1012, 1998, pp. 7071.
 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. 1114, 1997, pp. 1116. (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. 1215, 1996, pp. 161166. (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.
510,
1993, pp. 187191. (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. 510, 1993, pp.
16. (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. 1014, 1992, pp. 198203. (talk given by Whitesides)
 9.
 W. J. Lenhart and S. H. Whitesides,
``Turning a Polygon Insideout," in Proc. of the
Third
Canadian Conference on Computational Geometry, Vancouver,
British Columbia,
Canada, Aug. 610, 1991, pp. 6669. (talk given by Whitesides)
 10.
 H. Everett and S. Whitesides, ``Finding all the Largest
Circles in a 3Dimensional Box'', in Proc. of the
Third Canadian Conference on Computational Geometry,
Vancouver, British Columbia,
Canada, Aug. 610, 1991, pp. 8487. (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. 610, 1990,
pp. 362365. (talk given by Whitesides)
 12.
 S. Whitesides, K. Abadjian, P. Hum, and N. Rodjanapiches,
``Computeraided Instruction for a
Theorem in Geometry'', in Proc. of the
ISMM^{5} 30^{th}
International Symposium on Mini and Microcomputers and their
Applications,
Montreal, Quebec, Canada, June 35, 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. 304308. (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. 912,
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. 3637
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 Whitesides^{6} at
Harvard University. The chemists describe their techniques to me, and pose
questions of an openended 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.
[WB00] H. Wu, S. Britain, J. Andersen, B. Grzybowski, S. Whitesides, and G.
Whitesides,
``Fabrication of Topologically Complex ThreeDimensional Microstructures:
Metallic Microknots'', J. Am. Chem. Soc., vol. 122, no. 51,
2000, pp. 1269112699.
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 nonselfintersecting
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 topologyshapemetrics 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.
[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), SpringerVerlag,
LNCS series, vol. 1858, pp. 6473.
[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),
SpringerVerlag, LNCS series, vol. 1984, pp. 272283.
Paper [ESW00] below studies tradeoffs between bend minimization and volume
minimization for 3D rectilinear layouts of graphs, and provides two methods for
3D layout.
[ESW00]
P. Eades, A. Symvonis, and S. Whitesides, ``Threedimensional orthogonal
graph drawing algorithms'',
Discrete Applied Mathematics, vol. 103, no. 13, 15 July 2000,
pp. 5587.
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.
[AGW98] Alt, M. Godau and S. Whitesides,
``A Universal 3Dimensional 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. 111125, 1998.
Paper [EW96a] below gives a paradigm for proving NPhardness 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.
[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. 2337.
Paper [EW96b] below proves that it is NPhard 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.
[EW96b] P. Eades and S. Whitesides,
``The Realization Problem
for Euclidean Minimum Spanning Trees is NPHard'',
Algorithmica vol. 16, no. 1, July 1996,
pp. 6082.
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.
[AB+] P. Agarwal, T. Biedl, S. Lazard, S. Robbins, S. Suri and S. Whitesides,
``CurvatureConstrained Shortest Paths in a Convex Polygon'',
Proc. of the ACM Fourteenth Annual Symposium on Computational Geometry,
Minneapolis, Minnesota, USA, June 710, 1998, published by the ACM,
pp. 392401.
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 selfsimilar
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 ACMSIAM 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.
[DRW98] Greg Dudek, Kathleen Romanik, and
Sue Whitesides, ``Localizing a Robot with
Minimum Travel'', SIAM J. on
Computing, vol. 27, no. 2, pp. 583604, 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 noncrossing 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.
[LW95] W. Lenhart and S. Whitesides,
``Reconfiguring Closed Polygonal Chains
in Euclidean dSpace'',
Discrete and Computational Geometry,
vol. 13, 1995, pp. 123140.
Technical Report [WZ00] below formed part of the Ph.D. thesis of my student
Rongyao Zhao. It generalizes a wellknown 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. 5971. 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.
[WZ00] Sue Whitesides and Rongyao Zhao, ``Kadmissible 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 198182, 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.
[HJW85] J. Hopcroft, D. Joseph, and S. Whitesides,
``On the Movement of Robotic
Arms in 2Dimensional Bounded Regions'', SIAM J.
on Computing
vol. 14, May 1985,
pp. 315333.
Paper [HJW84] studies arbitrary planar linkages and shows that a
reachability
problem for them is PSPACEhard. It was among the very early lower bound
results in algorithmic motion planning.
[HJW84] J. Hopcroft, D. Joseph, and S. Whitesides, ``Movement
Problems for
2Dimensional Linkages'', SIAM J. on Computing vol.
13, Aug. 1984, pp. 610629.
Perfect Graphs
The next two papers represent my interest in the famous ``perfect graph''
conjecture of Claude Berge, a longstanding, 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. 221232, 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].
[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. 281297.
[Wh81] S. H. Whitesides, ``An Algorithm for Finding
Clique Cutsets'', Information
Processing Letters vol. 12, 1981, pp. 3132.
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 BruckRyser 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 nonprimepower order has now been open for over fifty years.
[Wh79] S. H. Whitesides, ``Collineations of
Projective Planes of Order 10, Part
II'', J. Combinatorial Theory A,
vol. 26, 1979, pp.
269277.
(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 axisaligned 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.
[ES+98] I. Stojmenovic, S. Whitesides and P. Valtr,
``The Largest kBall in a dDimensional Box'', Computational
Geometry, Theory and Applications, vol. 11, 5967, 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. 3958. 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 nonexistence of a certain Steiner system
S(3,12,122)'', J. Combinatorial Theory A, vol. 30 (3), 1981, pp. 209236.
* 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. 221232, 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, SpringerVerlag, 1992.
* The book ``Robot Motion Planning'' by JeanClaude Latombe, Kluwer, Boston,
1991 includes a section (pp. 234242) 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, SpringerVerlag, 1985, pp. 377427.
* 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 multidrawing 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, ``"3D geometry adds twist to microfabrication'';
and Chemical and Engineering News, pp. 3637, 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. 810, 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. 1519, 1999.
 NSERC
 Member,
NSERC Grant Selection Committee, Computer
Science, Ottawa 199899
 GD
 Chair, Program Committee, GD '98 (Graph Drawing '98),
Montreal, Canada, August 1315, 1998. Conference
proceedings published in the SpringerVerlag
LNCS series as vol. 1547
 CCCG
 Member, Organizing and
Program Committees, Tenth Canadian Conference
on Computational Geometry, Montreal, Aug. 1012, 1998
 CATS
 Member, Program Committee, CATS '98 (Computing  the Australasian
Theory Symposium), Perth, Australia, February 23, 1998
 NSERC
 Member,
NSERC Grant Selection Committee, Computer
Science, Ottawa, 199798
 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 1214, 1997
 NSERC
 Member,
NSERC Grant Selection Committee, Computer
Science, Ottawa, 199697
 ACM
 Member, Program Committee,
ACM Twelfth Annual Symposium
on Computational Geometry, Philadelphia USA, May 2426, 1996.
Proceedings published by the Association
for Computing Machinery.
 ISAAC
 Member, Program Committee, ISAAC '95 (Sixth Annual
International Symposium on Algorithms and Computation),
December 46, 1995, Cairns, Australia.
SpringerVerlag LNCS series vol. 1004
 WADS
 Member, Program Committee, Fourth International
Workshop on Algorithms and Data Structures (WADS '95),
Kingston, Canada, August 1618, 1995.
SpringerVerlag LNCS
series vol. 955
 GD
 Member, Program Committee, DIMACS International
Symposium on Graph Drawing, GD '94,
Princeton NJ, USA. Oct. 1012, 1994.
SpringerVerlag
LNCS series vol. 894
 WADS
 Chair, and member of program committee, Workshop
on Algorithms and Data Structures '93 (WADS '93),
Montreal, August 1113, 1993.
SpringerVerlag LNCS series vol. 709
 CCCG
 Member, program committee, Fourth Canadian Conference
on Computational Geometry, St. John's, Newfoundland,
Canada, August 1014, 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. 1921, 2001, Christchurch,
New Zealand
 2.
 Invited hour address Twelfth Australasian Workshop on
Combinatorial Algorithms (AWOCA 2001), Bandung, Indonesia,
July 1417, 2001
 3.
 DSRC/DARPA Workshop on SelfAssembly in Manufacturing, Arlington VA, USA,
Dec. 67, 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 1215, 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 47, 2000: ``Geometry in Motion:
a Survey of Linkage Movement Problems''
 6.
 Invited series of 3 hour talks The Fields Institute,
Toronto, Minisymposium on Geometric Representations of Graphs organized by
Petr Hlineny, April 1114, 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 24^{th} Australasian
Conference on Combinatorial Mathematics and Combinatorial
Computingi (ACCMCC '99), Northern Territory University,
Darwin, Australia, July 59, 1999: ``Geometric
Representations of Graphs''
 8.
 Workshop on Graph Algorithms,
Schloss Dagstuhl International Conference
and Research Centre for Computer
Science, July 2631, 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 1215, 1998:
``Graph Visibility''.
 10.
 Invited hour address
CoNE Conference (Combinatorics of New England  a series
of NSF sponsored oneday 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 coauthor N. Pei.
 12.
 Ph.D. Centennial Conference,
Department of Mathematics, University of Wisconsin, Madison,
Wisconsin, May 2124, 1997, invited 20 minute talk,
MiniSymposium 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. 56, 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 1317, 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. 30Dec. 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 29July 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. 2428, 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 15, 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, Mathassociates^{7},
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.
 INRIASophia 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ätBerlin, 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.
 INRIASophia Antipolis, France, KAFE seminar, Feb. 13, 1995:
``Geometric Problems for Graphs and Linkages''
 24.
 INRIASophia Antipolis, France,
Projet PRISME seminar, Jan. 24, 1995:
``Localizing a Robot with Minimum Travel''
 25.
 Universitat Politècnica de Catalunya (UPC),
Barcelona, Spain,
ALCOM^{8} 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.
 McRCIM^{9}. Montreal, Quebec, Canada, open house speaker, 199192: ``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 minicourse 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 2Dimensional 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 2Dimensional 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 2Dimensional 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 iTriangulated 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 Multidrawing'', 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 Societies^{10}
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
FCAR:
reviewer for proposals
submitted to the program ``Actions spontaneées''
NSERC: reviewer of research grant proposals
Reviewer of the Queen's University School of Computer Science
for the Ontario Council of Graduate Studies, Nov. 2000
NSF: reviewer of research grant proposals (Algebra and Number Theory
Program, including combinatorics; Computer Science Program,
Program on Advanced Computational Research)
Israeli National Science Foundation: proposals for research centre
grants
External Thesis
Examination
Member, NSERC Doctoral
Prize Selection Committee, Ottawa, Dec. 2000
External examiner for Ph.D.
thesis of David Wood, Monash University,
Australia, ``ThreeDimensional Orthogonal Graph Drawing'', June, 2000.
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.
External examiner (Rapporteur), candidat de doctorat,
Sylvain Lazard, l'Université Paris VI (Paul
et Marie Curie), ``Planification de trajectoires de robots
nobiles nonholonomes et de robots à pattes'', May 9, 1996
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, 199495.
External examiner, Ph.D. thesis of Kelly Lyons,
student of David Rappaport, Queen's
University, ``Cluster Busting in Anchored Graph
Drawing'', 1994
External examiner, Ph.D. thesis of Xuemin LIN, University
of Queensland, Australia, ``Analysis of Algorithms
for Drawing Graphs'', 1992
External examiner, M.Sc. thesis of Michael D. Junkin,
student of Derek Corneil, University of Toronto,
``Clique Perfect Graphs'', May 1988
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
ACM Strategic Directions Conference, Workgroup
on Computational Geometry, MIT, Cambridge,
Massachusetts, USA, June 1415, 1996,
50^{th} anniversary of the ACM, report
on Computational Geometry
AMS
IMS^{11} and SIAM:
Committee on Joint Summer Research
Conferences,
such as the 10 year
retrospective conference on computational geometry:
199296
SIAM Visiting Lectureship Program, 1981, 1982
MAA
 National Membership Committee, 19801983
 Chair, Program Committee, New England Section
Meeting, Williamstown MA, USA, June 1980
NSF Panelist, NSF Spectrum of Careers for
Women in Science Conference, Williams
College, Williamstown MA, USA, April 12, 1980
SWE Society for Women in Engineering, faculty cosponsor
of the charter chapter of SWE at Tufts University, USA,
197576
IEEE Secretary,
student chapter, Stanford University 196769
Organization of Major Conferences
General Conference Chair, GD '98, Montreal, Canada,
August 1315, 1998. This is in addition to being chair of
the program committee.
Organizing Committee, 10^{th} CCCG (Canadian Conference
on Computational Geometry), Montreal, Canada, August
1012, 1998
General Conference Chair, WADS '93,
Workshop^{12} on Algorithms and Data Structures '93
Organization of Small Workshops^{13}
Organizer, International Workshop on Fixed Parameter
Tractability in Geometry and Graph Drawing,
Bellairs Research Institute of McGill University, Barbados,
February 916, 2001.
Organizer, International Workshop on Similarity Measurement,
Bellairs Research Institute of McGill University, Barbados,
February 6  12, 1999.
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.
Organizer, International Workshop on Similarity Measurement,
Bellairs Research Institute of McGill University, Barbados,
February 6  12, 1999
Coorganizer, with A. Lubiw (U. Waterloo), International
Workshop on Wrapping and Folding,
Bellairs Research Institute of McGill University, Barbados,
January 30  February 6, 1998
Organizer, International Workshop on Bounded Radius of
Curvature Problems,
Bellairs Research Institute of McGill University, Barbados,
March 916, 1997
Organizer, International Workshop on 3Dimensional
Graph Drawing,
Bellairs Research Institute of McGill University, Barbados,
February, 1996
Coorganizer, with
David Rappaport (Queen's U.), of an International
Workshop on Geometric Representations of Graphs,
Bellairs Research Institute of McGill University, Barbados,
February
1118, 1994
Coorganizer, with Joan Hutchinson (Macalester College, MN), of an International
Workshop on Visibility Representation,
Bellairs Research Institute of McGill University, Barbados,
February 1993
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 1219, 1988
Next: About this document ...
Prof. Sue WHITESIDES
20010317