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 196869
and joined the faculty at the University of Toronto in Jan. 1970. He is
crosslisted 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
cosupervised 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
coauthor 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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

H.D. Covvey, N.H.
McAlister and
D.G. Corneil, ``Computerassisted medicine: how soft is software?''
C.M.A. Journal, 121 (Sept. 1979), pp.673676.

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

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

D.G. Corneil, D.G.
Kirkpatrick
and M.M. Klawe, ``Generalized notions of pseudosimilarity in graphs'',
Proceedings of the Eleventh Southeastern Conference on Combinatorics,
Graph Theory and Computing (1980), pp.293308.

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

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

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

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

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

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

D.G. Kirkpatrick, M.M.
Klawe
and D.G. Corneil, ``On pseudosimilarity in trees'', JCT Series
B, 34, 3 (June 1983), pp.323339.

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

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

D.G. Corneil and M.
Goldberg,
``A nonfactorial algorithm for canonical numbering of a graph'',
Journal of Algorithms 5 (1984), pp.345362.

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

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

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

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

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

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

M. Conforti, D.G.
Corneil and
A.R. Mahjoub, ``Kicovers I:
complexity and polytopes'', Discrete
Mathematics, 58, 2 (1986), pp.121142.

S. Arnborg, D.G.
Corneil and A.
Proskurowski, ``Complexity of finding embeddings in a ktree'', SIAM
J. Alg. Disc. Meth., 8, 2 (1987), pp.277284.

D.G. Corneil and
J.M.
Keil, ``A dynamic programming approach to the dominating set problem on
ktrees'',
SIAM J. Alg. Disc. Meth., 8, 4 (1987), pp.535543.

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

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

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

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

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

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

F. Cheah and
D.G.
Corneil, ``The complexity of regular subgraph recognition'', Discrete
Applied Mathematics, 27, 12 (1990), pp.5968. Addendum 31, 3 (1991),
pp.309.

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

A. Wagner and
D.G.
Corneil, ``Embedding trees in a hypercube is NPcomplete'', SIAM
J. on Computing, 19, 3 (1990), pp.570590.

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

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

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

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

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

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

J.I. Brown and D.G.
Corneil,
``On uniquely Gkcolourable
graphs'', Quaestiones Mathematicae, 15, 4
(1992), pp.477487.

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

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

E.G. Anagnostou and
D.G.
Corneil, ``Polynomialtime instances of the minimum weight
triangulation problem'', Computational Geometry: Theory and
Applications, 3 (1993), pp.247259.

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

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

D.G. Corneil, S.
Olariu
and L. Stewart, ``A linear time algorithm to compute a dominating path
in an ATfree graph'', IPL, 54 (1995), pp.253257.

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

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

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

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

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

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

L. Cai and D.G.
Corneil, ``A
generalization of perfect graphs – iperfect
graphs'', J. Graph
Theory, 23, 1 (1996), pp.87103.

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

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

D.G. Corneil, S.
Olariu and L.
Stewart, ``Asteroidal triplefree graphs'', SIAM J. Disc.
Math. 10,3 (1997), pp.399430. (Available as TR9431, Dept. of
Computer Science, Old Dominion University), Extended abstract appeared
in Proc. GraphTheoretic Concepts in Computer Science, LNCS
790 (Springer) (1993), pp.211225.

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

P. Kearney and D.G.
Corneil,
``Tree powers'', J. Algorithms 29, (1998) pp.111131.

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

T.B. Moorhouse and
D.G.
Corneil, ``Completeness for intersection classes'', Discrete
Mathematics, 190, 13 (1998), pp.277286.

D.G. Corneil, S.
Olariu and L.
Stewart, ``LBFS orderings and cocomparability graphs'' Proc. of the
Tenth Annual ACMSIAM Symposium on Discrete Algorithms (SODA)
(1999), pp.883884.

D.G. Corneil, S.
Olariu and L.
Stewart, ``Linear time algorithms for dominating pairs in asteroidal
triplefree graphs'', SIAM J. on Computing, 28, 4 (1999),
pp.12841297. (Extended Abstract in Proceedings of 22nd
ICALP Conference, LNCS 944 (Springer) (1995), pp.292302.)

M. Li, D.G. Corneil
and E.
Mendelsohn, ``Pancyclicity and NPcompleteness in planar graphs'',
Discrete Applied Mathematics 98, 3 (2000), pp.219225.

D.G. Corneil, M.
Habib, JM.
Lanlignel, B. Reed and U. Rotics, ``Polynomial time recognition of
cliquewidth ≤
3 graphs'', (extended abstract) Proceedings of LATIN2000
Conference, LNCS 1776 (Springer) (2000), pp.126134.

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

