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 is a Quebec city native and received his BSc degree in Mathematics and Physics from Queen's University in 1964 and his MA and PhD degrees in Computer Science from the University of Toronto in 1965 and1968 respectively. He had an NSERC post doctoral fellowship at the University of Eindhoven (the Netherlands) in 1968-69 and joined the faculty at the University of Toronto in Jan. 1970. He is cross-listed in the Department of Mathematics and has had visiting professorial positions at the University of British Columbia, Simon Fraser University the Universite de Grenoble and the Universite de Montpellier. 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.

His research is primarily in graph theory; this interest spans theoretical, algorithmic and application issues. He has supervised or co-supervised the completion of 24 PhD and 34 MSc theses. The doctoral graduates are currently in academic or industrial positions in 7 countries, including 6 provinces in Canada. He is the author or co-author of over 100 research publications and is currently an editor of Discrete Applied Mathematics, Ars Combinatoria and SIAM Monographs on Discrete Mathematics and Applications. 

   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. D.G. Corneil, S. Olariu, L. Stewart, ``The ultimate interval graph recognition algorithm?'' (Extended Abstract) Proc. of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (1998), pp.175-180.

  74. 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.

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

  76. 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.

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

  78. 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.

  79. 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.)

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

  81. D.G. Corneil, M. Habib, J-M. Lanlignel, B. Reed and U. Rotics, ``Polynomial time recognition of clique-width ≤ 3 graphs'', (extended abstract) Proceedings of LATIN2000 Conference, LNCS 1776 (Springer) (2000), pp.126-134.

  82. L. Cai, D.G. Corneil and A. Proskurowski, ``Stable 2-pairs and (X,Y)-intersection graphs'',  Discrete Mathematics 230 (2001), pp.119-131.

  83. 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 in Graph-Theoretic Concepts in Computer Science, LNCS 1517 (Springer) (1998),pp.192-202.)

  84. 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.

  85. 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 in Proceedings of the LATIN2002 Conference, LNCS 2286, (Springer) (2002), pp.209-223.)

  86. N. Przulj, D.G. Corneil and E. Koehler, ``Hereditary dominating pair graphs'', Discrete Applied Mathematics, 134 (2004) pp.239-261.

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

  88. 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.

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

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

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

  92. 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.)  

  93. 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.   

  94. 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.)

  95. 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 International Workshop on Graph Theory, WG2004, LNCS 3353  (Springer) (2004) pp.68-80.)   

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

  97. 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. 

  98. D.G. Corneil and R. Krueger, "A unified view of graph searching", to appear SIAM J. Disc. Math.

  99.  A. Bretscher, D.G. Corneil, M. Habib and C. Paul, ``A simple linear time LexBFS cograph recognition algorithm'', to appear SIAM J. Disc. Math. (Extended abstract appeared in 29th International Workshop on Graph Theory, WG2003, LNCS 2880 (Springer) (2003) pp.119-130.) 

  100. M. Tedder, D. Corneil, M. Habib and C. Paul, "Simpler linear-time modular decomposition via factorizing permutations", to appear 35th International Colloquium on Automata, Languages and Programming (ICALP) (2008).  

  101. F.F. Dragan, D.G. Corneil, E. Koehler and Y. Xiang, "Additive spanners for circle graphs and polygonal graphs", to appear 34th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2008). 

   Non-Refereed Publications

  1. D.G. Corneil and E. Mendelsohn (editors), ``Proceedings of the Conference on Algebraic Aspects of Combinatorics'', Utilitas Mathematica Publishing Co., Winnipeg, Man. (1975), pp.296.

  2. R. Chen, H.D. Covvey, D. Corneil, M. van Horik and E.D. Wigle, ``Study of the economics of a distributed versus a centralized approach in a small database management system'', Proceedings of the  International Conference on Computers in Cardiology, Geneva (Sept. 1979), pp.243-244.

  3. D.G. Corneil, S. Olariu and L. Stewart, ``On the linear structure of graphs'', Extended Abstract, The first workshop on COST, Combinatorial Optimization in Science and Technology, Rutgers University (April 1991), DIMACS TR 91-18, RUTCOR  Report 3-91, pp.99-106.

  4. D.G. Corneil and R. Mathon (editors), ``Geometry and Combinatorics, selected works of J.J. Seidel'', Academic Press, Boston, Mass. (1991), pp.410.

  5. D.G. Corneil, S. Olariu, L. Stewart, ``Asteroidal triple-free graphs'', Dept. of Computer Science Tech. Report #262/92.

  6. Editor:  ``Coloring Mixed Hypergraphs: Theory, Algorithms and Applications'' (181 pages) by V. I. Voloshin,  Fields Institute Monographs #17, published by the American  Mathematics Society (2002).

  7. Editor:  ``Efficient Graph Representations'' (342 pages) by J. Spinrad,  Fields Institute Monographs #19, published by the American Mathematics Society (2003).

  

   Papers in Preparation

  1. D.G. Corneil, S. Olariu and L. Stewart, ``The LBFS structure and recognition of interval graphs'', revised version resubmitted. (Journal version of #73)

  2. D.G. Corneil, M. Habib, J-M. Lanlignel, B. Reed and U. Rotics, ``Polynomial time recognition of clique-width ≤ 3 graphs'', under revision.  (Journal version of #81)

  3. D.G. Corneil, E. Koehler, J-M. Lanlignel, ``On LBFS end-vertices'', submitted for publication.