Publications of David R. Wood (as of February 10, 2012)


Preprints


[1]
(with V. Dujmovic, F. Frati, G. Joret)
Nonrepetitive colourings of planar graphs with O(log n) colours, 2011.
[arXiv] [pdf]

[2]
(with V. Dujmovic, G. Joret)
Nonrepetitive colouring via entropy compression, 2011.
[arXiv] [pdf]

[3]
(with V. Dujmovic, G. Joret)
An improved bound for first-fit on posets without two long incomparable chains, 2011.
[arXiv] [pdf]

[4]
(with R. Fabila-Monroy)
Colouring the triangles determined by a point set, 2011.
[arXiv] [pdf]

[5]
On multiplicative Sidon sets, 2011.
[arXiv] [pdf]

[6]
(with M. Payne, A. Pór, P. Valtr)
On the connectivity of visibility graphs, 2011.
[arXiv] [pdf]

[7]
Treewidth of cartesian products of highly connected graphs, 2011.
[arXiv] [pdf]

[8]
(with G. Joret)
Complete graph minors and the graph minor structure theorem, 2011.
[arXiv] [pdf]

[9]
(with R. Fabila-Monroy)
Rooted -Minors, 2011.
[arXiv] [pdf]

[10]
Partitions and coverings of trees by bounded-degree subtrees, 2011.
[arXiv] [pdf]

[11]
(with F. Hurtado, G. Liotta)
Proximity drawings of high-degree trees, 2011.
[arXiv] [pdf]

[12]
(with S. Fiorini, G. Joret, D. O. Theis)
Small minors in dense graphs, 2010.
[arXiv] [pdf]


Journal Publications


[13]
(with G. Joret)
Nordhaus-Gaddum for treewidth,
European J. Combinatorics 33.4:488-490, 2012.
[arXiv] [publication] [pdf] © 

[14]
(with B. Reed)
Polynomial treewidth forces a large grid-like-minor,
European J. Combinatorics 33.3:374-379, 2012.
[arXiv] [publication] [pdf] © 

[15]
(with J. Nešetril, P. Ossona de Mendez)
Characterisations and examples of graph classes with bounded expansion,
European J. Combinatorics 33.3:350-373, 2012.
[arXiv] [publication] [pdf] © Elsevier

[16]
(with J. Barát, G. Joret)
Disproof of the List Hadwiger Conjecture,
Electronic J. Combinatorics 18:P232, 2011.
[arXiv] [publication] [pdf] © 

[17]
(with R. Fabila-Monroy, D. Flores-Peñaloza, C. Huemer, F. Hurtado, J. Urrutia)
Token graphs,
Graphs and Combinatorics, 2011.
[arXiv] [publication] [pdf] © Springer

[18]
(with V. Dujmovic)
On the book thickness of $k$-trees,
Discrete Maths. & Theoretical Computer Science 13.3:39-44, 2011.
[arXiv] [publication] [pdf] © DMTCS

[19]
Clique minors in cartesian products of graphs,
New York J. Mathematics 17:627-682, 2011.
[arXiv] [publication] [pdf] © 

[20]
On the number of maximal independent sets in a graph,
Discrete Maths. & Theoretical Computer Science 13.3:17-20, 2011.
[MathSciNet] [arXiv] [publication] [pdf] © DMTCS

[21]
Colouring the square of the cartesian product of trees,
Discrete Maths. & Theoretical Computer Science 13.2:109-112, 2011.
[MathSciNet] [arXiv] [publication] [pdf] © DMTCS

[22]
(with V. Dujmovic, G. Fijavz, G. Joret, T. Sulanke)
On the maximum number of cliques in a graph embedded in a surface,
European J. Combinatorics 32.8:1244-1252, 2011.
[arXiv] [publication] [pdf] © 

