Events & News
Colloquium
| Category | Lecture |
| Date | Monday, April 13, 2009 |
| Time | 2:00 pm |
| Location | GS 906 |
| Details | Refreshments will be served at 1:45 p.m. in the 9th floor Atrium. PhD Thesis committee: Stephen G. Kobourov (chair) John D. Kececioglu Alon Efrat Joseph C. Watkins |
| Speaker | Alejandro Estrella Balderrama |
| Title | PhD Thesis Defense |
| Affiliation | Computer Science Department |
Simultaneous Embedding and Level Planarity
Graphs are a common model for representing information consisting of a
set of objects or entities and a set of connections or relations
between them. Graph Drawing is concerned with the automatic
visualization of graphs in order to make the information useful. That
is, a good drawing should be helpful in the application domain where
it is used by capturing the relationships in the underlying data. We
consider two important problems in automated graph drawing:
simultaneous embedding and level planarity.
Simultaneous embedding is the problem of drawing multiple graphs while
maintaining the readability of each graph independently and preserving
the mental map when going from one graph to another. In this case,
each graph has the same vertex set (same entities) but different edge
sets (different relationships). Level planarity arises in the layout of
graphs that contain hierarchical relationships. When drawing graphs in
the plane, this translates to a restricted form of planarity where the
vertical order of the entities is pre-determined.
We consider the computational complexity of the simultaneous embedding
problem. In particular, we show that in its generality the
simultaneous embedding problem is NP-hard if the edges are drawn as
straight-lines. We present algorithms for drawing graphs on
predetermined levels, which allow the simultaneous embedding of
restricted types of graphs, such as outerplanar graphs, trees and
paths. Finally, our practical contribution is a tool that implements
known and novel algorithms related to simultaneous embedding and level
planarity and can be used both as a visualization software and as an
aid to study theoretical problems.