crest

Department of Computer Science
University of Toronto

Steven Chaplick

  • My CV: pdf
  • Ph.D. Candidate (Supervisor: Derek Corneil)

  • 10 King's College Road
    Sandford Fleming Building, Room SF4301F
    University of Toronto
    Toronto, Ontario M5S 3G4

  • Email (Research): chaplick {at} cs {dot} toronto {dot} edu
  • Email (Teaching): chaplick {at} cdf {dot} toronto {dot} edu


Research Interests

My primary area of interest is Graph Theory, and my current research focuses on intersection representations of graphs, efficient methods for graph class recognition, and canonical representations of graphs. I am also interested in graph class hierarchies, forbidden induced subgraph characterizations of graph classes, graph isomorphism, graph search techniques, and graph classes for which NP-hard problems become polynomial time. My secondary interests are in Computational Biology and Complexity Theory; specifically, genome assembly and comparison, fixed parameter tractability, and kernelization.

Teaching (course webpages available here)

  • (Summer 2010) CSC373: Algorithm Design and Analysis
  • (Summer 2009) CSC165: Mathematical Expression and Reasoning for Computer Science
  • (Summer 2008) CSC165: Mathematical Expression and Reasoning for Computer Science
  • (Summer 2007) CSC236: Introduction to the Theory of Computing

Refereed papers in conference proceedings
  • Chaplick, S., E. Cohen, and J. Stacho (2011). “Recognizing some subclasses of vertex intersection graphs of 0-bend paths in a grid”. Accepted to the 37th International Workshop on Graph-Theoretic Concepts in Computer Science.
  • Chaplick, S., M. Gutierrez, B. Lévêque, and S. B. Tondato (2010). From Path Graphs to Directed Path Graphs. In: WG. Ed. by D. M. Thilikos. Vol. 6410. Lecture Notes in Computer Science, pp.256–265. isbn: 978-3-642- 16925-0. Links: LNCS, pdf
M.Sc. Thesis
  • Chaplick, S. (Jan. 2008). PQR-trees and Undirected Path Graphs. M.Sc. Thesis, University of Toronto. pdf
Submitted papers
  • Chaplick, S. (Apr. 2010). “Characterizing and Recognizing Path Graphs and Directed Path Graphs using PR-trees”. Submitted to the Journal of Discrete Applied Mathematics for publication. Current version: pdf
Unpublished working papers
  • Chaplick, S. and J. Stacho (Apr. 2011). The vertex leafage of chordal graphs. ArXiv e-prints. arXiv:1104.2524 [cs.DM].
Papers in Preparation
  • Chaplick, S., D. Corneil, and M. Francis. “On Vertex Intersection Graphs of Paths on a Grid”.
  • Chaplick, S., M. Fellows, and B. König. “Graph Rewriting Confluence in Kernelization Methods”.
  • Chaplick, S., M. Habib, and B. Lèvêque. “Vertex Ordering Properties of Leaf Powers”.
  • Chaplick, S. and B. Lèvêque. “The Forbidden Asteroidal Triple Structure of Path Graphs”.
  • Chaplick, S. and M. Habib. “The Maximal Clique vs. Minimal Separator Structure of Chordal Families of Graphs”.