Professor David Wood

Publications

(as of April 25, 2024)

__________________________________________________________________

Preprints

[1]

M. Briański, R. Hickingbotham, D. R. Wood
Defective and clustered colouring of graphs with given girth, 2024
[arXiv] ©

[2]

V. Dujmović, P. Morin, D. R. Wood, D. Worley
Grid minors and products, 2024
[arXiv] ©

[3]

A. Girão, F. Illingworth, A. Scott, D. R. Wood
Non-homotopic drawings of multigraphs, 2023
[arXiv] ©

[4]

V. Dujmović, R. Hickingbotham, J. Hodor, G. Joret, H. La, P. Micek, P. Morin, C. Rambaud, D. R. Wood
The grid-minor theorem revisited, 2023
[arXiv] ©

[5]

V. Dujmović, L. Esperet, P. Morin, D. R. Wood
Proof of the clustered Hadwiger conjecture, 2023
[arXiv] ©

[6]

R. Hickingbotham, R. Steiner, D. R. Wood
Clustered colouring of odd-\(H\)-minor-free graphs, 2023
[arXiv] ©

[7]

M. Distel, R. Hickingbotham, M. T. Seweryn, D. R. Wood
Powers of planar graphs, blocking partitions and product structure, 2023
[arXiv] ©

[8]

Z. Dvořák, D. R. Wood
Product structure of graph classes with strongly sublinear separators, 2023
[arXiv] ©

[9]

V. Dujmović, G. Joret, P. Micek, P. Morin, D. R. Wood
Bounded-degree planar graphs do not have bounded-degree product structure, 2022
[arXiv] ©

[10]

É. Bonnet, O-j. Kwon, D. R. Wood
Reduced bandwidth: a qualitative strengthening of twin-width in minor-closed classes (and beyond), 2022
[arXiv] ©

[11]

T. Huynh, B. Mohar, R. Šámal, C. Thomassen, D. R. Wood
Universality in minor-closed graph classes, 2021
[arXiv] ©

[12]

C.-H. Liu, D. R. Wood
Clustered coloring of graphs excluding a subgraph and a minor, 2019
[arXiv] ©

[13]

C.-H. Liu, D. R. Wood
Clustered graph coloring and layered treewidth, 2019
[arXiv] ©

[14]

L. Addario-Berry, B. Reed, A. Scott, D. R. Wood
A logarithmic bound for the chromatic number of the associahedron, 2018
[arXiv] ©

__________________________________________________________________

Journal Publications

[15]

M. Distel, V. Dujmović, D. Eppstein, R. Hickingbotham, G. Joret, P. Micek, P. Morin, M. T. Seweryn, D. R. Wood.
Product structure extension of the Alon–Seymour–Thomas theorem
SIAM J. Discrete Math., accepted 5th April 2024
[arXiv] ©

[16]

R. Hickingbotham, F. Illingworth, B. Mohar, D. R. Wood.
Treewidth, circle graphs and circular drawings
SIAM J. Discrete Math. 38.2:965–987, 2024
[arXiv] ©

[17]

F. Illingworth, A. Scott, D. R. Wood.
Product structure of graphs with an excluded minor
Trans. Amer. Math. Soc., accepted 20th January 2024
[arXiv] ©

[18]

V. Dujmović, R. Hickingbotham, G. Joret, P. Micek, P. Morin, D. R. Wood.
The excluded tree minor theorem revisited
Combinatorics, Probability & Computing 33.1:85–90, 2024
[arXiv] ©

[19]

R. Hickingbotham, P. Jungeblut, L. Merker, D. R. Wood.
The product structure of squaregraphs
J. Graph Theory 105.2:179–191, 2024
[arXiv] ©

[20]

A. Girão, F. Illingworth, A. Scott, D. R. Wood.
Defective colouring of hypergraphs
Random Structures & Algorithms 64.3:663–675, 2024
[arXiv] [pdf] ©

[21]

R. Hickingbotham, D. R. Wood.
Shallow minors, graph products and beyond planar graphs
SIAM J. Discrete Math. 38.1:1057–1089, 2024
[arXiv] ©

[22]

D. Eppstein, R. Hickingbotham, S. Norin, L. Merker, M. T. Seweryn, D. R. Wood.
Three-dimensional graph products with unbounded stack-number
Discrete & Computational Geometry 2023
[arXiv] ©

[23]

R. Hickingbotham, D. R. Wood.
Structural properties of graph products
J. Graph Theory 2023
[arXiv] ©

[24]

R. Campbell, K. Clinch, M. Distel, J.P. Gollin, K. Hendrey, R. Hickingbotham, T. Huynh, F. Illingworth, Y. Tamitegama, J. Tan, D. R. Wood.
Product structure of graph classes with bounded treewidth
Combinatorics, Probability & Computing 33.3:351–376, 2024
[arXiv] [publication] ©

[25]

D. R. Wood.
2-Layer graph drawings with bounded pathwidth
J. Graph Algorithms & Applications 27.9:843–851, 2023
[arXiv] ©

[26]

L. Esperet, D. R. Wood.
Colouring strong products
European J. Combinatorics 103847, 2023
[arXiv] ©

[27]

Y. Gu, Y. Jiang, X. Zhu, D. R. Wood.
Refined list version of Hadwiger’s conjecture
SIAM J. Discrete Math. 37.3:1738–1750, 2023
[arXiv] [pdf] ©

[28]

R. Campbell, M. Distel, J.P. Gollin, D. Harvey, K. Hendrey, R. Hickingbotham, B. Mohar, D. R. Wood.
Graphs of linear growth have bounded treewidth
Electronic J. Combinatorics 30:P3.1, 2023
[arXiv] ©

[29]

C.-H. Liu, D. R. Wood.
Clustered coloring of graphs with bounded layered treewidth and bounded degree
European J. Combinatorics 103730, 2023
[arXiv] ©

[30]

V. Dujmović, P. Morin, D. R. Wood.
Graph product structure for non-minor-closed classes
J. Combinatorial Theory Series B 162:34–67, 2023
[arXiv] ©

[31]

S. Norin, A. Scott, D. R. Wood.
Clustered colouring of graph classes with bounded treedepth or pathwidth
Combinatorics, Probability & Computing 32:122–133, 2023
[arXiv] [pdf]

[32]

M. Distel, R. Hickingbotham, T. Huynh, D. R. Wood.
Improved product structure for graphs on surfaces
Discrete Math. & Theoret. Comput. Sci. 24.2:#6, 2022
[arXiv] ©

[33]

T. Chan, D. Král’, B. Mohar, D. R. Wood.
Inducibility and universality for trees
Combinatorial Theory 2.3:#2, 2022
[arXiv]

[34]

I. Wanless, D. R. Wood.
A general framework for hypergraph colouring
SIAM J. Discrete Math. 36.3:1663–1677, 2022
[arXiv] [pdf]

[35]

K. Hendrey, S. Norin, D. R. Wood.
Extremal functions for sparse minors
Advances in Combinatorics 2022:#5
[arXiv]

[36]

T. Ueckerdt, W. Yi, D. R. Wood.
An improved planar graph product structure theorem
Electronic J. Combinatorics 29:P2.51, 2022
[arXiv]

[37]

P. Bose, V. Dujmović, M. Javarsineh, P. Morin, D. R. Wood.
Separating layered treewidth and row treewidth
Discrete Math. & Theoret. Comput. Sci. 24(1):#18, 2022
[arXiv]

[38]

T. Huynh, G. Joret, D. R. Wood.
Subgraph densities in a surface
Combinatorics, Probability & Computing 31.5:812–839, 2022
[arXiv] [pdf]

[39]

C.-H. Liu, D. R. Wood.
Clustered variants of Hajós’ conjecture
J. Combinatorial Theory Series B 152:27–54, 2022
[arXiv] [pdf]

[40]

V. Dujmović, L. Esperet, P. Morin, B. Walczak, D. R. Wood.
Clustered 3-colouring graphs of bounded degree
Combinatorics, Probability & Computing 31.1:123–135, 2022
[arXiv] [pdf]

[41]