[23]
(with Z. Abel, B. Ballinger, P. Bose, S. Collette, V. Dujmovic, F. Hurtado, S. D. Kominers, S. Langerman, A. Pór)
Every large point set contains many collinear points or an empty pentagon,
Graphs and Combinatorics 27.1:47-60, 2011.
[MathSciNet] [arXiv] [publication] [pdf] © Springer

[24]
(with S. Linusson)
Thomassen's choosability argument revisited,
SIAM J. Discrete Mathematics 24.4:1632-1637, 2010.
[MathSciNet] [arXiv] [publication] [pdf] © SIAM

[25]
(with G. Fijavz)
Graph minors and minimum degree,
Electronic J. Combinatorics R151, 2010.
[MathSciNet] [arXiv] [publication] [pdf] © 

[26]
Contractibility and the Hadwiger Conjecture,
European J. Combinatorics 31.8:2102-2109, 2010.
[MathSciNet] [arXiv] [publication] [pdf] © 

[27]
(with A. Pór)
On visibility and blockers,
J. Computational Geometry 1:29-40, 2010.
[MathSciNet] [arXiv] [publication] [pdf] © 

[28]
(with G. Joret)
Irreducible triangulations are small,
J. Combinatorial Theory Series B 100.5:446-455, 2010.
[MathSciNet] [arXiv] [publication] [pdf] © 

[29]
(with O. Aichholzer, S. Cabello, R. Fabila-Monroy, D. Flores-Peñaloza, T. Hackl, C. Huemer, F. Hurtado)
Edge-removal and non-crossing configurations in geometric graphs,
Discrete Maths. & Theoretical Computer Science 12.1:75-86, 2010.
[MathSciNet] [publication] [pdf] © DMTCS

[30]
(with C. Hernando, M. Mora, I. M. Pelayo, C. Seara)
Extremal graph theory for metric dimension and diameter,
Electronic J. Combinatorics 17.1:R30, 2010.
[MathSciNet] [arXiv] [publication] [pdf] © 

[31]
(with A. Pór)
Colourings of the cartesian product of graphs and multiplicative Sidon sets,
Combinatorica 29.4:449-466, 2009.
[MathSciNet] [arXiv] [publication] [pdf] © Springer

[32]
(with B. Reed)
A linear time algorithm to find a separator in a graph excluding a minor,
ACM Transactions on Algorithms 5.4:39, 2009.
[MathSciNet] [publication] [pdf] © ACM

[33]
(with P. Bose, V. Dujmovic, F. Hurtado, S. Langerman, P. Morin)
A polynomial bound for untangling geometric planar graphs,
Discrete & Computational Geometry 42.4:570-585, 2009.
[MathSciNet] [arXiv] [publication] [pdf] © Springer

[34]
(with R. Fabila-Monroy, D. Flores-Peñaloza, C. Huemer, F. Hurtado, J. Urrutia)
On the chromatic number of some flip graphs,
Discrete Maths. & Theoretical Computer Science 11.2:47-56, 2009.
[MathSciNet] [publication] © DMTCS

[35]
(with O. Aichholzer, S. Bereg, A. Dumitrescu, A. García, C. Huemer, F. Hurtado, M. Kano, A. Márquez, S. Smorodinsky, D. Souvaine, J. Urrutia)
Compatible geometric matchings,
Computational Geometry 42.6-7:617-626, 2009.
[MathSciNet] [arXiv] [publication] [pdf] © Elsevier

[36]
On tree-partition-width,
European J. Combinatorics 30:1245-1253, 2009.
[MathSciNet] [arXiv] [publication] [pdf] © Elsevier

[37]
(with E. D. Demaine, F. Gomez-Martin, H. Meijer, D. Rappaport, P. Taslakian, G. T. Toussaint, T. Winograd)
The distance geometry of music,
Computational Geometry 42.5:429-454, 2009.
[MathSciNet] [publication] [pdf] © Elsevier

[38]
(with V. Dujmovic, M. Fellows, M. Kitching, G. Liotta, C. McCartin, N. Nishimura, P. Ragde, F. Rosamond, and S. Whitesides)
On the parameterized complexity of layered graph drawing,
Algorithmica 52.2:267-292, 2008.
[MathSciNet] [publication] [pdf] © Springer

