## October 2, Fall Quarter 2009: Thoery Seminar

### 1:00pm in 1423 Bren Hall

# Planar Drawings of Higher-Genus Graphs

## Michael Goodrich, UC Irvine

In this talk, we give polynomial-time algorithms that can take a graph G with a given combinatorial
embedding on a surface S of genus g and produce a planar drawing of G, with a bounding
face de ned by a polygonal schema P for S. Our drawings are planar, but they allow for multiple copies of
vertices and edges on P's boundary, which is a common way of visualizing higher-genus graphs in the plane.
As a side note, we show that it is NP-complete to determine whether a given graph embedded in a genus-g
surface has a set of 2g fundamental cycles with vertex-disjoint interiors, which would be desirable from a
graph-drawing perspective.