Curriculum Vitæ - William J. Lenhart

Address

Department of Computer Science

Williams College

Williamstown, MA 01267

Phone (Office): (413)-597-2371

Phone (Home): (802)-823-0268

Research Interests

Graph Theory, Graph Drawing, Computational Geometry, Graph and Combinatorial Algorithms.

Education

Ph.D., Department of Mathematics, Dartmouth College, Hanover, NH, 1983,
Dissertation: Automorphism Groups of Block Designs

A.M., Department of Mathematics, Dartmouth College, Hanover, NH, 1979

B.S., Department of Mathematics, St. Joseph's College, Philadelphia, PA, 1977

Professional Experience

Chair of Department of Computer Science, Williams College, 2001-02, 1998-00 and 1990-92

Professor of Computer Science and Mathematics, Williams College, 1995-present.

Associate Professor of Computer Science and Mathematics,, Williams College, 1989-1995

Visiting Scholar, School of Computer Science, McGill University, 1992-93.

Visiting Scholar, Dept. of Computer Science, University of Newcastle, New South Wales, Fall 1992.

Assistant Professor of Mathematical Sciences,, Williams College, 1982-1989

Visiting Scholar, School of Computer Science, McGill University, 1985-86.

Awards and Grants

Investigator for NSF REU grant to support student research in Mathematics and Computer Science 1988, 1989.

Williams College Class of 1941 Fellowship for Assistant Professor leave, 1985.

Sloan grant through Williams College to design and teach a one week intensive course for faculty on applications of computers to research and teaching, summers of 1983, 1984.

Sloan grant through Williams College to redesign introductory Computer Science courses and create new Discrete Mathematics course, summers of 1983, 1984.

Publications

W. Lenhart, and C. Umans, ``Hamiltonian Cycles in Solid Grid Graphs'', in preparation.

W. Lenhart, and R. Hayward, ``Bichromatic P₄ Composition Schemes for Perfectly Orderable Graphs'', submitted to Special Issue of Discrete Applied Mathematics for the Brazilian Symposium on Graphs, Algorithms and Combinatorics.

W. Lenhart, and G. Liotta, ``The Drawability Problem for Minimum Weight Triangulations'', Theoretical Computer Science, Vol. 270, Issue 1-2, 2002.

P. Bose, G. Di Battista, W. Lenhart and G. Liotta ``Proximity Constraints and Representable Trees'', submitted to Computational Geometry, Theory and Application.

W. Lenhart, and G. Liotta ``Drawing OuterPlanar Minimum Weight Triangulations'', Information Processing Letters, Vol. 57, no. 5, 1996.

P. Bose, W. Lenhart, and G. Liotta, ``Characterizing Proximity Trees'', Algorithmica, Vol. 16, no. 1, 1996.

W. Lenhart and S. Whitesides, ``Reconfiguring Closed Polygonal Chains in Euclidean d-Space'', Discrete and Computational Geometry, Vol. 13, no. 1, 1995.

G. Jennings and W. Lenhart, ``An Art Gallery Theorem for Line Segments in the Plane'', Pattern Recognition Letters, Vol. 14, Sep. 1993.

V. Chvatal, W. Lenhart and N. Sbihi ``Two-Colorings that Decompose Perfect Graphs'', Journal of Combinatorial Theory, Series B, Vol. 49, No. 1, Jun. 1990.

R. Hayward and W. Lenhart, ``On the P4-Structure of Perfect Graphs IV: Partner Graphs'', Journal of Combinatorial Theory, Series B, Vol. 48, No. 1, Feb. 1990.

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.

Refereed Conference Papers

R. Hayward and W. Lenhart, ``Perfectly Orderable P₄ Composition'', Brazilian Symposium on Graphs, Algorithms and Combinatorics, 2001, Electronic Notes in Discrete Mathematics, Vol. 7, Elsevier, 2001.

W. Lenhart and G. Liotta, ``Minimum Weight Drawings of Maximal Triangulations'', Graph Drawing 2000, Eighth International Symposium, Colonial Williamsburg., Lecture Notes in Computer Science, Vpl. 1984, Springer, Berlin, 2001.

W. Lenhart and G. Liotta, ``Drawable and Forbidden Minimum Weight Triangulations'', Graph Drawing '97, Fifth International Symposium, Rome, 1997., Lecture Notes in Computer Science, Vpl. 1353, Springer, Berlin, 1998.