[39]
(with P. Carmi, V. Dujmovic, P. Morin)
Distinct distances in graph drawings,
Electronic J. Combinatorics 15:R107, 2008.
[MathSciNet] [publication] [pdf] © 

[40]
(with J. Barát)
Notes on nonrepetitive graph colouring,
Electronic J. Combinatorics 15:R99, 2008.
[MathSciNet] [publication] [pdf] © 

[41]
(with P. Bose, V. Dujmovic, D. Krizanc, S. Langerman, P. Morin, S. Wuhrer)
A characterization of the degree sequences of 2-trees,
J. Graph Theory, 58.3:191-209, 2008.
[MathSciNet] [arXiv] [publication] [pdf] © Wiley

[42]
Bounded-degree graphs have arbitrarily large queue-number,
Discrete Maths. & Theoretical Computer Science 10.1:27-34, 2008.
[MathSciNet] [arXiv] [publication] [pdf] © DMTCS

[43]
(with D. Bokal and G. Fijavz)
The minor crossing number of graphs with an excluded minor,
Electronic J. Combinatorics 15:R4, 2008.
[MathSciNet] [arXiv] [publication] [pdf] © 

[44]
On the oriented chromatic number of dense graphs,
Contributions to Discrete Mathematics 2.2:145-152, 2007.
[MathSciNet] [arXiv] [publication] [pdf] © University of Calgary

[45]
(with J. Kára and J. Kratochvil)
On the complexity of the balanced vertex ordering problem,
Discrete Maths. & Theoretical Computer Science 9.1:193-202, 2007.
[MathSciNet] [publication] [pdf] © DMTCS

[46]
Independent sets in graphs with an excluded clique minor,
Discrete Maths. & Theoretical Computer Science 9.1:171-177, 2007.
[MathSciNet] [arXiv] [publication] [pdf] © DMTCS

[47]
(with V. Dujmovic and M. Suderman)
Graph drawings with few slopes,
Computational Geometry 38:181-193, 2007.
[MathSciNet] [arXiv] [publication] [pdf] © Elsevier

[48]
(with V. Dujmovic, D. Eppstein and M. Suderman)
Drawings of planar graphs with few slopes and segments,
Computational Geometry 38:194-212, 2007.
[MathSciNet] [arXiv] [publication] [pdf] © Elsevier

[49]
On the maximum number of cliques in a graph,
Graphs and Combinatorics 23.3:337-352, 2007.
[MathSciNet] [arXiv] [publication] [pdf] © Springer

[50]
(with J. A. Telle)
Planar decompositions and the crossing number of graphs with an excluded minor,
New York J. Mathematics 13:117-146, 2007.
[MathSciNet] [arXiv] [publication] [pdf] © 

[51]
(with J. Cáceres, C. Hernando, M. Mora, I. M. Pelayo, M. L. Puertas, C. Seara)
On the metric dimension of cartesian products of graphs,
SIAM J. Discrete Mathematics 21.2:423-441, 2007.
[MathSciNet] [arXiv] [publication] [pdf] © SIAM

[52]
(with V. Dujmovic)
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] [publication] [pdf] © Springer

[53]
(with A. Pór)
No-three-in-line-in-3D,
Algorithmica 47.4:481-488, 2007.
[MathSciNet] [publication] [pdf] © Springer

[54]
(with P. Bose, J. Czyzowicz, Z. Gao, and P. Morin)
Simultaneous diagonal flips in plane triangulations,
J. Graph Theory 54.4:307-330, 2007.
[arXiv] [MathSciNet] [publication] [pdf] © Wiley

[55]
Vertex partitions of chordal graphs,
J. Graph Theory 53.2:167-172, 2006.
[arXiv] [MathSciNet] [publication] [pdf] © Wiley