V. Dujmović, D. Eppstein, R. Hickingbotham, P. Morin, D. R. Wood.
Stack-number is not bounded by queue-number
Combinatorica 42:151–164, 2022
[arXiv] [pdf]

[42]

T. Huynh, D. R. Wood.
Tree densities of sparse graph classes
Canadian J. Math. 74.5:1385–1404, 2022
[arXiv] [pdf]

[43]

M. Aprile, S. Fiorini, T. Huynh, G. Joret, D. R. Wood.
Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond
Electronic J. Combinatorics 28:P4.47, 2021
[arXiv]

[44]

D. R. Wood.
Nonrepetitive graph colouring
Electronic J. Combinatorics DS24, 2021
[pdf]

[45]

N. Kamčev, A. Liebenau, L. Yepremyan, D. R. Wood.
The size Ramsey number of graphs with bounded treewidth
SIAM J. Discrete Math. 35.1:281–293, 2021
[arXiv] [pdf]

[46]

A. Scott, D. R. Wood.
Separation dimension and degree
Math. Proc. Cambridge Philos. Soc. 170.3:549–558, 2021
[arXiv] [pdf]

[47]

T. Huynh, G. Joret, P. Micek, D. R. Wood.
Seymour’s conjecture on 2-connected graphs of large pathwidth
Combinatorica 40:839–868, 2020
[arXiv] [pdf] ©Springer

[48]

S. Norin, B. Reed, A. Thomason, D. R. Wood.
A lower bound on the average degree forcing a minor
Electronic J. Combinatorics 27:2.4, 2020
[arXiv] [pdf]

[49]

V. Dujmović, L. Esperet, G. Joret, B. Walczak, D. R. Wood.
Planar graphs have bounded nonrepetitive chromatic number
Advances in Combinatorics 2020:#5
[arXiv] [pdf]

[50]

V. Dujmović, G. Joret, P. Micek, P. Morin, T. Ueckerdt, D. R. Wood.
Planar graphs have bounded queue-number
J. ACM 67.4:22, 2020
[arXiv] [pdf] ©ACM

[51]

A. Scott, D. R. Wood.
Better bounds for poset dimension and boxicity
Trans. Amer. Math. Soc. 373.3:2157–2172, 2020
[arXiv] [pdf] [MathSciNet] ©AMS

[52]

F. Havet, B. Reed, M. Stein, D. R. Wood.
A variant of the Erdős-Sós conjecture
J. Graph Theory 94.1:131–158, 2020
[arXiv] [pdf] ©Wiley

[53]

V. Dujmović, D. Eppstein, G. Joret, P. Morin, D. R. Wood.
Minor-closed graph classes with bounded layered pathwidth
SIAM J. Discrete Math. 34.3:1693–1709, 2020
[arXiv] [pdf]

[54]

S. Norin, A. Scott, P. Seymour, D. R. Wood.
Clustered colouring in minor-closed classes
Combinatorica 39.6:1387–1412, 2019
[arXiv] [MathSciNet] [pdf] ©

[55]

F. Knox, B. Mohar, D. R. Wood.
A golden ratio inequality on vertex degrees of graphs
American Math. Monthly 126.8:742–747, 2019
[arXiv] [MathSciNet] [pdf] ©MAA

[56]

K. Hendrey, D. R. Wood.
Defective and clustered colouring of sparse graphs
Combinatorics, Probability & Computing 28.5:791–810, 2019
[arXiv] [MathSciNet] [pdf] ©

[57]

A. Scott, P. Seymour, D. R. Wood.
Bad news for chordal partitions
J. Graph Theory 90.1:5–12, 2019
[arXiv] [MathSciNet] [pdf] ©Wiley

[58]

M. J. Bannister, W. E. Devanny, V. Dujmović, D. Eppstein, D. R. Wood.
Track layouts, layered path decompositions, and leveled planarity
Algorithmica 81.4:1561–1583, 2019
[arXiv] [MathSciNet] [pdf] ©Springer

[59]

P. Wollan, D. R. Wood.
Nonrepetitive colourings of graphs excluding a fixed immersion or topological minor
J. Graph Theory 91.3:259–266, 2019
[arXiv] [MathSciNet] [pdf] ©Wiley

[60]

S.-i. Oum, P. Ossona de Mendez, D. R. Wood.
Defective colouring of graphs excluding a subgraph or minor
Combinatorica 39.2:377–410, 2019
[arXiv] [MathSciNet] [pdf] ©Springer

[61]

T. E. Wilson, D. R. Wood.
Anagram-free colorings of graph subdivisions
SIAM J. Discrete Math. 32.3:2346–2360, 2018
[arXiv] [MathSciNet] [pdf] ©

[62]

V. Dujmović, D. R. Wood.
Thickness and antithickness of graphs
J. Computational Geometry 9.1:356–386, 2018
[arXiv] [MathSciNet] [pdf] ©

[63]

D. Harvey, D. R. Wood.
The treewidth of line graphs
J. Combinatorial Theory Series B 132:157–179, 2018
[arXiv] [MathSciNet] [pdf] ©Elsevier

[64]

T. E. Wilson, D. R. Wood.
Anagram-free graph colouring
Electronic J. Combinatorics 25:2.20, 2018
[arXiv] [MathSciNet] [pdf] ©

[65]

D. R. Wood.
Defective and clustered graph colouring
Electronic J. Combinatorics #DS23, 2018
[arXiv] [pdf] ©

[66]

J. van den Heuvel, D. R. Wood.
Improper colourings inspired by Hadwiger’s conjecture
J. London Math. Society 98.1:129–148, 2018
[arXiv] [MathSciNet] [pdf] ©LMS

[67]

K. Hendrey, D. R. Wood.
The extremal function for Petersen minors
J. Combinatorial Theory Series B 131:220–253, 2018
[arXiv] [MathSciNet] [pdf] ©

[68]

V. Dujmović, G. Joret, P. Morin, S. Norin, D. R. Wood.
Orthogonal tree decompositions of graphs
SIAM J. Discrete Math. 32.2:839–863, 2018. Corrigendum: SIAM J. Discrete Math. 32.4:3003–3004, 2018
[arXiv] [MathSciNet] [MathSciNet] [publication] [publication] [pdf]

[69]

G. Joret, D. R. Wood.
\(K_{4}\)-minor-free induced subgraphs of sparse connected graphs
SIAM J. Discrete Math. 32.1:123–147, 2018
[arXiv] [MathSciNet] [pdf] ©SIAM

[70]

D. Best, K. Hendrey, I. Wanless, T. E. Wilson, D. R. Wood.
Transversals in Latin arrays with many distinct symbols
J. Combinatorial Designs 26.2:84–96, 2018
[arXiv] [MathSciNet] [pdf] ©Wiley

[71]

C. McDiarmid, D. R. Wood.
Edge-maximal graphs on surfaces
Canadian J. Math. 70.4:925–942, 2018
[arXiv] [MathSciNet] [pdf] ©CMS

[72]

V. Dujmović, P. Morin, D. R. Wood.
Layered separators in minor-closed graph classes with applications
J. Combinatorial Theory Series B 127:111–147, 2017
[arXiv] [MathSciNet] [pdf] ©Elsevier

[73]

B. Mohar, B. Reed, D. R. Wood.
Colourings with bounded monochromatic components in graphs of given circumference
Australasian J. Combinatorics 69.2:236–242, 2017
[arXiv] [MathSciNet] [pdf] ©

[74]

S. Kreutzer, S.-i. Oum, P. Seymour, D. van der Zypen, D. R. Wood.
Majority colourings of digraphs
Electronic J. Combinatorics 24:2.25, 2017
[arXiv] [MathSciNet] [pdf] ©

[75]

V. Dujmović, D. Eppstein, D. R. Wood.
Structure of graphs with locally restricted crossings
SIAM J. Discrete Math. 31.2:805–824, 2017
[arXiv] [MathSciNet] [pdf] ©SIAM

[76]

B. Jia, D. R. Wood.
Hadwiger’s conjecture for \(\ell \)-link graphs
J. Graph Theory 84.4:460–476, 2017
[arXiv] [MathSciNet] [pdf] ©Wiley

[77]