C. Umans and W. Lenhart, ``Hamiltonian Cycles in Solid Grid Graphs'', FOCS '97, 38^th IEEE Conference on Foundations of Computer Science, Miami, 1997.

W. Lenhart and G. Liotta, ``Proximity Drawings of Outerplanar Graphs'', Graph Drawing '96, Symposium on Graph Drawing, Berkeley, 1996., Lecture Notes in Computer Science, Vol. 1190, Springer, Berlin, 1997.

W. Lenhart and G. Liotta, ``How to Draw Outerplanar Minimum Weight Triangulations'', Graph Drawing '95, International Workshop on Graph Drawing, Passau, 1995., Lecture Notes in Computer Science, Vol. 1027, Springer, Berlin, 1996.

G. Di Battista, W. Lenhart and G. Liotta, ``Proximity Drawability: a Survey'', Graph Drawing '94, DIMACS International Workshop on Graph Drawing, Princeton, 1994., Lecture Notes in Computer Science, Vol. 894, Springer, Berlin, 1995.

P. Bose, G. Di Battista, W. Lenhart and G. Liotta, ``Proximity Constraints and Representable Trees'', Graph Drawing '94, DIMACS International Workshop on Graph Drawing, Princeton, 1994. Lecture Notes in Computer Science, Vol. 894, Springer, Berlin, 1995.

P. Eades, H. El Gindy, M. Houle, W. Lenhart, M. Miller, D. Rappaport and S. Whitesides, ``Dominance Drawings of Bipartite Graphs'', Graph Drawing '93, The ALCOM International Workshop on Graph Drawing, Paris, 1993.

P. Bose, W. Lenhart and G. Liotta, ``Recognizing Proximity Graphs'', Graph Drawing '93, The ALCOM International Workshop on Graph Drawing, Paris, 1993.

W. Lenhart and S. Whitesides, ``Reconfiguration with Line Tracking Motions'', Fourth Canadian Conference on Computational Geometry, St. John's, Newfoundland 1992.

H. Everett, W. Lenhart, M. Overmars, T. Shermer and J. Urrutia, ``Strictly Convex Quadrilateralizations of Polygons'', Fourth Canadian Conference on Computational Geometry, St. John's, Newfoundland 1992.

W. Lenhart and S. Whitesides, ``Turning a Polygon Inside-Out'', Third Canadian Conference on Computational Geometry, Vancouver, British Columbia 1991.

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'', Proceedings of Third A.C.M. Conference on Computational Geometry. Waterloo, Ontario, 1987.

Workshops and Program Committees

``Graph Drawing '99'', Prague, Czech Republic, Sept. 1999, Program Committee

``Graph Drawing, Geometric Graph Theory, and Proximity Drawability'' one of four day-long workshops for computer science faculty given as part of ``Integrating Recent Research Results, an NSF-CISE Educational Infrastructure Workshop'' at The Evergreen State College, Olympia, WA, July 1997.

Research Lectures

``An Efficient Algorithm for Finding Hamiltonian Cycles in Solid Grid Graphs'',
Università degli Studi di Roma Tre, Departimento di Informatica e Automazione, January 2000,
Università degli Studi di Perugia, Departimento di Ingegneria Elettronica e dell'Informazione, January 2000,
McGill University, School of Computer Science, March 1997.

``Drawing OuterPlanar Minimum Weight Triangulations'',
Université de Quebec à Montréal, School of Computer Science, March 1997.
University of Rome, La Sapienza, Dept. of Computer Science, December 1996.
Brown University, Dept. of Computer Science, April 1996.

``How to Draw OuterPlanar Minimum Weight Triangulations'',
Fifth MSI-Stony Brook Workshop on Computational Geometry, SUNY Stony Brook, October 1995.

``Recognizing Proximity Graphs''
University of Quebec at Montreal, Dept. of Mathematics and Computer Science, Nov. 1993.

``Quadrilateralizing Simple Polygons''
University of Newcastle, Australia, Dept. of Computer Science, Nov. 1992.

``Hamiltonian Cycles in Grid Graphs''
McGill University, School of Computer Science, Mar. 1992.

``Turning a Polygon Inside-Out''
University of Quebec at Montreal, Dept. of Mathematics and Computer Science, Mar. 1992.

``Reconfiguring Simple Polygons''
McGill University, School of Computer Science, Mar. 1991.

``An Introduction to Visibility Problems''
Colgate University, Science Lecture Series, Oct. 1988.

