Vida's papers

[1]

P. Bose, K. Douieb, V. Dujmović, and J. Howat, "Layered Working-Set Trees". Submitted to ACM Transactions on Algorithms, in March 2010.
[arXiv] [pdf]

[2]

V. Dujmović, J. Gudmundsson, P. Morin, and T. Wolle, "Notes on large angle crossing graphs". Submitted to Chicago Journal of Theoretical Computer Science , in March 2010.
[arXiv] [pdf]

[3]

D. Chen, L. Devroye, V. Dujmović, and P. Morin, "Memoryless Routing in Convex Subdivisions: Random Walks Are Optimal". Submitted to Computational Geometry: Theory and Applications, in November 2009.
[arXiv] [pdf]

[4]

V. Dujmović, and D. R. Wood, "On the book thickness of k-trees". Submitted to The Electronic Journal of Combinatorics, in December 2009.
[arXiv] [pdf]

[5]

G. Aloupis, E. D. Demaine, M. L. Demaine, V. Dujmović, J. Iacono, "Meshes Preserving Minimum Feature Size". Preprint, December 2009..

[6]

V. Dujmović, J. Howat, and P. Morin, "Biased Range Trees". Submitted to Algorithmica, in November, 2009.
[arXiv] [pdf]

[7]

P. Bose, K. Douieb, V. Dujmović, and R. Fagerberg, "An O(log log n)-Competitive Binary Search Tree with Optimal Worst-Case Access Times". Submitted to the 12th Scandinavian Symposium and Workshops on Algorithm Theory, (SWAT'10) in January 2010.
[pdf]

[8]

V. Dujmović, G. Fijavz, G. Joret and D. R. Wood, "On the maximum number of cliques in a graph embedded in a surface". Submitted to European Journal of Combinatorics, in June 2009.
[arXiv] [pdf]

[9]

Z. Abel, B. Ballinger, P. Bose, S. Collette, V. Dujmović, F. Hurtado, S. D. Kominers, S. Langerman, A. Pór, and D. R. Wood, "Every large point set contains many collinear points or an empty pentagon". Submitted to Graphs and Combinatorics, in May, 2009.
[arXiv] [pdf]

[10]

S. Collette, V. Dujmović, J. Iacono, S. Langerman, and P. Morin, "Entropy, triangulation, and point location in planar subdivisions". Submitted to ACM Transactions on Algorithms, in March 2009.
[arXiv] [pdf]

[11]

G. Aloupis, P. Bose, V. Dujmović, C. Gray, S. Langerman, and B. Speckmann, "Guarding Fat Polygons and Triangulating Guarded Polygons". Submitted to Computational Geometry: Theory and Applications, in September, 2008.
[pdf]

[12]

V. Dujmović and S. Whitesides, "Three-dimensional drawing algorithms", Invited Chapter in Handbook of Graph Drawing and Visualization, Roberto Tamassia Editor, CRC Press. Preprint at
[Handbook] [pdf]

[13]

P. Bose, O. Cheong, and V. Dujmović, "A note on the perimeter of fat objects". Accepted to Computational Geometry: Theory and Applications, in June 2009.
[pdf]

[14]

P. Carmi, V. Dujmović, P. Morin, and D. R. Wood, "Distinct distances in graph drawings". The Electronic Journal of Combinatorics, 15:R107, 2008.
[arXiv] [pdf]

[15]

P. Bose, V. Dujmović, F. Hurtado, S. Langerman, P. Morin, and D. R. Wood, "A polynomial bound for untangling geometric planar graphs". Discrete and Computational Geometry , to appear.
[arXiv] [pdf]©Springer

[16]

P. Bose, V. Dujmović, D. Krizanc, S. Langerman, P. Morin, D. R. Wood and S. Wuhrer, "A Characterization of the Degree Sequences of 2-Trees", Journal of Graph Theory, vol 58(3), pp.191-209, 2008.
[pdf] [ps.gz]]©Wiley

[17]

V. Dujmović, and D. R. Wood, "Graph Treewidth and Geometric Thickness Parameters", Discrete and Computational Geometry, vol 37(4), pp. 641-670, 2007.
[pdf] [ps.gz]©Springer

[18]

P. Bose, V. Dujmović, F. Hurtado and P. Morin, "Connectivity-Preserving Transformations of Binary Images", Computer Vision and Image Understanding, Special issue dedicated to the memory of Azriel Rosenfeld, vol. 6(2), pp. 313-323, 2008.
[pdf] [ps.gz] ©Elsevier

[19]

V. Dujmović, M. Fellows, M. Kitching, G. Liotta, C. McCartin, N. Nishimura, P. Ragde, F. Rosamond, S. Whitesides, and D. R. Wood, "On the Parameterized Complexity of Layered Graph Drawing", Algorithmica, vol. 52(2), pp. 267-292, 2008.
[ps.gz]©Springer