[56]
(with V. Dujmovic)
Upward three-dimensional grid drawings of graphs,
Order 23:1-20, 2006.
[MathSciNet] [publication] [pdf] © Springer

[57]
Drawing a graph in a hypercube,
Electronic J. Combinatorics 13.1:R73, 2006.
[MathSciNet] [publication] [ps][pdf] © 

[58]
(with V. Dujmovic, M. Fellows, M. Hallett, M. Kitching, G. Liotta, C. McCartin, N. Nishimura, P. Ragde, F. Rosamond, M. Suderman, and S. Whitesides)
A fixed-parameter approach to two-layer planarization,
Algorithmica 45.2:159-182, 2006.
[MathSciNet] [publication] [pdf] © Springer

[59]
(with P. Bose and V. Dujmovic)
Induced subgraphs of bounded degree and bounded treewidth,
Contributions to Discrete Mathematics 1.1:88-105, 2006.
[arXiv] [MathSciNet] [publication] [pdf] © 

[60]
(with P. Bose, F. Hurtado, and E. Rivera-Campo)
Partitions of complete geometric graphs into plane trees,
Computational Geometry 34.2:116-125, 2006.
[MathSciNet] [publication] [pdf] © Elsevier

[61]
(with T. Biedl and T. Thiele)
Three-dimensional orthogonal graph drawing with optimal volume,
Algorithmica 44.3:233-255, 2006.
[MathSciNet] [publication] [pdf] © Springer

[62]
(with J. Barát and J. Matoušek)
Bounded-degree graphs have arbitrarily large geometric thickness,
Electronic J. Combinatorics 13.1:R3, 2006.
[MathSciNet] [publication] [ps][pdf] © 

[63]
Characterisations of intersection graphs by vertex orderings,
Australasian J. Combinatorics 34:261-268, 2006.
[MathSciNet] [publication] [pdf] © Combinatorial Mathematics Society of Australasia

[64]
Queue layouts of graph products and powers,
Discrete Maths. & Theoretical Computer Science 7:255-268, 2005.
[MathSciNet] [publication] [ps][pdf] © DMTCS

[65]
(with V. Dujmovic)
Stacks, queues and tracks: Layouts of graph subdivisions,
Discrete Maths. & Theoretical Computer Science 7:155-202, 2005.
[MathSciNet] [publication] [ps][pdf] © DMTCS

[66]
(with J. Kára and A. Pór)
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] [publication] [pdf] © Springer

[67]
Acyclic, star and oriented colourings of graph subdivisions,
Discrete Maths. & Theoretical Computer Science 7.1:37-50, 2005.
[MathSciNet] [publication] [ps][pdf] © DMTCS

[68]
(with V. Dujmovic and P. Morin)
Layout of graphs with bounded tree-width,
SIAM J. Computing 34.3:553-579, 2005.
[MathSciNet] [publication] [ps][pdf] © SIAM

[69]
(with T. Biedl, T. Chan, Y. Ganjali and M. Hajiaghayi)
Balanced vertex-orderings of graphs,
Discrete Applied Mathematics 148.1:27-48, 2005.
[MathSciNet] [pdf] © Elsevier

[70]
Grid drawings of $k$-colourable graphs,
Computational Geometry 30.1:25-28, 2005.
[MathSciNet] [publication] [pdf] © Elsevier

[71]
(with P. Morin)
Three-dimensional 1-bend graph drawings,
J. Graph Algorithms & Applications 8.3:357-366, 2004.
[MathSciNet] [ps][pdf] © JGAA

[72]
(with V. Dujmovic and A. Pór)
Track layouts of graphs,
Discrete Maths. & Theoretical Computer Science 6.2:497-522, 2004.
[MathSciNet] [publication] [ps][pdf] © DMTCS

[73]
(with P. Bose, J. Czyzowicz and P. Morin)
The maximum number of edges in a three-dimensional grid-drawing,
J. Graph Algorithms & Applications 8.1:21-26, 2004.
[MathSciNet] [pdf] © JGAA

