crest



Department of Computer Science


University of Toronto


  








Derek G. Corneil

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

Phone:   (416)-978-8954
Fax:       (416) 978-1931
E-mail:   dgc [at] cs [dot] utoronto [dot] ca    

    
pic





Biography

Derek Corneil joined the Department of Computer Science of the University of Toronto in the fall
of 1964, the inaugural year of the department's graduate program. He had received his BSc degree in
Mathematics and Physics from Queen's University in 1964 and went on to complete his MA (1965) and
PhD (1968) degrees at the University of Toronto under the supervision of William Kahan and Kelly
Gotlieb respectively. He had an NSERC post doctoral fellowship at the University of Eindhoven (the
Netherlands) in 1968-69 (under the joint supervision of Jaap Seidel and Edsger Dijkstra) and joined the
faculty at the University of Toronto in Jan. 1970. He served as the chair of the Department from July
1985 to June 1990, the Director of Research Initiatives for the Faculty of Arts and Science, from July
1991 to March 1998, Acting Vice President of Research and International Relations from Sept. to Dec.
1993, and Academic Coordinator of Bell Canada University Labs at the University of Toronto from April
1998 to June 1999.

He retired in July, 2010 and is currently Professor Emeritus in both the Department of Computer
Science and the Department of Mathematics. His research is primarily in graph theory; this interest
spans theoretical, algorithmic and application issues. Most of his resent research attention has been on
Graph Searching. He has supervised or co-supervised the completion of 26 PhD and 35 MSc theses. His
doctoral graduates are currently in academic or industrial positions in 8 countries, as well as 6 provinces
in Canada. He is the author or co-author of over 100 refereed research publications.