D. Harvey, D. R. Wood.
Parameters tied to treewidth
J. Graph Theory 84.4:364–385, 2017
[arXiv] [MathSciNet] [pdf] ©Wiley

[78]

J. Cardinal, C. D. Tóth, D. R. Wood.
General position subsets and independent hyperplanes in \(d\)-space
J. Geometry 108.1:33–43, 2017
[arXiv] [MathSciNet] [pdf] ©Springer

[79]

G. Pineda-Villavicencio, E. Nevo, D. R. Wood.
On the maximum order of graphs embedded in surfaces
J. Combinatorial Theory Series B 119:28–41, 2016
[arXiv] [MathSciNet] [pdf] ©Elsevier

[80]

V. Dujmović, G. Joret, J. Kozik, D. R. Wood.
Nonrepetitive colouring via entropy compression
Combinatorica 36.6:661–686, 2016
[arXiv] [MathSciNet] [pdf] ©Springer

[81]

B. Reed, D. R. Wood.
Forcing a sparse minor
Combinatorics, Probability & Computing 25.2:300–322, 2016. Corrigendum: Combinatorics, Probability & Computing 25.2:323, 2016

[arXiv] [MathSciNet] [publication] [publication] [pdf]
©Cambridge University Press

[82]

G. Xu, S. Zhou, D. R. Wood.
Hadwiger’s conjecture for 3-arc graphs
Electronic J. Combinatorics 23:4.21, 2016
[arXiv] [MathSciNet] [pdf] ©

[83]

D. R. Wood.
Cliques in graphs excluding a complete graph minor
Electronic J. Combinatorics 23:3.18, 2016
[MathSciNet] [arXiv] [pdf] ©

[84]

T. Grubman, A. Şekercioğlu, D. R. Wood.
Partitioning de Bruijn graphs into fixed-length cycles for robot identification and tracking
Discrete Applied Mathematics 213:101–113, 2016
[MathSciNet] [arXiv] [pdf] ©Elsevier

[85]

D. Harvey, D. R. Wood.
Average degree conditions forcing a minor
Electronic J. Combinatorics 23:1.42, 2016
[MathSciNet] [arXiv] [pdf] ©

[86]

V. Dujmović, A. Sidiropoulos, D. R. Wood.
Layouts of graph expanders
Chicago J. Theoretical Comput. Sci. 16:Article 1, 2016
[MathSciNet] [arXiv] [pdf] ©

[87]

H. Alt, M. Payne, J. M. Schmidt, D. R. Wood.
Thoughts on Barnette’s conjecture
Australasian J. Combinatorics 64.2:354–365, 2016
[MathSciNet] [arXiv] [pdf] ©

[88]

D. Harvey, D. R. Wood.
Cycles of given size in a dense graph
SIAM J. Discrete Math. 29.4:2336–2349, 2015
[MathSciNet] [arXiv] [pdf] ©SIAM

[89]

G. Pineda-Villavicencio, D. R. Wood.
The degree-diameter problem for sparse graph classes
Electronic J. Combinatorics 22:2.46, 2015
[MathSciNet] [arXiv] [pdf] ©

[90]

E. Marshall, D. R. Wood.
Circumference and pathwidth of highly connected graphs
J. Graph Theory 79.3:222–232, 2015
[MathSciNet] [arXiv] [pdf] ©Wiley

[91]

J. Barát, V. Dujmović, G. Joret, M. Payne, L. Scharf, D. Schymura, P. Valtr, D. R. Wood.
Empty pentagons in point sets with collinearities
SIAM J. Discrete Math. 29.1:198–209, 2015
[MathSciNet] [arXiv] [pdf] ©SIAM

[92]

D. Harvey, D. R. Wood.
Treewidth of the line graph of a complete graph
J. Graph Theory 79.1:48–54, 2015
[MathSciNet] [arXiv] [pdf] ©Wiley

[93]

F. Frati, M. Kaufmann, J. Pach, C. D. Tóth, D. R. Wood.
On the upward planarity of mixed plane graphs
J. Graph Algorithms & Applications 18.2:253–279, 2014
[MathSciNet] [pdf] ©

[94]

M. Payne, D. R. Wood.
Progress on Dirac’s conjecture
Electronic J. Combinatorics 21:2.12, 2014
[MathSciNet] [arXiv] [pdf] ©

[95]

M. Payne, J. M. Schmidt, D. R. Wood.
Which point sets admit a \(k\)-angulation?
J. Computational Geometry 5.1:42–55, 2014
[MathSciNet] [arXiv] [pdf] ©

[96]

D. Harvey, D. R. Wood.
Treewidth of the Kneser graph and the Erdős-Ko-Rado Theorem
Electronic J. Combinatorics 21:1.48, 2014
[MathSciNet] [arXiv] [pdf] ©

[97]

F. Hurtado, G. Liotta, D. R. Wood.
Proximity drawings of high-degree trees
International J. of Computational Geometry and Applications 23:213–230, 2013
[MathSciNet] [arXiv] [pdf]

[98]

V. Dujmović, D. Harvey, G. Joret, B. Reed, D. R. Wood.
A linear-time algorithm for finding a complete graph minor in a dense graph
SIAM J. Discrete Math. 27.4:1770–1774, 2013
[MathSciNet] [arXiv] [pdf] ©SIAM

[99]

M. Payne, D. R. Wood.
On the general position subset selection problem
SIAM J. Discrete Math. 27.4:1727-1733, 2013
[MathSciNet] [arXiv] [pdf] ©SIAM

[100]

G. Joret, S. Fiorini, D. R. Wood.
Excluded forest minors and the Erdős-Pósa property
Combinatorics, Probability & Computing 22.5:700–721, 2013
[MathSciNet] [arXiv] [pdf] ©Cambridge University Press

[101]

R. Fabila-Monroy, D. R. Wood.
Rooted \(K_4\)-minors
Electronic J. Combinatorics 20:2.64, 2013
[MathSciNet] [arXiv] [pdf] ©

[102]

D. Wakeham, D. R. Wood.
On multiplicative Sidon sets
INTEGERS 13:A26, 2013
[MathSciNet] [arXiv] [pdf] ©

[103]

V. Dujmović, F. Frati, G. Joret, D. R. Wood.
Nonrepetitive colourings of planar graphs with \(O(\log n)\) colours
Electronic J. Combinatorics 20:1.51, 2013
[MathSciNet] [arXiv] [pdf] ©

[104]

G. Joret, D. R. Wood.
Complete graph minors and the graph minor structure theorem
J. Combinatorial Theory Series B 103:61–74, 2013
[MathSciNet] [arXiv] [pdf] ©

[105]

D. R. Wood.
Treewidth of cartesian products of highly connected graphs
J. Graph Theory 73.3:318–321, 2013
[MathSciNet] [arXiv] [pdf] ©Wiley

[106]

P. Bose, V. Dujmović, F. Hurtado, J. Iacono, S. Langerman, H. Meijer, V. Sacristán, M. Saumell, D. R. Wood.
Proximity graphs: \(E\), \(\delta \), \(\Delta \), \(\chi \) and \(\omega \)
International J. of Computational Geometry and Applications 22.5:439-469, 2012
[MathSciNet] [pdf]

[107]

V. Dujmović, G. Joret, D. R. Wood.
An improved bound for first-fit on posets without two long incomparable chains
SIAM J. Discrete Math. 26.3:1068-1075, 2012
[MathSciNet] [arXiv] [pdf] ©SIAM

[108]

M. Payne, A. Pór, P. Valtr, D. R. Wood.
On the connectivity of visibility graphs
Discrete & Computational Geometry 48.3:669–681, 2012
[MathSciNet] [arXiv] [pdf] ©Springer

[109]

R. Fabila-Monroy, D. R. Wood.
Colouring the triangles determined by a point set
J. Computational Geometry 3:86–101, 2012
[MathSciNet] [arXiv] [publication] [pdf] ©

[110]

S. Fiorini, G. Joret, D. O. Theis, D. R. Wood.
Small minors in dense graphs
European J. Combinatorics 33.6:1226-1245, 2012
[MathSciNet] [arXiv] [pdf] ©

[111]