[74]
(with V. Dujmovic)
On linear layouts of graphs,
Discrete Maths. & Theoretical Computer Science 6.2:339-358, 2004.
(solves an open problem of Dan Archdeacon)
[MathSciNet] [publication] [ps][pdf] © DMTCS

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

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

[77]
(with M. Houle and A. Symvonis)
Dimension-exchange algorithms for token distribution on tree-connected architectures,
J. Parallel and Distributed Computing 64.5:591-605, 2004.
[publication] [pdf] © Elsevier

[78]
(with P. Bose and M. Smid)
Light edges in degree-constrained graphs,
Discrete Mathematics 282.1-3:35-41, 2004.
[MathSciNet] [publication] [pdf] © Elsevier

[79]
Bounded degree acyclic decompositions of digraphs,
J. Combinatorial Theory Series B 90:309-313, 2004.
[MathSciNet] [publication] [pdf] © Elsevier

[80]
Geometric thickness in a grid,
Discrete Mathematics 273.1-3:221-234, 2003.
[MathSciNet] [publication] [pdf] © Elsevier

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

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

[83]
Degree constrained book embeddings,
J. Algorithms 45.2:144-154, 2002.
[MathSciNet] [publication] [ps][pdf] © Elsevier

[84]
(with A. Roberts and A. Symvonis)
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

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

[86]
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


[87]
(with G. Aloupis, B. Ballinger, S. Collette, S. Langerman, A. Pór)
Blocking coloured point sets,
In Thirty Essays on Geometric Graph Theory (János Pach, ed.), Springer, 2012.
[arXiv] [pdf]

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

[89]
(with C. Hernando, M. Mora, P. J. Slater)
Fault-tolerant metric dimension of graphs,
In 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]


Refereed Conference Publications