``An Introduction to the Theory of Perfect Graphs''
University of Colorado, Denver, Dept. of Mathematics, Mar. 1988.

``Metrics in Polygons''
Rutgers University, Dept. of Computer Science, Dec. 1987.

``Two-Colorings that decompose Perfect Graphs''
Bellairs Research Institute of McGill U., Workshop on Perfect Graphs, Feb. 1986.

``Some Generalizations of Difference Sets''
University of Montreal, Nov. 1985

Technical Reports (Partial List)

P. Bose, W. Lenhart and G. Liotta
Recognizing Proximity Graphs,
McGill University Tech. Report SOCS-94.1, Jan, 1994.

W. Lenhart
Some Generalizations of Difference Sets,
McGill University Tech. Report SOCS-86.10, March, 1986.

Professional Service

Referee journal and conference articles in Graph Drawing, Computational Geometry, Graph Theory and Combinatorial Algorithms.

External reader for Masters and Ph.D. Theses.

External evaluator for tenure and promotion decisions.

Undergraduate Research Advising

Reed Townsend '00, Honors Thesis: Co-Circular Point Sets and the Minimum Weight Triangulation.

Davina Kunvipusilkul '99, Honors Thesis: Bend Minimumization for Hexagonal Graph Drawing.

Marc Blackstein '99, Honors Thesis: Minimum Weight Triangulations and an Improved LMT Algorithm.

Christopher Umans '96, Honors Thesis: An Algorithm for Finding Hamiltonian Cycles in Grid Graphs Without Holes.

Michael Pelsmajer '95, Honors Thesis: Bumper Drawings: A New Type of Proximity Drawing.

Stina Bridgeman '95, Honors Thesis: Finding Hamiltonian Cycles in Grid Graphs Without Holes.

Douglas Briggs '94, Honors Thesis: Hamiltonian Cycles in Grid Graphs.

Victor Kravets '91, Honors Thesis: Recognizing Perfectly Orderable Graphs.

George Jennings '90, Honors Thesis: Line Segment Visibility: Necessity, Sufficiency and Complexity.

Elizabeth Borowsky '90, Honors Thesis: Some Questions on Perfectly Orderable and Minimally Non-Perfectly Orderable Graphs.

SMALL Geometry Group Summer 1989: More work on art gallery problems in the plane. Jessica Baraka, Elizabeth Borowsky, Baird Jarman and Mark Knell.

SMALL Geometry Group Summer 1988: Working on an 'Art Gallery' problems concerning line segments in the plane. Rob Allen, Janet Wiener, Ken Hodges, Josh Smith and George Jennings

George Tolley '88, Honors Thesis. Two-Color P₃ Decomposition Theorems for Perfect Graphs.

Kenneth April '88, Honors Thesis. An Introduction to Several Classes of Perfect Graphs.

Michael McDougall '88, Independent Study. Porting and rewriting large parts of a software tool (GED) for geometers and graph theorists.

Davide Cervone '84, Honors Thesis. How Many Colors in a Box of Crayola Crayons? Graph Coloring and Short Cycles on the Torus.

Courses Taught

Computer Literacy, Introduction to Computer Science (CS1), Data Structures (CS2), Algorithm Design, Computer Graphics, Theory of Computation, Discrete Mathematics, Calculus, Linear Algebra, Combinatorics, Graph Theory, Real Analysis, Abstract Algebra

College Service

Chair, Dept. of Computer Science, 2001-02

Science Executive Committee, 2001-02

Faculty Steering Committee, 2001-02

Presidential Search Committee, 1999-00

Committee on Appointments and Promotions, 1999-00

Chair, Dept. of Computer Science, 1998-00

Science Executive Committee, 1998-00

Faculty Steering Committee, 1998-99

Committee on Educational Policy, 1997-99

Faculty Compensation Committee, 1995-96

Committee on Educational Policy, 1993-95

Science Executive Committee, 1990-92

Chair, Dept. of Computer Science, 1990-92

Ad Hoc Committee on Teaching Evaluation, 1990-92

Hiring Committee for Director of Academic Computing, 1990-91

Pine Cobble Building Covenants Committee, 1989-90

Chair of the Faculty Compensation Committee, 1987-88

Faculty Steering and Compensation Committee, 1986-88

Division III Planning Committee, 1984-85

Committee on Educational Policy, 1984-85

Committee on Priorities and Resources, 1983-85

Misc. ad hoc College and Science Division committees