Referee Publications

  1. C.C. Gotlieb and D.G. Corneil, ``Algorithms for finding a fundamental set of cycles for an undirected linear graph'', CACM 10, 12 (December 1967), pp.780-783.

  2. D.G. Corneil and C.C. Gotlieb, ``An efficient algorithm for graph isomorphism'', JACM 17, 1 (January 1970), pp.51-64.

  3. D.G. Corneil, ``An n**2 algorithm for determining the bridges of a graph'', IPL 1, 2 (July 1971), pp.51-55.

  4. G.D. Mulligan and D.G. Corneil, ``Corrections to Bierstone's algorithm for generating cliques'', JACM 19, 2 (April 1972), pp.244-247.

  5. D.G. Corneil, ``An algorithm for determining the automorphism partitioning of an undirected graph'', BIT 12 (1972), pp.161-171.

  6. D.G. Corneil, C.C. Gotlieb and Y.M. Lee, ``Minimal eventnode network of project precedence relations'', CACM, 16, 5 (May 1973), pp.296-298.

  7. D.G. Corneil and B. Graham, ``An algorithm for determining the chromatic number of a graph'', SIAM J. on Computing, 2, 4 (December 1973), pp.311-318.

  8. E. Arjomandi and D.G. Corneil, ``Unicyclic graphs satisfy Harary's conjecture'', Canadian Bull. Math., 17, 4 (1974), pp.593-595.

  9. D.G. Corneil, ``The analysis of graph theoretical algorithms'', Proceedings of the Fifth Southeastern Conference on Combinatorics, Graph Theory and Computing, (February 1974), pp.3-38.

  10. P.B. Gibbons, R. Mathon and D.G. Corneil, ``Steiner quadruple systems on 16 symbols'', Proceedings of the Sixth Southeastern Conference on Combinatorics, Graph Theory and Computing, (February 1975), pp.345-365.

  11. E. Arjomandi and D.G. Corneil, ``Parallel computations in graph theory'', Proceedings of the Sixteenth Annual Symposium on Foundations of Computer Science, (October 1975), pp.13-18.

  12. P.B. Gibbons, R.A. Mathon and D.G. Corneil, ``Computing techniques for the construction and analysis of block designs'', Utilitas Mathematica, 11 (May 1977), pp.161-192.

  13. R.C. Read and D.G. Corneil, ``The graph isomorphism disease'', Journal of Graph Theory 1 (1977), pp.339-363.

  14. D.G. Corneil and R.A. Mathon, ``Algorithmic techniques for the generation and analysis of strongly regular graphs and other combinatorial configurations'', Annals of Discrete Mathematics, 2 (1978), pp.1-32.

  15. D.G. Corneil and M.E. Woodward, ``A comparison and evaluation of graph theoretical clustering techniques'', INFOR, 16, 1 (February 1978), pp.74-89.

  16. E. Reghbati (Arjomandi) and D.G. Corneil, ``Parallel computations in graph theory'', SIAM J. on Computing, 7, 2 (May 1978), pp.230-237.

  17. D.G. Corneil, ``Recent results on the graph isomorphism problem'', Proc. 8th Manitoba Conference on Numerical Mathematics and Computing (September 1978), pp.13-31.

  18. H.D. Covvey, N.H. McAlister and D.G. Corneil, ``Computer-assisted medicine: how soft is software?'' C.M.A. Journal, 121 (Sept. 1979), pp.673-676.

  19. D.G. Corneil and D.G. Kirkpatrick, ``A theoretical analysis of various heuristics for the graph isomorphism problem'', SIAM J. on Computing, 9, 2 (May 1980), pp.281-297.

  20. C.J. Colbourn and D.G. Corneil, ``On deciding switching equivalence of graphs'', Discrete Applied Mathematics, 2 (1980), pp.181-184.

  21. D.G. Corneil, D.G. Kirkpatrick and M.M. Klawe, ``Generalized notions of pseudo-similarity in graphs'', Proceedings of the Eleventh Southeastern Conference on Combinatorics, Graph Theory and Computing (1980), pp.293-308.

  22. D.G. Kirkpatrick and D.G. Corneil, ``Forest embeddings in regular graphs with large girth'', JCT Series B, 30, 1 (February 1981), pp.45-60.

  23. D.G. Corneil, H. Lerchs and L. Stewart Burlingham, ``Complement reducible graphs'', Discrete Applied  Mathematics, 3 (1981), pp.163-174.

  24. D.G. Corneil and M.S. Krishnamoorthy, ``Weighted isomorphism problems'', Proceedings of the  Twelfth Southeastern Conference on Combinatorics, Graph Theory and Computing (1981), 32, pp.213-220.

  25. G. Cheston and D.G. Corneil, ``Graph update algorithms and their application to distance matrix corrections'', INFOR 20, 3 (Aug. 1982), 178-201.

  26. M.M. Klawe, D.G. Corneil and A. Proskurowski, ``Isomorphism testing in hookup classes'', SIAM J. Alg. Disc. Meth., 3, 2 (June 1982), pp.260-274.

  27. D.G. Corneil and M. Goldberg, ``On graph certificates'', Proc. of the Thirteenth Southeastern Conference on Combinatorics, Graph Theory and Computing (1982), pp.181-189.

  28. D.G. Kirkpatrick, M.M. Klawe and D.G. Corneil,  ``On pseudo-similarity in trees'', JCT Series B, 34, 3 (June 1983), pp.323-339.

  29. D.G. Corneil and J.M. Keil, ``A note on a conjecture by Gavril on clique separable graphs'' Discrete Mathematics, 45 (1983), pp.317-318.

  30. D.G. Corneil and D.G. Kirkpatrick, ``Families of recursively defined perfect graphs'', Proceedings of the Fourteenth Southeastern Conference on Combinatorics, Graph Theory and Computing (1983), pp.237-246.

  31. D.G. Corneil and M. Goldberg, ``A non-factorial algorithm for canonical numbering of a graph'', Journal of Algorithms 5 (1984), pp.345-362.

  32. D.G. Corneil and Y. Perl, ``Clustering and domination in perfect graphs'', Discrete Applied Mathematics 9 (1984), pp.27-39.

  33. D.G. Corneil, Y. Perl and L.K. Stewart,  ``Cographs: recognition, applications and algorithms'',  Proceedings of the Fifteenth Southeastern Conference on Combinatorics, Graph Theory and Computing (1984), pp.249-258.

  34. D.G. Corneil, Y. Perl and L.K. Stewart, ``A linear recognition algorithm for cographs'', SIAM J. on Computing, 14, 4 (Nov. 1985), pp.926-934.

  35. D.G. Corneil, ``The complexity of generalized clique packing'',  Discrete Applied Mathematics, 12 (1985), pp.233-239.

  36. D.G. Corneil, ``Algorithms for perfect graphs'', Proc. 1985 International Symposium on Circuits and Systems (IEEE) (1985), pp.1187-1190.

  37. D.G. Corneil, ``Families of graphs complete for the strong perfect graph conjecture'', J. Graph Theory, 10, 1 (1986), pp.33-40.

  38. M. Conforti, D.G. Corneil and A.R. Mahjoub, ``Ki-covers I: complexity and polytopes'', Discrete Mathematics, 58, 2 (1986), pp.121-142.

  39. S. Arnborg, D.G. Corneil and A. Proskurowski, ``Complexity of finding embeddings in a k-tree'', SIAM J. Alg. Disc. Meth., 8, 2 (1987), pp.277-284.

  40.  D.G. Corneil and J.M. Keil, ``A dynamic programming approach to the dominating set problem on k-trees'', SIAM J. Alg. Disc. Meth., 8, 4 (1987), pp.535-543.

  41. J. Brown and D.G. Corneil, ``On generalized graph colourings'', J. Graph Theory, 11, 1 (1987), pp.87-99.

  42. M. Conforti, D.G. Corneil and A.R. Mahjoub, ``Ki -covers II: Ki - perfect graphs'', J. Graph Theory, 11, 4 (1987), pp.569-584.

  43. D.G. Corneil and P.A. Kamula, ``Extensions of permutation and interval graphs'', Proceedings of the Eighteenth Southeastern Conference on Combinatorics, Graph Theory and Computing (1987), pp.267-276.

  44. D.G. Corneil and J. Fonlupt, ``The complexity of generalized clique  covering'', Discrete Applied Mathematics, 22 (1988/89), pp.109-118.

  45. S. Arnborg, A. Proskurowski and D.G. Corneil, ``Forbidden minors characterization of partial 3-trees'', Discrete Mathematics , 80, 1 (1990), pp.1-19.

  46.  D.G. Corneil and L.K. Stewart, ``Dominating sets in perfect graphs'', Discrete Mathematics, 86 (1990), pp.145-164.

  47.  F. Cheah and D.G. Corneil, ``The complexity of regular subgraph recognition'', Discrete Applied Mathematics, 27, 1-2 (1990), pp.59-68. Addendum 31, 3 (1991), pp.309.

  48. H. Everett and D.G. Corneil, ``Recognizing visibility graphs of spiral polygons'', Journal of Algorithms, 11, 1 (1990), pp.1-26.

  49.  A. Wagner and D.G. Corneil, ``Embedding trees in a hypercube is  NP-complete'', SIAM J. on Computing, 19, 3 (1990), pp.570-590.

  50.  J.I. Brown, D.G. Corneil and A.R. Mahjoub, ``A note on Ki -perfect graphs'', J. Graph Theory, 14, 3 (1990), pp.333-340.

  51.  J.I. Brown and D.G. Corneil, ``Perfect colourings'', Ars  Combinatoria, 30 (1990), pp.141-159.

  52. T. Przytycka and D.G. Corneil, ``Parallel algorithms for parity graphs'',  Journal of Algorithms, 12 (1991), pp.96-109.

  53. J.I. Brown and D.G. Corneil, ``Graph properties and hypergraph colourings'', Discrete Mathematics, 98 (1991), pp.81-93.

  54. L. Cai and D.G. Corneil, ``Cycle double covers of line graphs'',  Discrete Mathematics, 102 (1992), pp.103-106.

  55. L. Cai and D.G. Corneil, ``Tree spanners: an overview'',  Proceedings of the Twenty-Third Southeastern Conference on Combinatorics, Graph Theory and Computing 1992, Congressus Numerantium, 88 (1992), pp.65-76.

  56. J.I. Brown and D.G. Corneil, ``On uniquely G-k-colourable graphs'', Quaestiones Mathematicae, 15, 4 (1992), pp.477-487.

  57. A. Wagner and D.G. Corneil, ``On the complexity of the embedding problem for hypercube related graphs'', Discrete Applied Mathematics, 43 (1993), pp.75-95.

  58. D.G. Corneil and J. Fonlupt,  ``Stable set bonding in perfect graphs and parity graphs'', JCT Series B, 59, 1 (1993), pp.1-14.

  59. E.G. Anagnostou and D.G. Corneil, ``Polynomial-time instances of the minimum weight triangulation problem'', Computational Geometry: Theory and Applications, 3 (1993), pp.247-259.

  60. D.G. Corneil, S. Masuyama and S.L. Hakimi, ``Edge disjoint packings of graphs'', Discrete Applied Mathematics, 50 (1994), pp.135-148.

  61. L. Cai and D.G. Corneil, ``Isomorphic tree spanner problems'',  Algorithmica, 14 (1995), pp.138-153.

  62. D.G. Corneil, S. Olariu and L. Stewart, ``A linear time algorithm to compute a dominating path in an AT-free graph'', IPL, 54 (1995), pp.253-257.

  63. L. Cai and D.G. Corneil, ``Tree spanners'', SIAM J. Disc. Math., 8 (1995), pp.359-387.

  64. D.G. Corneil, H. Kim, S. Natarajan, S. Olariu and A.P. Sprague, ``Simple  linear time recognition of unit interval graphs'', IPL, 55 (1995), pp.99-104.

  65. H. Everett and D.G. Corneil, ``Negative results on characterizing visibility graphs'', Computational Geometry, 5 (1995), pp.51-63.

  66. D.G. Corneil, S. Olariu and L. Stewart, ``Computing a dominating pair in an asteroidal triple-free graph in linear time'', Proceedings of 4th  Algorithms and Data Structures Workshop, LNCS 955 (Springer) (1995), pp.358-368.

  67. L. Cai, D.G. Corneil and A. Proskurowski, ``A generalization of line graphs: (X,Y)-intersection graphs'', J. Graph Theory, 21,3 (1996), pp.267-287.

  68. F. Cheah and D.G. Corneil, ``On the structure of trapezoid graphs'', Discrete Applied Mathematics, 66, 2 (1996), pp.109-133.

  69. L. Cai and D.G. Corneil, ``A generalization of perfect graphs   i-perfect graphs'', J. Graph Theory, 23, 1 (1996), pp.87-103.

  70. M.D. Hutton, J.P. Grossman, J. Rose, and D.G. Corneil, ``Characterization and parameterized random generation of digital circuits'', Proc.  33rd ACM/IEEE Design Automation Conference (1996), pp.94-99.

  71. M.D. Hutton, J.S. Rose and D.G. Corneil, ``Generation of synthetic sequential bench-mark circuits'', 5th ACM/SIGDA International Symposium on FPGAs (FPGA97) (1997), pp.149-155.

  72. D.G. Corneil, S. Olariu and L. Stewart, ``Asteroidal triple-free  graphs'',  SIAM J. Disc. Math. 10,3 (1997), pp.399-430.  (Available as TR94-31, Dept. of Computer Science, Old Dominion University), Extended abstract appeared in  Proc. Graph-Theoretic Concepts in  Computer Science, LNCS 790 (Springer) (1993), pp.211-225.

  73. M.D. Hutton, J.S. Rose, J.P. Grossman and D.G. Corneil, `` Characterization and parameterized generation of combinational benchmark circuits'', IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems, 17, 10 (1998) pp.985-996.

  74. P. Kearney and D.G. Corneil, ``Tree powers'', J. Algorithms 29, (1998) pp.111-131.

  75. D. Achlioptas, J.I. Brown, D.G. Corneil and M.S.O. Molloy, ``The existence of uniquely -G colourable graphs'',  Discrete Mathematics 179, 1-3 (1998), pp.1-11.

  76. T.B. Moorhouse and D.G. Corneil, ``Completeness for intersection classes'', Discrete Mathematics, 190, 1-3 (1998), pp.277-286.

  77. D.G. Corneil, S. Olariu and L. Stewart, ``LBFS orderings and cocomparability graphs'' Proc. of the Tenth Annual ACM-SIAM Symposium on Discrete  Algorithms (SODA) (1999), pp.883-884.

  78. D.G. Corneil, S. Olariu and L. Stewart, ``Linear time algorithms for dominating pairs in asteroidal triple-free graphs'', SIAM J. on Computing, 28, 4 (1999), pp.1284-1297.  (Extended  Abstract in Proceedings of 22nd ICALP Conference,  LNCS 944 (Springer) (1995), pp.292-302.)

  79. M. Li, D.G. Corneil and E. Mendelsohn, ``Pancyclicity and NP-completeness in planar graphs'', Discrete Applied Mathematics 98, 3 (2000), pp.219-225.

  80. L. Cai, D.G. Corneil and A. Proskurowski, \Stable 2-pairs and (X; Y )-intersection graphs",
    Discrete Mathematics 230 (2001), pp.119-131.

  81. D.G. Corneil, F. Dragan, M. Habib and C. Paul, \Diameter determination on restricted graph
    families", Discrete Applied Mathematics 113, 2-3 (2001), pp.143-166. (Extended Abstract
    in Proceedings of 24th International Workshop on Graph Theory, LNCS 1517 (Springer)
    (1998),pp.192-202.)

  82. M.D. Hutton, J. Rose and D.G. Corneil. \Automatic Generation of Synthetic Sequential
    Benchmark Circuits", IEEE Trans. on CAD, 21, 8 (2002) pp.928-940.

  83. D.G. Corneil, F.F. Dragan and E. Koehler, \On the power of BFS to determine a graph's
    diameter", Networks 42 (2003), pp.209-222. (Extended Abstract appeared in Proceedings of
    the LATIN2002 Conference, LNCS 2286, (Springer) (2002), pp.209-223.)
  84. N. Przulj, D.G. Corneil and E. Koehler, \Hereditary dominating pair graphs", Discrete Applied
    Mathematics, 134 (2004) pp.239-261.

  85. D.G. Corneil, \A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs",
    Discrete Applied Mathematics, 138 (2004) pp.371-379.

  86. L.C. Lau and D.G. Corneil, \Recognizing powers of proper interval, split and chordal graphs",
    SIAM J. Disc. Math., 18, 1 (2004) pp.83-102.

  87. N. Przulj, D.G. Corneil and I. Jurisica, \Modeling Interactome: Scale-Free or Geometric?",
    Bioinformatics, 20, 18 (2004) pp.3508-3515.

  88. D.G. Corneil, \Lexicographic Breadth First Search - a survey", 30th International Workshop
    on Graph Theory, WG2004, LNCS 3353 (Springer) (2004) pp.1-19.

  89. N. Przulj and D.G. Corneil, \2-tree probe interval graphs have a large obstruction set", Discrete
    Applied Mathematics, 150 (2005) pp.216-231.

  90. D.G. Corneil and U. Rotics, \On the relationship between clique-width and treewidth", SIAM
    J. Computing, 34, 4 (2005) pp.825-847. (Extended abstract appeared in 27th International
    Workshop on Graph Theory (WG2001), LNCS 2204 (Springer) (2001), pp.78-90.)  

  91. D.G. Corneil, F.F. Dragan, E. Koehler and C. Yan, \Collective tree 1-spanners for interval
    graphs" (extended abstract), in 31st International Workshop on Graph Theory (WG2005),
    LNCS 3787 (Springer) (2005), pp.151-162.

  92. D.G. Corneil, E. Koehler, S. Olariu and L. Stewart, \On subfamilies of AT-free graphs", SIAM
    J. Disc. Math., 20, 1 (2006), pp.105-118. (Extended abstract appeared as \Linear orderings of
    subfamilies of AT-free graphs", in 27th International Workshop on Graph Theory (WG2001),
    LNCS 2204 (Springer) (2001), pp.241-253.) 

  93. F.F. Dragan, C. Yan and D.G. Corneil, \Collective tree spanners and routing in AT-free
    related graphs", Journal of Graph Algorithms and Applications (JGAA) 10, 2 (2006), pp.97-
    122. (Extended abstract appeared in 30th InternationalWorkshop on Graph Theory, WG2004,
    LNCS 3353 (Springer) (2004) pp.68-80.)

  94. N. Przulj, D.G. Corneil and I. Jurisica, \Ecient estimation of graphlet frequency distributions
    in protein-protein interaction networks", Bioinformatics 22, 8 (2006) pp.974-980.

  95. M. Tedder and D.G. Corneil, \An optimal, edges only fully dynamic algorithm for distance-
    hereditary graphs", Proceedings of 24th International Symposium on Theoretical Aspects of
    Computer Science (STACS 2007), Aachen, LNCS 4393 (Springer) (2007) pp.344-355.

  96. D.G. Corneil and R. Krueger, \A uni ed view of graph searching", SIAM J. Disc. Math. 22,
    4 (2008) pp.1259-1276.

  97. A. Bretscher, D.G. Corneil, M. Habib and C. Paul, \A simple linear time LexBFS cograph
    recognition algorithm", SIAM J. Disc. Math. 22, 4 (2008) pp.1277-1296. (Extended abstract
    appeared in 29th International Workshop on Graph Theory, WG2003, LNCS 2880 (Springer)
    (2003) pp.119-130.)  

  98. M. Tedder, D. Corneil, M. Habib and C. Paul, \Simpler linear-time modular decomposition via
    recursive factorizing permutations", 35th International Colloquium on Automata, Languages
    and Programming, ICALP2008, Part 1 LNCS 5125 (Springer) (2008) pp.634-645. 

  99. D.G. Corneil, S. Olariu and L. Stewart, \The LBFS structure and recognition of interval
    graphs", SIAM J. Disc. Math. 23, 4, (2009) pp.1905-1953. (Extended Abstract appeared as
    \The ultimate interval graph recognition algorithm?", Proc. of the Ninth Annual ACM-SIAM
    Symposium on Discrete Algorithms (SODA) (1998), pp.175-180.) 

  100. D.G. Corneil, E. Koehler, J-M. Lanlignel, \On end-vertices of Lexicographic Breadth First
    Searches", Discrete Applied Mathematics, 158 (2010) pp.434-443.

  101. G.B. Mertzios and D.G. Corneil, \Vertex splitting and the recognition of trapezoid graphs",
    Discrete Applied Mathematics, 159 (2011) pp. 1131-1147.

  102. D.G. Corneil, M. Habib, J-M. Lanlignel, B. Reed and U. Rotics, \Polynomial time recognition
    of clique-width  3 graphs", Discrete Applied Mathematics, 160(6) (2012) pp.834-865. (Ex-
    tended Abstract appeared in Proceedings of LATIN2000 Conference, LNCS 1776 (Springer)
    (2000), pp.126-134.)

  103. F.F. Dragan, D.G. Corneil, E. Koehler and Y. Xiang, \Spanners of circle graphs and poly-
    gon graphs", Discrete Applied Mathematics, 160(12) (2012) pp.1717-1729. (Extended Ab-
    stract appeared as \Additive spanners for circle graphs and polygonal graphs", 34th Interna-
    tional Workshop on Graph-Theoretic Concepts in Computer Science, WG 2008, LNCS 5344
    (Springer) (2008) pp.110-121.)

  104. G.B. Mertzios and D.G. Corneil, \A simple polynomial algorithm for the longest path problem
    on cocomparability graphs", SIAM J. Disc. Math. 26, 3 (2012) pp.940-963.

  105. E. Gioan, C. Paul, M. Tedder and D.G. Corneil, \Practical and ecient split-decomposition
    via graph-labelled trees", Algorithmica, appeared online March 2013, 55pp.

  106. E. Gioan, C. Paul, M. Tedder and D.G. Corneil, \Practical and ecient circle graph recogni-
    tion", Algorithmica, appeared online March 2013, 30pp.

  107. D.G. Corneil, B. Dalton and M. Habib, \LDFS based certifying algorithm for the Minimum
    Path Cover problem on cocomparability graphs", SIAM J. on Computing, 42(3) (2013) pp.792-
    807.

  108. D.G. Corneil and J. Stacho, \Elimination orderings of graphs of bounded asteroidal number",
    to appear Journal of Graph Theory.    


Papers in Preparation

  1. D.G. Corneil, J. Dusart, M. Habib, A. Mamcarz, and F. de Montgol er, \A new model for
    graph search", submitted for publication.

  2. D.G. Corneil and J. Stacho, \The structure and recognition of C4-free, AT-free graphs", in
    preparation.

  3. D.G. Corneil, F.F. Dragan, E. Koehler and Y. Xiang, \Lower bounds on additive spanners",
    in preparation.

  4. D.G. Corneil, J. Dusart, M. Habib and E. Koehler, \On the power of graph searching for
    cocomparability graphs", in preparation.