Events & News
Colloquium
| Category | Lecture |
| Date | Monday, April 13, 2009 |
| Time | 11:00 am |
| Location | GS 701 |
| Details | Refreshments will be served at 10:45 a.m. in the 7th floor lobby. PhD Thesis committee: Stephen Kobourov (chair) Pete Downey Alon Efrat John Kececioglu |
| Speaker | Joe Fowler |
| Title | PhD Thesis Defense |
| Affiliation | Computer Science Department |
Unlabeled Level Planarity
Consider a graph G with vertex set V in which each of the n vertices is assigned a number from the set {1,...,k} for some positive integer k. This assignment φ is a labeling if all k numbers are used. If φ does not assign adjacent vertices the same label, then φ forms a leveling that partitions V into k levels. In a level drawing, the y-coordinate of each vertex matches its label and the edges are drawn strictly y-monotone. This leads to level drawings in the xy-plane where all vertices with label j lie along the line lj = {(x, j): x ∈ R} and where each edge crosses any of the k horizontal lines lj for j ∈ [1..k] at most once. A graph with a leveling forms a level graph and is level planar if it has a level drawing without crossings.
We first consider the class of level trees that are level planar regardless of their labeling. We call such trees unlabeled level planar (ULP). We describe which trees are ULP and provide linear-time level planar drawing algorithms for any labeling. We characterize ULP trees in terms of two forbidden minors so that any other tree must contain a subtree homeomorphic to one of these. We also provide linear-time recognition algorithms for ULP trees. We then extend this characterization to all ULP graphs with five additional forbidden cyclic minors, and provide linear-time drawing algorithms for any given leveling.