G. Joret, D. R. Wood.
Nordhaus-Gaddum for treewidth
European J. Combinatorics 33.4:488–490, 2012
[MathSciNet] [arXiv] [pdf] ©

[112]

B. Reed, D. R. Wood.
Polynomial treewidth forces a large grid-like-minor
European J. Combinatorics 33.3:374–379, 2012
[MathSciNet] [arXiv] [pdf] ©

[113]

J. Nešetřil, P. Ossona de Mendez, D. R. Wood.
Characterisations and examples of graph classes with bounded expansion
European J. Combinatorics 33.3:350–373, 2012
[MathSciNet] [arXiv] [pdf] ©Elsevier

[114]

R. Fabila-Monroy, D. Flores-Peñaloza, C. Huemer, F. Hurtado, J. Urrutia, D. R. Wood.
Token graphs
Graphs and Combinatorics 28.3:365–380, 2012
[arXiv] [MathSciNet] [pdf] ©Springer

[115]

J. Barát, G. Joret, D. R. Wood.
Disproof of the list Hadwiger conjecture
Electronic J. Combinatorics 18:1.232, 2011
[MathSciNet] [arXiv] [publication] [pdf] ©

[116]

V. Dujmović, D. R. Wood.
On the book thickness of \(k\)-trees
Discrete Math. & Theoret. Comput. Sci. 13.3:39-44, 2011
[MathSciNet] [arXiv] [pdf] ©DMTCS

[117]

D. R. Wood.
Clique minors in cartesian products of graphs
New York J. Math. 17:627–682, 2011
[MathSciNet] [arXiv] [pdf] ©

[118]

D. R. Wood.
On the number of maximal independent sets in a graph
Discrete Math. & Theoret. Comput. Sci. 13.3:17–20, 2011
[MathSciNet] [arXiv] [pdf] ©DMTCS

[119]

D. R. Wood.
Colouring the square of the cartesian product of trees
Discrete Math. & Theoret. Comput. Sci. 13.2:109–112, 2011
[MathSciNet] [arXiv] [pdf] ©DMTCS

[120]

V. Dujmović, G. Fijavž, G. Joret, T. Sulanke, D. R. Wood.
On the maximum number of cliques in a graph embedded in a surface
European J. Combinatorics 32.8:1244–1252, 2011
[MathSciNet] [arXiv] [pdf] ©

[121]

Z. Abel, B. Ballinger, P. Bose, S. Collette, V. Dujmović, F. Hurtado, S. D. Kominers, S. Langerman, A. Pór, D. R. Wood.
Every large point set contains many collinear points or an empty pentagon
Graphs and Combinatorics 27.1:47–60, 2011
[MathSciNet] [arXiv] [pdf] ©Springer

[122]

D. R. Wood, S. Linusson.
Thomassen’s choosability argument revisited
SIAM J. Discrete Math. 24.4:1632–1637, 2010
[MathSciNet] [arXiv] [pdf] ©SIAM

[123]

G. Fijavž, D. R. Wood.
Graph minors and minimum degree
Electronic J. Combinatorics 17:1.151, 2010
[MathSciNet] [arXiv] [pdf] ©

[124]

D. R. Wood.
Contractibility and the Hadwiger Conjecture
European J. Combinatorics 31.8:2102–2109, 2010
[MathSciNet] [arXiv] [pdf] ©

[125]

A. Pór, D. R. Wood.
On visibility and blockers
J. Computational Geometry 1:29–40, 2010
[MathSciNet] [arXiv] [pdf] ©

[126]

G. Joret, D. R. Wood.
Irreducible triangulations are small
J. Combinatorial Theory Series B 100.5:446–455, 2010
[MathSciNet] [arXiv] [pdf] ©

[127]

O. Aichholzer, S. Cabello, R. Fabila-Monroy, D. Flores-Peñaloza, T. Hackl, C. Huemer, F. Hurtado, D. R. Wood.
Edge-removal and non-crossing configurations in geometric graphs
Discrete Math. & Theoret. Comput. Sci. 12.1:75–86, 2010
[MathSciNet] [pdf] ©DMTCS

[128]

C. Hernando, M. Mora, I. M. Pelayo, C. Seara, D. R. Wood.
Extremal graph theory for metric dimension and diameter
Electronic J. Combinatorics 17:1.30, 2010
[MathSciNet] [arXiv] [pdf] ©

[129]

A. Pór, D. R. Wood.
Colourings of the cartesian product of graphs and multiplicative Sidon sets
Combinatorica 29.4:449–466, 2009
[MathSciNet] [arXiv] [pdf] ©Springer

[130]

B. Reed, D. R. Wood.
A linear time algorithm to find a separator in a graph excluding a minor
ACM Transactions on Algorithms 5.4:39, 2009
[MathSciNet] [pdf] ©ACM

[131]

P. Bose, V. Dujmović, F. Hurtado, S. Langerman, P. Morin, D. R. Wood.
A polynomial bound for untangling geometric planar graphs
Discrete & Computational Geometry 42.4:570–585, 2009
[MathSciNet] [arXiv] [pdf] ©Springer

[132]

R. Fabila-Monroy, D. Flores-Peñaloza, C. Huemer, F. Hurtado, J. Urrutia, D. R. Wood.
On the chromatic number of some flip graphs
Discrete Math. & Theoret. Comput. Sci. 11.2:47–56, 2009
[MathSciNet] ©DMTCS

[133]

O. Aichholzer, S. Bereg, A. Dumitrescu, A. García, C. Huemer, F. Hurtado, M. Kano, A. Márquez, S. Smorodinsky, D. Souvaine, J. Urrutia, D. R. Wood.
Compatible geometric matchings
Computational Geometry: Theory & Applications 42.6–7:617–626, 2009
[MathSciNet] [arXiv] [pdf] ©Elsevier

[134]

D. R. Wood.
On tree-partition-width
European J. Combinatorics 30:1245–1253, 2009
[MathSciNet] [arXiv] [pdf] ©Elsevier

[135]

E. D. Demaine, F. Gomez-Martin, H. Meijer, D. Rappaport, P. Taslakian, G. T. Toussaint, T. Winograd, D. R. Wood.
The distance geometry of music
Computational Geometry: Theory & Applications 42.5:429–454, 2009
[MathSciNet] [pdf] ©Elsevier

[136]

V. Dujmović, M. Fellows, M. Kitching, G. Liotta, C. McCartin, N. Nishimura, P. Ragde, F. Rosamond, and S. Whitesides, D. R. Wood.
On the parameterized complexity of layered graph drawing
Algorithmica 52.2:267–292, 2008
[MathSciNet] [pdf] ©Springer

[137]

P. Carmi, V. Dujmović, P. Morin, D. R. Wood.
Distinct distances in graph drawings
Electronic J. Combinatorics 15:1.107, 2008
[MathSciNet] [pdf] ©

[138]

J. Barát, D. R. Wood.
Notes on nonrepetitive graph colouring
Electronic J. Combinatorics 15:1.99, 2008. Corrigendum added 2014
[MathSciNet] [pdf] ©

[139]

P. Bose, V. Dujmović, D. Krizanc, S. Langerman, P. Morin, S. Wuhrer, D. R. Wood.
A characterization of the degree sequences of 2-trees
J. Graph Theory 58.3:191–209, 2008
[MathSciNet] [arXiv] [pdf] ©Wiley

[140]

D. R. Wood.
Bounded-degree graphs have arbitrarily large queue-number
Discrete Math. & Theoret. Comput. Sci. 10.1:27–34, 2008
[MathSciNet] [arXiv] [pdf] ©DMTCS

[141]

D. Bokal, G. Fijavž, D. R. Wood.
The minor crossing number of graphs with an excluded minor
Electronic J. Combinatorics 15:1.4, 2008
[MathSciNet] [arXiv] [pdf] ©

[142]

D. R. Wood.
On the oriented chromatic number of dense graphs
Contributions to Discrete Math. 2.2:145–152, 2007
[MathSciNet] [arXiv] [pdf] ©University of Calgary

[143]

J. Kára, J. Kratochvil, D. R. Wood.
On the complexity of the balanced vertex ordering problem
Discrete Math. & Theoret. Comput. Sci. 9.1:193–202, 2007
[MathSciNet] [pdf] ©DMTCS