[20]

V. Dujmović, D. Eppstein, M. Suderman and D. R. Wood, "Drawings of Planar Graphs with Few Slopes and Segments", Computational Geometry: Theory and Applications, vol. 38, pp. 194-212, 2007.
[pdf] [ps.gz] ©Elsevier

[21]

V. Dujmović, M. Suderman and D. R. Wood, "Graph Drawings with Few Slopes", Computational Geometry: Theory and Applications, vol. 38, pp. 181-193, 2007.
[pdf] [ps.gz] ©Elsevier

[22]

V. Dujmović, H. Fernau and M. Kaufmann, "Fixed Parameter Algorithms for one-sided crossing minimization -- Revisited", Journal of Discrete Algorithms, vol 6(2), pp. 313-323, 2008.
[pdf] [ps.gz] ©Elsevier

[23]

H. Brönnimann, O. Devillers, V. Dujmović, H. Everett, M. Glisse, X. Goaoc, S. Lazard, H.-S. Na, and S. Whitesides, "On the Number of maximal free line segments Tangent to Arbitrary Three-dimensional Convex Polyhedra", SIAM Journal on Computing, vol. 37(2), pp. 522--551, 2007.
[pdf] [ps.gz] ©SIAM Press

[24]

V. Dujmović, and D. R. Wood, "Upward Three-Dimensional Grid Drawings of Graphs", Order, vol 23, pp. 1-20, 2006.
[pdf] [ps.gz] ©Springer

[25]

O. Devillers, V. Dujmović, H. Everett, S. Hornus, S. Whitesides and S. Wismath, "Maintaining Visibility Information of Planar Point Sets with a Moving Viewpoint", International Journal of Computational Geometry and Applications, vol. 17(4), pp. 297-304, 2007.
[pdf] [ps.gz]

[26]

P. Bose, V. Dujmović, and D. R. Wood, "Induced Subgraphs of Bounded Degree and Bounded Treewidth", Contributions to Discrete Mathematics, vol 1(1), pp. 88-105, 2006.
[pdf] [ps.gz]

[27]

V. Dujmović and D. R. Wood, "Stacks, queues and tracks: Layouts of graph subdivisions", Discrete Mathematics and Theoretical Computer Science, vol 7, pp. 155-202, 2005.
[pdf] [ps.gz] ©DMTCS

[28]

V. Dujmović, P. Morin, and D. R. Wood, "Layout of graphs with bounded tree-width", SIAM Journal on Computing, vol 34 (3), pp. 553-579, 2005.
[pdf] [ps.gz] ©SIAM Press

[29]

V. Dujmović, M. Fellows, M. Hallett, M. Kitching, G. Liotta, C. McCartin, N. Nishimura, P. Ragde, F. Rosamond, M. Suderman, S. Whitesides, and D. R. Wood, "A Fixed-Parameter Approach to Two-Layer Planarization", Algorithmica, vol 45. pp. 159-182, 2006.
[pdf] [ps.gz] ©Springer

[30]

V. Dujmović, A. Pór and D. R. Wood, "Track layouts of graphs", Discrete Mathematics and Theoretical Computer Science, vol 6(2), pp. 497-522, 2004.
[pdf] [ps.gz] ©DMTCS

[31]

V. Dujmović and D. R. Wood, "On linear layouts of graphs", Discrete Mathematics and Theoretical Computer Science, vol. 6(2), pp. 339-358, 2004.
[pdf] [ps.gz] ©DMTCS

[32]

V. Dujmović and S. Whitesides, "An efficient fixed parameter tractable algorithm for 1-sided crossing minimization", Algorithmica, vol. 40(1), pp. 15-31, 2004.
[ps.gz] ©Springer

[33]

O. Devillers, V. Dujmović, H. Everett, X. Goaoc, S. Lazard, H-S. Na, S. Petitjean, "The expected number of 3D visibility events is linear", SIAM Journal on Computing, vol. 32(6), pp. 1586-1620, 2003.
[pdf] [ps.gz] ©SIAM Press

[34]

O. Aichholzer, C. Cortés , V. Dujmović, E. Demaine, J. Erickson, H. Meijer, M. Overmars, B. Palop, S. Ramaswami, and G. Toussaint, "Flipturning polygons", Discrete and Computational Geometry, vol. 28, pp. 231-253, 2002.
[pdf] [ps.gz]

[35]

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

[36]

P. Bose, K. Douieb, V. Dujmović, and J. Howat, "Layered Working-Set Trees". In Proceedings of the Latin American Theoretical Informatics Symposium (LATIN), 2010, to appear..
(See [1] for the full paper.)
[arXiv] [pdf]

[37]

