There are number of interesting questions concerned with algorithms for graphs on surfaces. Indeed, examples of such geometric graphs include planar convex hulls, Voronoi diagrams, Delaunay triangulations, line arrangements, visibility graphs, polygon triangulations, and Euclidean minimum spanning trees, which collectively form the backbone of the topics in computational geometry. This work studies algorithms for graphs such that the vertices are points in a geometric space and the edges are curves that are embedded in a surface that is itself embedded in that space. In particular, this project is focused on algorithms for graphs on surfaces, directed at the following three thrust areas:

• Algorithms for Embedding Graphs on Surfaces: This is the study of methods for producing geometric configurations from a combinatorial graph. Topics of interest in this thrust area include methods for approximate minimum-genus embedding of graphs, algorithms for manifold triangulation for a set of points sampled from an embedded surface, and techniques for drawing trees in the plane, which are of interest in the visualization of hierarchies, such as organization charts and object-oriented class hierarchies.
• Algorithms for Graphs Embedded on Surfaces: This is the study of graph algorithms that take advantage of additional structure available for graphs embedded on surfaces. Topics of interest in this thrust area include the study of connections between partial cubes and integer lattices, the development of algorithms for graphs embedded in Non-Euclidean spaces, such as hyperbolic spaces, and the design of methods for solving graph problems on quadrilateral meshes, which arise in surface modeling and animation applications.
• Applications of Algorithms for Graphs on Surfaces: This is the study of applications of algorithms that are specialized for graphs on surfaces. Topics of interest include applications of geometric graphs to computer graphics, computer security, greedy geometric routing in sensor networks, and algorithms for road networks.

Papers

• D. Eppstein*, M.T. Goodrich*, E. Kim, and R. Tamstorf, "Approximate Topological Matching of Quadrilateral Meshes," Proc. IEEE Int. Conf. on Shape Modeling and Applications (SMI), 2008, 83--92.
• G. Bareqet, D. Eppstein, M.T. Goodrich, and A. Waxman, "Straight Skeletons of Three-Dimensional Polyhedra," Proc. 16th European Symposium on Algorithms (ESA), 2008, LNCS 5193, 148-160.
• D. Eppstein*, M.T. Goodrich*, E. Kim, and R. Tamstorf, "Motorcycle Graphs: Canonical Quad Mesh Partitioning," Proc. 6th European Symposium on Geometry Processing (SGP), 2008, to appear.
• D. Eppstein and M.T. Goodrich, "Succinct Greedy Graph Drawing in the Hyperbolic Plane," Graph Drawing 2008, to appear.
• D. Eppstein, M.T. Goodrich, and D. Strash, Linear-Time Algorithms for Geometric Graphs with Sublinearly Many Crossings, SODA 2009, to appear.
• D. Eppstein. The Topology of Bendless Three-Dimensional Orthogonal Graph Drawing. arxiv:0709.4087. Proc. 16th Int. Symp. Graph Drawing, Heraklion, Crete, 2008.
• D. Eppstein. Isometric diamond subgraphs. arxiv:0807.2218. Proc. 16th Int. Symp. Graph Drawing, Heraklion, Crete, 2008.
• D. Eppstein and E. Mumford. Self-Overlapping Curves Revisited. arxiv:0806.1724. 20th ACM-SIAM Symp. Discrete Algorithms, New York, 2009.
• Charalampos Papamanthou, Franco P. Preparata, and Roberto Tamassia. Algorithms for Location Estimation based on RSSI Sampling. to appear In Proc. of the ICALP Int. Workshop on Algorithms for Sensor Networks (ALGOSENSORS), 2008
• Roberto Tamassia, Bernardo Palazzi, and Charalampos Papamanthou. Graph Drawing for Security Visualization. to appear In Proc. of the Int. Conference on Graph Drawing (GD), 2008

Support

*This research was performed while Drs. Eppstein and Goodrich were serving as consultants to Walt Disney Animation Studios.