[144]

D. R. Wood.
Independent sets in graphs with an excluded clique minor
Discrete Math. & Theoret. Comput. Sci. 9.1:171–177, 2007
[MathSciNet] [arXiv] [pdf] ©DMTCS

[145]

V. Dujmović, M. Suderman, D. R. Wood.
Graph drawings with few slopes
Computational Geometry: Theory & Applications 38:181–193, 2007
[MathSciNet] [arXiv] [pdf] ©Elsevier

[146]

V. Dujmović, D. Eppstein, M. Suderman, D. R. Wood.
Drawings of planar graphs with few slopes and segments
Computational Geometry: Theory & Applications 38:194–212, 2007
[MathSciNet] [arXiv] [pdf] ©Elsevier

[147]

D. R. Wood.
On the maximum number of cliques in a graph
Graphs and Combinatorics 23.3:337–352, 2007
[MathSciNet] [arXiv] [pdf] ©Springer

[148]

D. R. Wood, J. A. Telle.
Planar decompositions and the crossing number of graphs with an excluded minor
New York J. Math. 13:117–146, 2007
[MathSciNet] [arXiv] [pdf] ©

[149]

J. Cáceres, C. Hernando, M. Mora, I. M. Pelayo, M. L. Puertas, C. Seara, D. R. Wood.
On the metric dimension of cartesian products of graphs
SIAM J. Discrete Math. 21.2:423–441, 2007
[MathSciNet] [arXiv] [pdf] ©SIAM

[150]

V. Dujmović, D. R. Wood.
Graph treewidth and geometric thickness parameters
Discrete & Computational Geometry 37.4:641–670, 2007
(Note that the conjecture on line 2 of page 665 of this paper was disproved by Lenwood Heath [FOCS 1984].) [MathSciNet] [arXiv] [pdf] ©Springer

[151]

A. Pór, D. R. Wood.
No-three-in-line-in-3D
Algorithmica 47.4:481–488, 2007
[MathSciNet] [pdf] ©Springer

[152]

P. Bose, J. Czyzowicz, Z. Gao, P. Morin, D. R. Wood.
Simultaneous diagonal flips in plane triangulations
J. Graph Theory 54.4:307–330, 2007
[arXiv] [MathSciNet] [pdf] ©Wiley

[153]

D. R. Wood.
Vertex partitions of chordal graphs
J. Graph Theory 53.2:167–172, 2006
[arXiv] [MathSciNet] [pdf] ©Wiley

[154]

V. Dujmović, D. R. Wood.
Upward three-dimensional grid drawings of graphs
Order 23:1–20, 2006
[MathSciNet] [pdf] ©Springer

[155]

D. R. Wood.
Drawing a graph in a hypercube
Electronic J. Combinatorics 13:1.73, 2006
[MathSciNet] [ps] [pdf] ©

[156]

V. Dujmović, M. Fellows, M. Hallett, M. Kitching, G. Liotta, C. McCartin, N. Nishimura, P. Ragde, F. Rosamond, M. Suderman, and S. Whitesides, D. R. Wood.
A fixed-parameter approach to two-layer planarization
Algorithmica 45.2:159–182, 2006
[MathSciNet] [pdf] ©Springer

[157]

P. Bose, V. Dujmović, D. R. Wood.
Induced subgraphs of bounded degree and bounded treewidth
Contributions to Discrete Math. 1.1:88–105, 2006
[arXiv] [MathSciNet] [pdf] ©

[158]

P. Bose, F. Hurtado, E. Rivera-Campo, D. R. Wood.
Partitions of complete geometric graphs into plane trees
Computational Geometry: Theory & Applications 34.2:116–125, 2006
[MathSciNet] [pdf] ©Elsevier

[159]

T. Biedl, T. Thiele, D. R. Wood.
Three-dimensional orthogonal graph drawing with optimal volume
Algorithmica 44.3:233–255, 2006
[MathSciNet] [pdf] ©Springer

[160]

J. Barát, J. Matoušek, D. R. Wood.
Bounded-degree graphs have arbitrarily large geometric thickness
Electronic J. Combinatorics 13:1.3, 2006
[MathSciNet] [ps] [pdf] ©

[161]

D. R. Wood.
Characterisations of intersection graphs by vertex orderings
Australasian J. Combinatorics 34:261–268, 2006
[MathSciNet] [pdf] ©Combinatorial Mathematics Society of Australasia

[162]

D. R. Wood.
Queue layouts of graph products and powers
Discrete Math. & Theoret. Comput. Sci. 7:255–268, 2005
[MathSciNet] [ps] [pdf] ©DMTCS

[163]

V. Dujmović, D. R. Wood.
Stacks, queues and tracks: Layouts of graph subdivisions
Discrete Math. & Theoret. Comput. Sci. 7:155–202, 2005
[MathSciNet] [ps] [pdf] ©DMTCS

[164]

J. Kára, A. Pór, D. R. Wood.
On the chromatic number of the visibility graph of a set of points in the plane
Discrete & Computational Geometry 34.3:497–506, 2005
[MathSciNet] [pdf] ©Springer

[165]

D. R. Wood.
Acyclic, star and oriented colourings of graph subdivisions
Discrete Math. & Theoret. Comput. Sci. 7.1:37–50, 2005
[MathSciNet] [ps] [pdf] ©DMTCS

[166]

V. Dujmović, P. Morin, D. R. Wood.
Layout of graphs with bounded tree-width
SIAM J. Computing 34.3:553–579, 2005
[MathSciNet] [ps] [pdf] ©SIAM

[167]

T. Biedl, T. Chan, Y. Ganjali, M. Hajiaghayi, D. R. Wood.
Balanced vertex-orderings of graphs
Discrete Applied Mathematics 148.1:27–48, 2005
[MathSciNet] [pdf] ©Elsevier

[168]

D. R. Wood.
Grid drawings of k-colourable graphs
Computational Geometry: Theory & Applications 30.1:25–28, 2005
[MathSciNet] [pdf] ©Elsevier

[169]

P. Morin, D. R. Wood.
Three-dimensional 1-bend graph drawings
J. Graph Algorithms & Applications 8.3:357–366, 2004
[MathSciNet] [ps] [pdf] ©JGAA

[170]

V. Dujmović, A. Pór, D. R. Wood.
Track layouts of graphs
Discrete Math. & Theoret. Comput. Sci. 6.2:497–522, 2004
[MathSciNet] [ps] [pdf] ©DMTCS

[171]

P. Bose, J. Czyzowicz, P. Morin, D. R. Wood.
The maximum number of edges in a three-dimensional grid-drawing
J. Graph Algorithms & Applications 8.1:21–26, 2004
[MathSciNet] [pdf] ©JGAA

[172]

V. Dujmović, D. R. Wood.
On linear layouts of graphs
Discrete Math. & Theoret. Comput. Sci. 6.2:339–358, 2004
[MathSciNet] [ps] [pdf] ©DMTCS

[173]

D. R. Wood.
A note on colouring the plane grid
Geombinatorics XIII.4:193–196, 2004
[ps] [pdf] ©Center for Excellence in Mathematical Education, Colorado

[174]

D. R. Wood.
Minimising the number of bends and volume in 3-dimensional orthogonal graph drawings with a diagonal vertex layout
Algorithmica 39:235–253, 2004
[MathSciNet] [pdf] ©Springer

[175]

M. Houle, A. Symvonis, D. R. Wood.
Dimension-exchange algorithms for token distribution on tree-connected architectures
J. Parallel and Distributed Computing 64.5:591–605, 2004
[pdf] ©Elsevier

[176]

P. Bose, M. Smid, D. R. Wood.
Light edges in degree-constrained graphs
Discrete Mathematics 282.1–3:35–41, 2004
[MathSciNet] [pdf] ©Elsevier

[177]

D. R. Wood.
Bounded degree acyclic decompositions of digraphs
J. Combinatorial Theory Series B 90:309–313, 2004
[MathSciNet] [pdf] ©Elsevier

[178]

D. R. Wood.
Geometric thickness in a grid
Discrete Mathematics 273.1–3:221–234, 2003
[MathSciNet] [pdf] ©Elsevier