D.G. Corneil, F.
Dragan, M.
Habib and C. Paul, ``Diameter determination on restricted graph
families'', Discrete Applied Mathematics 113, 23 (2001), pp.143166.
(Extended Abstract in Proceedings of 24th International Workshop in
GraphTheoretic Concepts in Computer Science, LNCS 1517 (Springer)
(1998),pp.192202.)

M.D. Hutton, J. Rose
and D.G.
Corneil. ``Automatic Generation of Synthetic Sequential Benchmark
Circuits'', IEEE Trans. on CAD, 21, 8 (2002) pp.928940.

D.G. Corneil, F.F.
Dragan and
E. Koehler, ``On the power of BFS to determine a graph's diameter'',
Networks 42 (2003), pp.209222. (Extended Abstract in Proceedings of
the LATIN2002 Conference, LNCS 2286, (Springer) (2002), pp.209223.)

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

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

L.C. Lau and D.G.
Corneil,
``Recognizing powers of proper interval, split and chordal graphs'',
SIAM J. Disc. Math., 18, 1 (2004) pp.83102.

N. Przulj, D.G.
Corneil and I.
Jurisica, ``Modeling Interactome: ScaleFree or Geometric?'',
Bioinformatics, 20, 18 (2004) pp.35083515.

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

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

D.G. Corneil and U.
Rotics,
``On the relationship between cliquewidth and treewidth'',
SIAM J. Computing , 34, 4 (2005) pp.825847. (Extended abstract
appeared in 27th International
Workshop on Graph Theory (WG2001), LNCS 2204 (Springer) (2001),
pp.7890.)

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

D.G. Corneil, E.
Koehler, S.
Olariu and L. Stewart, ``On subfamilies of ATfree graphs'',
SIAM J. Disc. Math., 20, 1 (2006), pp.105118. (Extended abstract
appeared as "Linear orderings of subfamilies of ATfree graphs", in
27th International Workshop
on Graph Theory (WG2001), LNCS 2204 (Springer) (2001), pp.241253.)

F.F. Dragan, C. Yan
and D.G.
Corneil, ``Collective tree spanners and routing in ATfree related
graphs'', Journal of Graph Algorithms and Applications (JGAA) 10, 2
(2006), pp.97122. (Extended abstract appeared in 30th
International Workshop on Graph Theory,
WG2004, LNCS 3353 (Springer) (2004) pp.6880.)

N. Przulj, D.G. Corneil and I. Jurisica, "Efficient
estimation of graphlet frequency distributions in proteinprotein
interaction networks", Bioinformatics 22, 8 (2006) pp.974980.

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

D.G. Corneil and R. Krueger, "A unified view of
graph searching", SIAM J. Disc. Math. 22, 4 (2008) pp.12591276.

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

M. Tedder, D. Corneil, M. Habib and C. Paul,
"Simpler lineartime modular decomposition via recursive factorizing
permutations", 35th International Colloquium on Automata,
Languages and Programming, ICALP 2008, Part 1 LNCS 5125 (Springer)
(2008) pp.634645.

F.F. Dragan, D.G. Corneil, E. Koehler and Y. Xiang,
"Additive spanners for circle graphs and polygonal graphs",
34th International Workshop on GraphTheoretic Concepts in Computer
Science, WG 2008, LNCS 5344 (Springer) (2008) pp.110121.

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

D.G. Corneil, E. Koehler, JM. Lanlignel, "On LBFS
endvertices", to appear Discrete Applied Mathematics.
Papers
in Preparation

D.G.
Corneil, M. Habib,
JM. Lanlignel,
B. Reed and U. Rotics, ``Polynomial time recognition of
cliquewidth ≤ 3
graphs'', under revision. (Journal
version of #80)

G.B.
Mertzios and D.G. Corneil, "Vertex splitting and the recognition of
trapezoid graphs", submitted for publication.

F.F. Dragan, D.G. Corneil, E. Koehler and Y. Xiang,
"Spanners of circle graphs and polygon graphs" (Journal version of
#100), in preparation.

E. Gioan, C. Paul, M. Tedder and D.G. Corneil,
"Practical and efficient splitdecomposition via graphlabelled trees",
in preparation.

E. Gioan, C. Paul, M. Tedder and D.G. Corneil,
"Quasilinear circle graph recognition", in preparation.

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

D.G. Corneil, B. Dalton and M. Habib, "The
application of Lexicographic Depth First Search to minimum path cover
problems in cocomparability graphs", in preparation.

