Thursday, June 20

10:00 AM-12:00 PM

Room 301
## MS12

Computational Geometry and Graph Drawing

This minisymposium addresses computational geometry and graph drawing. Because of the fundamental spatial properties of the physical world, issues for dealing with geometric data, either as input or output, arise naturally anytime one wishes to model physical objects or to visualize non-physical relationships using an intuitive representation. Talks in this minisymposium will focus on both of these aspects, with the first two discussing geometric planning problems for computing assembly or cutting strategies for a given configuration of geometric objects, and the second two discussing problems dealing with the determination of geometric objects that realize combinatorial relationships represented in graphs.
**Organizer: Michael T. Goodrich**

Johns Hopkins University

**10:00 Computing Offset Curves and Tool Paths of Simple Polygons**
- Diane Souvaine, Rutgers University
**10:30 Efficient Generation of k-Directional Assembly Sequences**
- Pankaj Agarwal, Duke University
**11:00 Quasi-Planar Graphs Have a Linear Number of Edges**
- Richard Pollack, Courant Institute of Mathematical Sciences, New York University
**11:30 On 3-dimensional Convex Graph Drawing**
- Michael T. Goodrich, Organizer

*MEM, 4/10/96*