[179]

D. R. Wood.
Lower bounds for the number of bends in three-dimensional orthogonal graph drawings
J. Graph Algorithms & Applications 7.1:33–77, 2003
[MathSciNet] [ps] ©JGAA

[180]

D. R. Wood.
Optimal three-dimensional orthogonal graph drawing in the general position model
Theoretical Computer Science 299.1–3: 151–178, 2003
[MathSciNet] [ps] [pdf] ©Elsevier

[181]

D. R. Wood.
Degree constrained book embeddings
J. Algorithms 45.2:144–154, 2002
[MathSciNet] [ps] [pdf] ©Elsevier

[182]

A. Roberts, A. Symvonis, D. R. Wood.
Lower bounds for one-to-one packet routing on trees using hot-potato algorithms
The Computer Journal 45.4:423–435, 2002
[ps] [pdf] ©British Computer Society

[183]

D. R. Wood.
On vertex-magic and edge-magic total injections
Australasian J. Combinatorics 26:49–63, 2002
[MathSciNet] [pdf] ©Combinatorial Mathematics Society of Australasia

[184]

D. R. Wood.
An algorithm for finding a maximum clique in a graph
Operations Research Letters 21.5:211–217, 1997
[MathSciNet] [ps] [pdf] ©Elsevier

__________________________________________________________________

Publications in Edited Books

[185]

M. Distel, D. R. Wood.
Tree-partitions with bounded degree trees
In 2021–22 MATRIX Annals, accepted 9 May 2023, Springer
©

[186]

R. Campbell, K. Clinch, M. Distel, J.P. Gollin, K. Hendrey, R. Hickingbotham, T. Huynh, F. Illingworth, Y. Tamitegama, J. Tan, D. R. Wood.
Product structure of graph classes with bounded treewidth
In 2021–22 MATRIX Annals, accepted 3 May 2023, Springer
©

[187]

R. Hickingbotham, F. Illingworth, B. Mohar, D. R. Wood.
Treewidth, circle graphs and circular drawings
In 2021–22 MATRIX Annals, accepted 23 February 2023, Springer
©

[188]

T. Huynh, B. Reed, L. Yepremyan, D. R. Wood.
Notes on tree- and path-chromatic number
In 2019–20 MATRIX Annals, 489–498, Springer, 2021
[publication] [pdf] ©

[189]

Z. Dvořák, T. Huynh, G. Joret, C.-H. Liu, D. R. Wood.
Notes on graph product structure theory
In 2019–20 MATRIX Annals, 513–533, Springer, 2021
[publication] [pdf] ©

[190]

D. R. Wood.
Three-dimensional graph drawing
In Encyclopedia of Algorithms (2nd edition), 2231–2236, Springer, 2016
[publication] [pdf] ©

[191]

G. Aloupis, B. Ballinger, S. Collette, S. Langerman, A. Pór, D. R. Wood.
Blocking coloured point sets
Thirty Essays on Geometric Graph Theory (János Pach, ed.), 31–48, Springer, 2012
[arXiv] [publication] [pdf] ©Springer

[192]

C. Hernando, M. Mora, P. J. Slater, D. R. Wood.
Fault-tolerant metric dimension of graphs
Convexity in Discrete Structures (M. Changat, S. Klavzar, H. M. Mulder and A. Vijayakumar, eds.),
Lecture Notes Series in Math. 5:81–85, Ramanujan Mathematical Society, 2008
[MathSciNet] [pdf] ©

[193]

V. Dujmović, D. R. Wood.
Three-dimensional grid drawings with sub-quadratic volume
Towards a Theory of Geometric Graphs (János Pach, ed.),
Contemporary Mathematics 342:55–66, American Mathematical Society, 2004
[MathSciNet] [ps] [pdf] ©AMS

__________________________________________________________________

Refereed Conference Publications

[194]

V. Dujmović, R. Hickingbotham, J. Hodor, G. Joret, H. La, P. Micek, P. Morin, C. Rambaud, D. R. Wood.
The grid-minor theorem revisited
Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA ’24) ,
SIAM, 2024
[publication] [arXiv] ©

[195]

V. Dujmović, L. Esperet, P. Morin, D. R. Wood.
Proof of the clustered Hadwiger conjecture
Proc. 64th IEEE Symposium on Foundations of Computer Science (FOCS ’23),
1921–1930, 2023
[publication] [arXiv] ©

[196]

M. Distel, R. Hickingbotham, M. T. Seweryn, D. R. Wood.
Powers of planar graphs, product structure, and blocking partitions
Proc. European Conference on Combinatorics, Graph Theory and Applications (Eurocomb ’23),
355–361, 2023
[publication] ©

[197]

Y. Gu, Y. Jiang, X. Zhu, D. R. Wood.
Refined list version of Hadwiger’s conjecture
Proc. European Conference on Combinatorics, Graph Theory and Applications (Eurocomb ’23),
511–517, 2023
[publication] [arXiv] ©

[198]

V. Dujmović, G. Joret, P. Micek, P. Morin, T. Ueckerdt, D. R. Wood.
Planar graphs have bounded queue-number
Proc. 60th Annual Symposium on Foundations of Computer Science (FOCS ’19),
IEEE, 2019
[arXiv] [pdf] ©

[199]

M. J. Bannister, W. E. Devanny, V. Dujmović, D. Eppstein, D. R. Wood.
Track layout is hard
Proc. 24th International Symp. on Graph Drawing and Network Visualization (GD ’16),
Lecture Notes in Computer Science 9801:499–510, Springer, 2016
[arXiv] [publication] [pdf] ©

[200]

V. Dujmović, D. Eppstein, D. R. Wood.
Genus, treewidth, and local crossing number
Proc. 23rd International Symp. on Graph Drawing and Network Visualization (GD ’15),
Lecture Notes in Computer Science 9411:87–98, Springer, 2015
[arXiv] [pdf] ©Springer

[201]

F. Frati, M. Kaufmann, J. Pach, C. D. Tóth, D. R. Wood.
On the upward planarity of mixed plane graphs
Proc. 21st International Symp. on Graph Drawing (GD ’13),
Lecture Notes in Computer Science 8242:1–12, Springer, 2013
[publication] [pdf] ©Springer

[202]

V. Dujmović, P. Morin, D. R. Wood.
Layered separators for queue layouts, 3D graph drawing and nonrepetitive coloring
Proc. 54th Annual Symposium on Foundations of Computer Science (FOCS ’13),
pp. 280–289, IEEE, 2013
[publication] [pdf] ©IEEE

[203]

R. Fabila-Monroy, D. R. Wood.
The chromatic number of the convex segment disjointness graph
Proc. Hurtado Festschrift, XIV Spanish Meeting on Computational Geometry (EGC 2011),
Lecture Notes in Computer Science 7579:79–84, Springer, 2012
[publication] [pdf] ©Springer

[204]

K. Kawarabayashi, D. R. Wood.
Cliques in odd-minor-free graphs
Proc. Computing: the Australasian Theory Symposium (CATS ’12),
2012
[arXiv] [pdf] ©

[205]

G. Aloupis, B. Ballinger, S. Collette, S. Langerman, A. Pór, D. R. Wood.
Blocking coloured point sets
Proc. 26th European Workshop on Computational Geometry (EuroCG ’10),
2010
(See [191] for the full paper.), D. R. Wood[pdf] ©

[206]

Z. Abel, B. Ballinger, P. Bose, S. Collette, V. Dujmović, F. Hurtado, S. D. Kominers, S. Langerman, A. Pór, D. R. Wood.
Every large point set contains many collinear points or an empty pentagon
Proc. 21st Canadian Conf. on Computational Geometry (CCCG ’09),
pp. 99–102, 2009
(See [121] for the full paper.) ©

[207]

G. Fijavž, D. R. Wood.
Minimum degree and graph minors
Proc. Topological & Geometric Graph Theory (TGGT ’08),
Electronic Notes in Discrete Mathematics 31:79–83, 2008
[pdf] ©

[208]