[90]
(with K. Kawarabayashi)
Cliques in odd-minor-free graphs.
Proc. of Computing: the Australasian Theory Symposium (CATS '12),
2012.
[arXiv] [pdf]

[91]
(with V. Dujmovic, B. Mohar, K. Kawarabayashi)
Improved upper bounds on the crossing number.
Proc. of 24th ACM Annual Symp. on Computational Geometry (SoCG '08),
pp. 375-384, 2008.
[MathSciNet] [pdf] © ACM

[92]
(with C. Hernando, M. Mora, I. M. Pelayo, C. Seara)
Extremal graph theory for metric dimension and diameter.
Proc. of European Conf. on Combinatorics, Graph Theory and Applications (EuroComb '07),
Electronic Notes in Discrete Mathematics 29:339-343, 2007.
(See [27] for the full paper.)

[93]
(with P. Bose, V. Dujmovic, D. Krizanc, S. Langerman, P. Morin, S. Wuhrer)
A characterization of the degree sequences of 2-trees.
Proc. of Workshop on Analytic Algorithmics and Combinatorics (ANALCO '07),
SIAM, pp. 232-241, 2007.
(See [38] for the full paper.)

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

[95]
(with P. Bose, J. Czyzowicz, Z. Gao, and P. Morin)
Simultaneous diagonal flips in plane triangulations.
Proc. of 17th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA '06),
pp. 212-221, ACM-SIAM, 2006.
(See [51] for the full paper.)
[pdf] © SIAM

[96]
(with V. Dujmovic)
Graph treewidth and geometric thickness parameters.
Proc. of 13th International Symp. on Graph Drawing (GD '05),
Lecture Notes in Computer Science 3843:129-140, Springer, 2006.
(See [49] for the full paper.)
[MathSciNet] [pdf] © Springer

[97]
(with B. Reed)
Fast separation in a graph with an excluded minor.
Proc. of European Conf. on Combinatorics, Graph Theory and Applications (EuroComb '05),
Discrete Mathematics & Theoretical Computer ScienceAE:45-50, 2005.
[ps][pdf]

[98]
(with P. Bose and V. Dujmovic)
Induced subgraphs of bounded degree and bounded treewidth.
Proc. of 31st International Workshop on Graph Theoretic Concepts in Computer Science (WG '05),
Lecture Notes in Computer Science 3787:175-186, Springer, 2005.
(See [56] for the full paper.)
[pdf] © Springer

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

[100]
(with V. Dujmovic)
Layouts of graph subdivisions.
Proc. of 12th International Symp. on Graph Drawing (GD '04),
Lecture Notes in Computer Science 3383:133-143, Springer, 2004.
[pdf] © Springer

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

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

[103]
(with V. Dujmovic and M. Suderman)
Really straight graph drawings.
Proc. of 12th International Symp. on Graph Drawing (GD '04),
Lecture Notes in Computer Science 3383:122-132, Springer, 2004.
(See [45] and [44] for the full papers.)
[pdf] © Springer

[104]
(with V. Dujmovic)
Three-dimensional grid drawings with sub-quadratic volume.
Proc. of 11th International Symp. on Graph Drawing (GD '03),
Lecture Notes in Computer Science 2912:190-201, Springer, 2004.
(Also appears in [85].)
[ps][pdf] © Springer

[105]
(with V. Dujmovic)
Tree-partitions of $k$-trees with applications in graph layout.
Proc. of 29th Workshop on Graph Theoretic Concepts in Computer Science (WG '03),
Lecture Notes in Computer Science 2880:205-217, Springer 2003.
(See [65] for the full paper.)
[MathSciNet] [ps][pdf] © Springer

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

[107]
(with V. Dujmovic and P. Morin)
Path-width and three-dimensional straight-line grid drawing of graphs.
Proc. of 10th International Symp. on Graph Drawing (GD '02),
Lecture Notes in Computer Science 2528:42-53, Springer, 2002.
(See [65] for the full paper.)
[MathSciNet] [ps][pdf] © Springer

[108]
(with M. Houle and A. Symvonis)
Dimension-exchange algorithms for load balancing on trees.
Proc. of 9th International Colloquium on Structural Information and Communication Complexity (SIROCCO '02),
pp. 181-196, Carleton Scientific, 2002.
(See [74] for the full paper.)
[ps] © Carleton Scientific

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

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

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

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

[113]
Geometric thickness in a grid of linear area.
Proc. of 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 [77].)
[ps] © Elsevier

[114]
On pseudo vertex-magic and edge-magic total-labellings.
Proc. of 12th Australasian Workshop on Combinatorial Algorithms (AWOCA '01),
pp. 180-198, Institut Teknologi Bandung, Indonesia, 2001.
(See [82] for the final version.)
[ps]

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

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

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

[118]
(with A. Roberts and A. Symvonis)
Lower bounds for hot-potato permutation routing on trees.
Proc. of 7th International Colloquium on Structural Information and Communication Complexity (SIROCCO '00),
pp. 281-295, Carleton Scientific, 2000.
(These results have been improved in [81].)

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

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

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

[122]
Towards a two-bends algorithm for three-dimensional orthogonal graph drawing.
Proc. of 8th Australasian Workshop on Combinatorial Algorithms (AWOCA '97),
pp. 102-107, Queensland University of Technology, 1997.

[123]
On higher-dimensional orthogonal graph drawing.
Proc. of Computing: the Australasian Theory Symposium (CATS '97),
pp. 3-8, Macquarie University, 1997.


Unpublished Notes


[124]
(with R. Fabila-Monroy)
Decompositions of complete multipartite graphs into complete graphs, 2011.
[arXiv] [pdf]

[125]
(with A. Pór)
The big-line-big-clique conjecture is false for infinite point sets, 2010.
[arXiv] [pdf]

[126]
Folding = Colouring, 2008.
[arXiv] [pdf]

[127]
A simple proof of the Fáry-Wagner theorem, 2005.
[arXiv] [ps][pdf]

[128]
(with B. Baetz)
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.
[ps]

web counter


David Wood 2012-02-10