Topological and Geometric Algorithms, Part II
Org: Mark Ellingham and Joanna Ellis-Monaghan (Vanderbilt University and Saint Michael's College)
[PDF]

THERESE BIEDL, University of Waterloo
Optimum-width upward drawings of trees  [PDF]

Tree visualizations are useful for displaying hierarchical structures such as family trees, subdirectories and XML code. In this talk, we consider algorithms that create tree drawings that are planar (no crossings) and upward (parents are above children). We also consider other restrictions, such as being straight-line (no bends) and/or order-preserving (the children appear in prescribed order) and/or a grid-embedding (edges are drawn along grid-lines). Our objective is to obtain drawings of small width. We give algorithms that (for some of these models) draw a given tree T with the minimum width that was possible for T.

MARK ELLINGHAM, Vanderbilt University
Graph embeddings and DNA reporter strands  [PDF]

A reporter strand is used to sequence the base pairs in a DNA structure. It corresponds to a closed walk in a graph that uses every edge at least once and occurs as a face boundary in some orientable embedding of the graph. Jonoska, Seeman and Wu showed that such a walk always exists. We give a short algorithmic proof of this. We also show that it is NP-complete to determine whether a graph has a reporter strand walk whose length meets a natural polynomial-time-computable lower bound, even for 3-connected 3-regular planar graphs. This is joint work with Joanna Ellis-Monaghan.

ELLEN GETHNER, University of Colorado Denver
Thickness, Simultaneous Embeddings, and Graph Sculpting  [PDF]

We study variations of the simultaneous embedding problem: given two unlabeled planar graphs $G$ and $H$ on $n$ vertices, is there a set of $n$ points in the plane on which both $G$ and $H$ can be embedded simultaneously without edge crossings? In particular, given any simple graph $G$ on $n$ vertices and any spanning subgraph $H<G$, is there a pointset $\mathcal{P}$ of size $n$ and a decomposition of $G$ into isomorphic copies of $H$ such that each copy of $H$ is noncrossing when embedded on $\mathcal{P}$? We study two classes of graphs: the $r$-blowups and $r$-inflations of planar graphs.

ANNA LUBIW, University of Waterloo
Flipping Edge-Labelled Triangulations  [PDF]

In a triangulation of points in the plane, a flip replaces one edge by the opposite edge of its surrounding quadrilateral when that quadrilateral is convex. Flips can be used to transform any triangulation to any other. We study flips when the edges of the triangulation are labelled and a flip of an edge transfers its label to the new edge. We characterize when one edge-labelled triangulation can be transformed to another via flips. Although our statement is purely combinatorial/geometric, the proof involves topological results on a structure that generalizes the associahedron.

Joint work with Zuzana MasÃ¡rovÃ¡ and Uli Wagner.

SUE WHITESIDES, University of Victoria
Visibility Graphs: a survey  [PDF]

Visibility graphs represent physical, geometric objects as vertices, and visibility between pairs of such objects as edges. These graphs can be studied from many points of view, including geometric, algorithmic, and graph theoretic. They have many applications as well. This talk briefly surveys a collection of older and newer results, as well as open problems in the area.