O. Aichholzer, S. Bereg, A. Dumitrescu, A. García, C. Huemer, F. Hurtado, M. Kano, A. Márquez, D. Rappaport, S. Smorodinsky, D. Souvaine, J. Urrutia, D. R. Wood.
Compatible geometric matchings
Proc. Topological & Geometric Graph Theory (TGGT ’08),
Electronic Notes in Discrete Mathematics 31:201–206, 2008
(See [133] for the full paper.) [publication] ©

[209]

P. Bose, V. Dujmović, F. Hurtado, S. Langerman, P. Morin, D. R. Wood.
A polynomial bound for untangling geometric planar graphs
Proc. Topological & Geometric Graph Theory (TGGT ’08),
Electronic Notes in Discrete Mathematics 31:213–218, 2008
(See [131] for the full paper.) [pdf] ©

[210]

O. Aichholzer, S. Cabello, R. Fabila-Monroy, D. Flores-Peñaloza, T. Hackl, C. Huemer, F. Hurtado, D. R. Wood.
Edge-removal and non-crossing configurations in geometric graphs
Proc. 24th European Workshop on Computational Geometry (EWCG ’08),
2008
©

[211]

R. Fabila-Monroy, D. Flores-Peñaloza, C. Huemer, F. Hurtado, J. Urrutia, D. R. Wood.
On the chromatic numbers of some flip graphs
Proc. 23rd European Workshop on Computational Geometry (EWCG ’07),
Graz University of Technology, Austria, 2007
©

[212]

V. Dujmović, B. Mohar, K. Kawarabayashi, D. R. Wood.
Improved upper bounds on the crossing number
Proc. 24th ACM Annual Symp. on Computational Geometry (SoCG ’08),
pp. 375–384, 2008
[MathSciNet] [pdf] ©ACM

[213]

P. Bose, V. Dujmović, F. Hurtado, S. Langerman, P. Morin, D. R. Wood.
A polynomial bound for untangling geometric planar graphs
Proc. International Conference on Topological and Geometric Graph Theory,
Electronic Notes in Discrete Mathematics 31:213–218, 2008
(See [131] for the full paper.)

[214]

C. Hernando, M. Mora, I. M. Pelayo, C. Seara, D. R. Wood.
Extremal graph theory for metric dimension and diameter
Proc. European Conf. on Combinatorics, Graph Theory and Applications (EuroComb ’07),
Electronic Notes in Discrete Mathematics 29:339–343, 2007
(See [128] for the full paper.)

[215]

P. Bose, V. Dujmović, D. Krizanc, S. Langerman, P. Morin, S. Wuhrer, D. R. Wood.
A characterization of the degree sequences of 2-trees
Proc. Workshop on Analytic Algorithmics and Combinatorics (ANALCO ’07),
SIAM, pp. 232–241, 2007
(See [139] for the full paper.)

[216]

D. R. Wood, J. A. Telle.
Planar decompositions and the crossing number of graphs with an excluded minor
Proc. 14th International Symp. on Graph Drawing (GD ’06),
Lecture Notes in Computer Science 4372:150–161, Springer, 2007
(See [148] for the full paper.) [publication] [pdf] ©Springer

[217]

P. Bose, J. Czyzowicz, Z. Gao, P. Morin, D. R. Wood.
Simultaneous diagonal flips in plane triangulations
Proc. 17th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA ’06),
pp. 212–221, ACM-SIAM, 2006
(See [152] for the full paper.) [pdf] ©SIAM

[218]

A. Pór, D. R. Wood.
Colourings of the cartesian product of graphs and multiplicative Sidon sets
Proc. 6th Czech-Slovak International Symp. on Combinatorics, Graph Theory, Algorithms and Applications (CS ’06),
Charles University, Prague, Czech Republic, 2006
[MathSciNet]

[219]

J. Cáceres, C. Hernando, M. Mora, I. M. Pelayo, M. L. Puertas, C. Seara, D. R. Wood.
On the metric dimension of cartesian products of graphs
Proc. V Jornadas de Matemática Discreta y Algorítmica (V JMDA ’06):181–188,
Universidad de Valladolid, Spain, 2006

[220]

C. Hernando, M. Mora, I. M. Pelayo, M. L. Puertas, C. Seara, D. R. Wood.
Grafos de orden máximo y jados mínimo con diámetro y dimensión métrica
Proc. V Jornadas de Matemática Discreta y Algorítmica (V JMDA ’06):295–302,
Universidad de Valladolid, Spain, 2006

[221]

V. Dujmović, D. R. Wood.
Graph treewidth and geometric thickness parameters
Proc. 13th International Symp. on Graph Drawing (GD ’05),
Lecture Notes in Computer Science 3843:129–140, Springer, 2006
(See [150] for the full paper.) [MathSciNet] [pdf] ©Springer

[222]

E. D. Demaine, F. Gomez-Martin, H. Meijer, D. Rappaport, P. Taslakian, G. T. Toussaint, T. Winograd, D. R. Wood.
The distance geometry of deep rhythms and scales
Proc. 17th Canadian Conf. on Computational Geometry (CCCG ’05),
pp. 163–166, 2005
[pdf]

[223]

B. Reed, D. R. Wood.
Fast separation in a graph with an excluded minor
Proc. European Conf. on Combinatorics, Graph Theory and Applications (EuroComb ’05),
Discrete Math. & Theoret. Comput. Sci.AE:45–50, 2005
[ps] [pdf] ©

[224]

P. Bose, V. Dujmović, D. R. Wood.
Induced subgraphs of bounded degree and bounded treewidth
Proc. 31st International Workshop on Graph Theoretic Concepts in Computer Science (WG ’05),
Lecture Notes in Computer Science 3787:175–186, Springer, 2005
(See [157] for the full paper.) [pdf] ©Springer

[225]

J. Kára, J. Kratochvil, D. R. Wood.
On the complexity of the balanced vertex ordering problem
Proc. 11th International Computing and Combinatorics Conference (COCOON ’05),
Lecture Notes in Computer Science 3595:849–858, Springer, 2005
(See [143] for the full paper.) [MathSciNet] [pdf] ©Springer

[226]

P. Morin, D. R. Wood.
Three-dimensional 1-bend graph drawings
Proc. 16th Canadian Conf. on Computational Geometry (CCCG ’04),
pp. 40–43, 2004
[ps] [pdf]

[227]

V. Dujmović, D. R. Wood.
Layouts of graph subdivisions
Proc. 12th International Symp. on Graph Drawing (GD ’04),
Lecture Notes in Computer Science 3383:133–143, Springer, 2004
[pdf] ©Springer

[228]

P. Bose, F. Hurtado, E. Rivera-Campo, D. R. Wood.
Partitions of complete geometric graphs into plane trees
Proc. 12th International Symp. on Graph Drawing (GD ’04),
Lecture Notes in Computer Science 3383:71–81, Springer, 2004
(See [158] for the full paper.) [pdf] ©Springer

[229]

A. Pór, D. R. Wood.
No-three-in-line-in-3D
Proc. 12th International Symp. on Graph Drawing (GD ’04),
Lecture Notes in Computer Science 3383:395–402, Springer, 2004
(These results have been improved in [151].) [pdf] ©Springer

[230]

