|
Research Interests
My primary area of interest is Graph Theory. In
particular, I focus on intersection representations of graph, efficient methods for
graph class recognition, and canonical representations of graphs. I am also
interested in graph class hierarchies, forbidden induced subgraph characterisations
of graph classes, graph isomorphism, graph search techniques, and restricted classes
of graphs for which NP-hard problems become polynomial time (or better). My
secondary areas of interest are Complexity Theory, Computer Graphics, and Artificial
Intelligence; specifically, problems between P and NP, approximation of NP-hard
problems, photo-realistic rendering, ray-tracing, pre-computed radiance transfer,
accurate shadow generation, real-time approximations of exact rendering techniques,
machine learning, and some aspects of natural language processing.
Current Research
In my current research I am working on characterizing and recognizing restricted families of graphs. More specifically, I am interested in undirected path
graphs, directed path graphs, and rooted directed path graphs. These are the intersection graphs of subpaths of a tree, directed paths in a directed tree, and directed paths in a rooted directed tree (respectively). In particular, I am
working a new characterization and recognition algorithm for these graph classes.
Teaching
Papers
- Steven Chaplick, "PQR-trees and Undirected Path Graphs", M.Sc. Thesis, Dept. of Computer Science, University of Toronto, 2008
|