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 196869 (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
cosupervised 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 coauthor
of over 100 refereed research
publications.
Referee
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.

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 on Graph
Theory, 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
appeared 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.97
122. (Extended abstract appeared
in 30th InternationalWorkshop on
Graph Theory, WG2004,
LNCS 3353 (Springer) (2004)
pp.6880.)

N. Przulj, D.G. Corneil and I.
Jurisica, \Ecient 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 distance
hereditary 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
unied 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", SIAM J.
Disc. Math. 22, 4 (2008)
pp.12771296. (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, ICALP2008, Part 1
LNCS 5125 (Springer) (2008)
pp.634645.

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 endvertices of
Lexicographic Breadth First
Searches", Discrete Applied
Mathematics, 158 (2010)
pp.434443.

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

D.G. Corneil, M. Habib, JM.
Lanlignel, B. Reed and U. Rotics,
\Polynomial time recognition
of cliquewidth 3 graphs",
Discrete Applied Mathematics,
160(6) (2012) pp.834865. (Ex
tended Abstract appeared in
Proceedings of LATIN2000
Conference, LNCS 1776 (Springer)
(2000), pp.126134.)

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.17171729. (Extended Ab
stract appeared as \Additive
spanners for circle graphs and
polygonal graphs", 34th Interna
tional Workshop on GraphTheoretic
Concepts in Computer Science, WG
2008, LNCS 5344
(Springer) (2008) pp.110121.)

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

E. Gioan, C. Paul, M. Tedder and
D.G. Corneil, \Practical and
ecient splitdecomposition
via graphlabelled trees",
Algorithmica, appeared online
March 2013, 55pp.

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

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.

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

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

D.G.
Corneil and J. Stacho, \The
structure and recognition of
C4free, ATfree graphs", in
preparation.

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

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