V. Dujmović, M. Suderman, D. R. Wood.
Really straight graph drawings
Proc. 12th International Symp. on Graph Drawing (GD ’04),
Lecture Notes in Computer Science 3383:122–132, Springer, 2004
(See [146] and [145] for the full papers. [pdf] ©Springer

[231]

V. Dujmović, D. R. Wood.
Three-dimensional grid drawings with sub-quadratic volume
Proc. 11th International Symp. on Graph Drawing (GD ’03),
Lecture Notes in Computer Science 2912:190–201, Springer, 2004
(Also appears in [193].) [ps] [pdf] ©Springer

[232]

P. Bose, J. Czyzowicz, P. Morin, D. R. Wood.
The maximum number of edges in a three-dimensional grid-drawing
Proc. 19th European Workshop on Computational Geometry (CG ’03),
University of Bonn, Germany, 2003
(Final version is in [171].) [ps] [pdf]

[233]

V. Dujmović, D. R. Wood.
Tree-partitions of \(k\)-trees with applications in graph layout
Proc. 29th Workshop on Graph Theoretic Concepts in Computer Science (WG ’03),
Lecture Notes in Computer Science 2880:205–217, Springer 2003
(See ?? for the full paper.) [MathSciNet] [ps] [pdf] ©Springer

[234]

P. Bose, M. Smid, D. R. Wood.
Light edges in degree-constrained graphs
Proc. 14th Canadian Conf. on Computational Geometry (CCCG ’02),
pp. 109–112, 2002
(Final version is in [176].) [ps]

[235]

H. Brönnimann, M. Glisse, D. R. Wood.
Cost-optimal quadtrees for ray tracing
Proc. 14th Canadian Conf. on Computational Geometry (CCCG ’02),
pp. 109–112, 2002
[ps]

[236]

D. R. Wood.
Queue layouts, tree-width, and three-dimensional graph drawing
Proc. 22nd Foundations of Software Technology and Theoretical Computer Science (FST TCS ’02),
Lecture Notes in Computer Science 2556:348–359, Springer 2002
(See ?? for the full paper.) [MathSciNet] [ps] [pdf] ©Springer

[237]

V. Dujmović, P. Morin, D. R. Wood.
Path-width and three-dimensional straight-line grid drawing of graphs
Proc. 10th International Symp. on Graph Drawing (GD ’02),
Lecture Notes in Computer Science 2528:42–53, Springer, 2002
(See ?? for the full paper.) [MathSciNet] [ps] [pdf] ©Springer

[238]

M. Houle, A. Symvonis, D. R. Wood.
Dimension-exchange algorithms for load balancing on trees
Proc. 9th International Colloquium on Structural Information and Communication Complexity (SIROCCO ’02),
pp. 181–196, Carleton Scientific, 2002
(See [175] for the full paper.) [ps] ©Carleton Scientific

[239]

D. R. Wood.
Bounded-degree book embeddings and three-dimensional orthogonal graph drawing
Proc. 9th International Symp. on Graph Drawing (GD ’01),
Lecture Notes in Computer Science 2265:312–327, Springer, 2002
[MathSciNet] [ps] [pdf] ©Springer

[240]

V. Dujmović, M. Fellows, M. Hallett, M. Kitching, G. Liotta, C. McCartin, N. Nishimura, P. Ragde, F. Rosamond, M. Suderman, S. Whitesides, D. R. Wood.
A fixed-parameter approach to two-layer planarization
Proc. 9th International Symp. on Graph Drawing (GD ’01),
Lecture Notes in Computer Science 2265:1–15, Springer, 2002
(See [156] for the full paper.) [MathSciNet] [ps] [pdf] ©Springer

[241]

T. Biedl, J. Johansen, T. Shermer, D. R. Wood.
Orthogonal drawings with few layers
Proc. 9th International Symp. on Graph Drawing (GD ’01),
Lecture Notes in Computer Science 2265:297–311, Springer, 2002
[MathSciNet] [ps] [pdf] ©Springer

[242]

V. Dujmović, M. Fellows, M. Hallett, M. Kitching, G. Liotta, C. McCartin, N. Nishimura, P. Ragde, F. Rosamond, M. Suderman, S. Whitesides, D. R. Wood.
On the parameterized complexity of layered graph drawing
Proc. 9th Annual European Symp. on Algorithms (ESA ’01),
Lecture Notes in Computer Science 2161:488–499, Springer, 2001
(See [136] for the full paper.) [MathSciNet] [ps] [pdf] ©Springer

[243]

D. R. Wood.
Geometric thickness in a grid of linear area
Proc. European Conf. on Combinatorics, Graph Theory and Applications (EuroCOMB ’01),
Universitat Autònoma de Barcelona, Spain, Electronic Notes in Discrete Mathematics 10, 2001
(Final version appears in [178].) [ps] ©Elsevier

[244]

D. R. Wood.
On pseudo vertex-magic and edge-magic total-labellings
Proc. 12th Australasian Workshop on Combinatorial Algorithms (AWOCA ’01),
pp. 180–198, Institut Teknologi Bandung, Indonesia, 2001
(See [183] for the final version. [ps]

[245]

D. R. Wood.
Lower bounds for the number of bends in three-dimensional orthogonal graph drawings
Proc. 8th International Symp. on Graph Drawing (GD ’00),
Lecture Notes in Computer Science 1984:259–271, Springer, 2001
(These results have been improved in [179].)

[246]

B. Y. S. Lynn, A. Symvonis, D. R. Wood.
Refinement of three-dimensional orthogonal graph drawings
Proc. 8th International Symp. on Graph Drawing (GD ’00),
Lecture Notes in Computer Science 1984:308–320, Springer, 2001
[ps] ©Springer

[247]

T. Biedl, T. Thiele, D. R. Wood.
Three-dimensional orthogonal graph drawing with optimal volume
Proc. 8th International Symp. on Graph Drawing (GD ’00),
Lecture Notes in Computer Science 1984:284–295, Springer, 2001
(See [159] for the full paper.) [ps] ©Springer

[248]

A. Roberts, A. Symvonis, D. R. Wood.
Lower bounds for hot-potato permutation routing on trees
Proc. 7th International Colloquium on Structural Information and Communication Complexity (SIROCCO ’00),
pp. 281–295, Carleton Scientific, 2000
(These results have been improved in [182].)

[249]

D. R. Wood.
Multi-dimensional orthogonal graph drawing with small boxes
Proc. 7th International Symp. on Graph Drawing (GD ’99),
Lecture Notes in Computer Science 1731:311–322, Springer, 1999
[MathSciNet] [Citeseer] [ps] [pdf] ©Springer

[250]

D. R. Wood.
A new algorithm and open problems in three-dimensional orthogonal graph drawing
Proc. 10th Australasian Workshop on Combinatorial Algorithms (AWOCA ’99),
pp. 157–167, Curtin University of Technology, Perth, 1999

[251]

D. R. Wood.
An algorithm for three-dimensional orthogonal graph drawing
Proc. 6th International Symp. on Graph Drawing (GD ’98),
Lecture Notes in Computer Science 1547:332–346, Springer, 1998
(These results have been improved in [180].) [MathSciNet] [ps] [pdf] ©Springer

[252]

D. R. Wood.
Towards a two-bends algorithm for three-dimensional orthogonal graph drawing
Proc. 8th Australasian Workshop on Combinatorial Algorithms (AWOCA ’97),
pp. 102–107, Queensland University of Technology, 1997

[253]

D. R. Wood.
On higher-dimensional orthogonal graph drawing
Proc. Computing: the Australasian Theory Symposium (CATS ’97),
pp. 3–8, Macquarie University, 1997

__________________________________________________________________

Unpublished Notes

[254]

R. Hickingbotham, D. R. Wood
Structural properties of bipartite subgraphs, 2021
[arXiv]

[255]

V. Dujmović, P. Morin, D. R. Wood
Queue layouts of graphs with bounded degree and bounded genus, 2019
[arXiv] [pdf] ©

[256]

D. R. Wood
Three dimensional graph drawing with fixed vertices and one bend per edge, 2016
[arXiv] [pdf] ©

[257]

D. R. Wood
A note on Hadwiger’s conjecture, 2013
[arXiv] [pdf] ©

[258]

D. R. Wood
Hypergraph colouring and degeneracy, 2013
[arXiv] [pdf] ©

[259]

D. R. Wood
Partitions and coverings of trees by bounded-degree subtrees, 2011
[arXiv] [pdf] ©

[260]

R. Fabila-Monroy, D. R. Wood
Decompositions of complete multipartite graphs into complete graphs, 2011
[arXiv] [pdf] ©

[261]

A. Pór, D. R. Wood
The big-line-big-clique conjecture is false for infinite point sets, 2010
[arXiv] [pdf] ©

[262]

D. R. Wood
Folding = Colouring, 2008
[arXiv] [pdf] ©

[263]

D. R. Wood
A simple proof of the Fáry-Wagner theorem, 2005
[arXiv] [ps] [pdf] ©

[264]

B. Baetz, D. R. Wood
Brooks’ vertex-colouring theorem in linear time, Technical Report TR-CS-AAG-2001-05, Basser Department of Computer Science, The University of Sydney, Australia, 2001
[arXiv] [ps] ©