V. Dujmović, J. Gudmundsson, P. Morin, and T. Wolle, "Notes on large angle crossing graphs". In Computing: The Australasian Theory Symposium (CATS), 2010.
(See [2] for the full paper.)
[arXiv] [pdf]

[38]

V. Dujmović, J. Howat, and P. Morin, "Biased Range Trees". In Proceedings of the 20th ACM-SIAM Symposium on Discrete Algorithms (SODA'09), pp. 486-496, 2009.
(See [6] for the full paper.)
[pdf] ©SIAM Press

[39]

V. Dujmović, K. Kawarabayashi, B. Mohar and D. R. Wood, "Improved Upper Bounds on the Crossing Number". In Proceedings of the 24th ACM Symposium on Computational Geometry (SoCG '08), pp. 375-384, 2008.
[pdf]

[40]

S. Collette, V. Dujmović, J. Iacono, S. Langerman, and P. Morin, "Distribution-sensitive point location in convex subdivisions", In Proceedings of the 19th ACM-SIAM Symposium on Discrete Algorithms, (SODA '08), pp. 912-921, 2008.
[pdf]©SIAM Press

[41]

P. Bose, V. Dujmović, F. Hurtado, S. Langerman, P. Morin, and D. R. Wood, "A polynomial bound for untangling geometric planar graphs". In Proceedings of the Topological & Geometric Graph Theory (TGGT '08), Paris, 2008. Electronic Notes in Discrete Mathematics, vol. 31, pp. 213-218, 2008.
(See [15] for the full paper.)

[42]

P. Bose, V. Dujmović, D. Krizanc, S. Langerman, P. Morin, D. R. Wood and S. Wuhrer, "A Characterization of the Degree Sequences of 2-Trees", In Proceedings of the Workshop on Analytic Algorithms and Combinatorics (ANALCO'07).
(See [16] for the full paper.)
[pdf] [ps.gz] ©SIAM Press

[43]

V. Dujmović, and D. R. Wood, "Graph Treewidth and Geometric Thickness Parameters", In Proceedings of the 13th International Symposium on Graph Drawing (GD'05), vol. 3843 of LNCS, pp. 129-140, 2006.
(See [17] for the full paper.)
[pdf] ©Springer

[44]

P. Bose, V. Dujmović, and D. R. Wood, "Induced Subgraphs of Bounded Degree and Bounded Treewidth", In Proceedings of the 31st Workshop on Graph Theoretic Concepts in Computer Science (WG'05), vol. 3787 of LNCS, pp. 175-186, 2005.
(See [26] for the full version.)
[pdf] [ps.gz] ©Springer

[45]

V. Dujmović and D. R. Wood, "Layouts of Graph Subdivisions", In Proceedings of the 12th International Symposium on Graph Drawing (GD'04), vol. 3383 of LNCS, pp. 133-143, 2004.
(See [27] for the full paper.)
[pdf] ©Springer

[46]

V. Dujmović, M. Suderman and D. R. Wood, "Really Straight Graph Drawings", In Proceedings of the 12th International Symposium on Graph Drawing (GD'04), vol. 3383 of LNCS, pp. 122-132, 2004.
(See [20] and [21] for the full papers.)
[pdf] ©Springer

[47]

H. Brönnimann, O. Devillers, V. Dujmović, H. Everett, M. Glisse, X. Goaoc, S. Lazard, H.-S. Na, and S. Whitesides, "The number of lines tangent to arbitrary convex polyhedra in 3D", In Proceedings of the 20th ACM Symposium on Computational Geometry (SoCG'04), pp. 46-55, 2004.
(See [23] for the full paper.)
[pdf] ©ACM Press

[48]

V. Dujmović and D. R. Wood, "Three-dimensional grid drawings with sub-quadratic volume", In Proceedings of the 11th International Symposium on Graph Drawing (GD'03), vol. 2912 of LNCS, pp. 190-201, 2003.
(Also appears in [35].)
[pdf] [ps.gz] ©Springer

[49]

V. Dujmović, H. Fernau and M. Kaufmann, "Fixed parameter algorithms for one-sided crossing minimization revisited", In Proceedings of the 11th International Symposium on Graph Drawing (GD'03), vol. 2912 of LNCS, pp. 332-344, 2003.
(See [22] for the full paper.)
[pdf] ©Springer

[50]

V. Dujmović and D. R. Wood, "Tree-partitions of k-trees with applications in graph layout", In Proceedings of the 29th Workshop on Graph Theoretic Concepts in Computer Science (WG'03), vol. 2880 of LNCS, pp. 205-217, 2003.
(See [28] for the journal version.)
[pdf] [ps.gz] ©Springer

[51]

V. Dujmović and S. Whitesides, "An efficient fixed parameter tractable algorithm for 1-sided crossing minimization", In Proceedings of the 10th International Symposium on Graph Drawing (GD'02), vol. 2528 of LNCS, pp. 118-130, 2002.
(Also appears in [32].)
[pdf] [ps.gz] ©Springer

[52]

V. Dujmović, P. Morin and D. R. Wood, "Path-width and three-dimensional straight-line grid drawing of graphs", In Proceedings of the 10th International Symposium on Graph Drawing (GD'02), vol. 2528 of LNCS, pp. 42-53, 2002.
(See [28] for the full paper.)
[pdf] [ps.gz] ©Springer

[53]

G. Aloupis, E. Demaine, V. Dujmović, J. Erickson, S. Langerman, H. Meijer, I. Streinu, J. O'Rourke, M. Overmars, M. Soss, and G. Toussaint, "Flat-state connectivity of linkages under dihedral motions", In Proceedings of the 13th International Symposium on Algorithms and Computation (ISAAC'02), vol.2518 of LNCS, pp. 369-380, 2002.
[pdf] [ps.gz] ©Springer

[54]

V. Dujmović, and S. Whitesides, "On validating planar worlds", In Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms (SODA'01), pp. 791-792, 2001.
[pdf] [ps.gz] ©SIAM Press

[55]

V. Dujmović, M. Fellows, M. Hallett, M. Kitching, G. Liotta, C. McCartin, N. Nishimura, P. Ragde, F. Rosamond, M. Suderman, S. Whitesides, and D. R. Wood, "A Fixed-Parameter Approach to Two Layer Planarization", In Proceedings of the 9th International Symposium on Graph Drawing (GD'01), vol. 2265 in LNCS , pp. 1-15, 2001.
(See [29] for the full paper.)
[pdf] [ps.gz] ©Springer

[56]

V. Dujmović, M. Fellows, M. Hallett, M. Kitching, G. Liotta, C. McCartin, N. Nishimura, P. Ragde, F. Rosamond, M. Suderman, S. Whitesides, and D. R. Wood, "On the Parameterized Complexity of Layered Graph Drawing", In Proceedings of the 9th European Symposium on Algorithms (ESA'01), vol. 2161 in LNCS , pp. 488-499, 2001.
(See [19] for the full paper.)
[pdf] [ps.gz] ©Springer

[57]

I. Rekleitis, V. Dujmović, and G. Dudek, "Efficient Topological Exploration", In Proceedings of IEEE International Conference in Robotics and Automation (ICRA '99), pp. 676-681, IEEE Press, 1999.

[58]

P. Bose, L. Devroye, K. Douieb, V. Dujmović, J. King, and P. Morin, "Odds-on trees". Preprint, February 2010.
[arXiv] [note].

[59]

D. Chen, L. Devroye, V. Dujmović, and P. Morin, "Memoryless Routing in Convex Subdivisions: Random Walks Are Optimal". In Proceedings of the 26th European Conference on Computational Geometry (EuroCG '10), to appear.
(See [3 ] for the full paper.)

[60]

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

[61]

G. Aloupis, P. Bose, V. Dujmović, C. Gray, S. Langerman, and B. Speckmann "Guarding Fat Polygons and Triangulating Guarded Polygons", In Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG'08), to appear.
(See [11] for the full paper.)

[62]

M. Damian, E. Demaine, M. Demaine, V. Dujmović, D. El-Khechen, R. Flatland, J. Iacono, S. Langerman, H. Meijer, S. Ramaswami, D. Souvaine, P. Taslakian and G. Toussaint, "Curves in the Sand: Algorithmic Drawing", In Proceedings of the 18h Canadian Conference on Computational Geometry (CCCG'06), pp. 11-15, 2006.
[pdf]

[63]

O. Devillers, V. Dujmović, H. Everett, S. Hornus, S. Whitesides and S. Wismath, "Maintaining Visibility Information of Planar Point Sets with a Moving Viewpoint", In Proceedings of the 17th Canadian Conference on Computational Geometry, (CCCG'05), pp. 302-305, 2005.
(See [25] for the full paper.)
[pdf] [ps.gz]

[64]

H. Brönnimann, O. Devillers, V. Dujmović, H. Everett, M. Glisse, X. Goaoc, S. Lazard, H.-S. Na, and S. Whitesides, "On the number of lines tangent to four convex polyhedra", In Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG'02), pp. 113-117, 2002.
[pdf] [ps.gz]

[65]

O. Aichholzer, C. Cortés , V. Dujmović, E. Demaine, J. Erickson, H. Meijer, M. Overmars, B. Palop, S. Ramaswami, and G. Toussaint, "Flipturning polygons", In Proceedings of Japan Conference on Discrete and Computational Geometry (JCDCG'00)}, pp. 107-108, 2000.
(See [34] for the full paper.)
[pdf] [ps.gz] ©Springer