Publications of Imrich Vrt'o


Books and Chapters in Books:

  1. Czabarka, E., Sykora, O., Szekely, L.A., Vrt'o, I., "Biplanar crossing number: A survey of problems and results", in: More Sets, Graphs and Numbers (G., Ervin, L. Lovasz, G.O.H. Katona, eds.), Bolyai Society Mathematical Studies, Vol. 15. Springer, Berlin, 2006, 57-77.

  2. Shahrokhi, F., Sykora, O., Szekely, L.A., Vrt'o, I., ``The gap between crossing numbers and convex crossing numbers", in: Towards a Theory of Geometric Graphs (J. Pach, ed.), Contemporary Mathematics, Vol. 342, AMS, 2004, 249-258.
    CONFERENCE VERSION: in: Proc. COCOON 2003, Lecture Notes in Computer Science 2697, Springer, Berlin, 2003, 487-495.

  3. Shahrokhi, F., Sykora, O., Szekely, L.A., Vrt'o, I., "Crossing numbers: bounds and applications", in: Intuitive Geometry, (I. Barany, K. Boroczky, eds.), Bolyai Society Mathematical Studies 6, Akademia Kiado, Budapest, 1997, 179-206.

  4. Miklosko, J., Klette, R., Vajtersic, M., Vrt'o, I., "Fast Algorithms and their Implementation on Specialized Parallel Computers", North-Holland, Amsterdam, 1989.


Articles in Journals:

  1. Bokal, D., Czabarka, E., Szekely, L.A., Vrt'o, I., "General lower bounds for the minor crossing number of graphs", Discrete and Computational Geometry 44 (2010), 463-483.

  2. Vrt'o, I., "A note on isoperimetric peaks of complete trees", Discrete Mathematics 310 (2010), 1272-1274.

  3. Torok, L., Vrt'o, I., "Antibandwidth of three-dimensional meshes", Discrete Mathematics 310 (2010), 505-510.

  4. Calamoneri, T, Massini, A., Torok, L., Vrt'o, I., "Antibandwidth of complete k-ary trees", Discrete Mathematics 309 (2009), 6408-6414.

  5. Dobrev, S., Pardubska, D., Kralovic, Torok, L., Vrt'o, I., ``Antibandwidth and cyclic antibandwidth of Hamming graphs", Electronic Notes in Discrete Mathematics 34 (2009), 295-300.

  6. Raspaud, A., Schroder, H., Sykora, O., Torok, L., Vrt'o, I., ``Antibandwidth and cyclic antibandwidth of meshes and hypercubes", Discrete Mathematics 309 (2009), 3541-3552.

  7. Geyer, M., Kaufmann, M., Vrt'o, I., ``Two trees which are self-intersecting when drawn simultaneously", Discrete Mathematics 307 (2009), 1909-1916.
    CONFERENCE VERSION: in: Proc. 13th Intl. Symposium on Graph Drawing, Lecture Notes in Computer Science 3843, Springer, Berlin, 2003, 201-210.

  8. Czabarka, E., Sykora,O., Szekely, L.A., Vrt'o,I., ``Biplanar crossing numbers. II. Comparing crossing numbers and biplanar crossing numbers using the probabilistic method", Random Structures and Algorithms 33 (2008), 480-496.

  9. Faria, L., de Figueiredo, C.M.H., Sykora, O., Vrt'o, I., ``An improved upper bound on the crossing number of the hypercube", Journal of Graph Theory 59 (2008), 145-161.
    CONFERENCE VERSION: in: Proc. 29th Intl. Workshop on Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science 2880, Springer, Berlin, 2003, 230-236.

  10. Shahrokhi, F., Sykora, O., Szekely, L.A., Vrt'o, I., ``On k-planar crossing numbers", Discrete Applied Mathematics 155 (2007), 1106-1115.
    CONFERENCE VERSION: ``Bounds and methods for k-planar crossing numbers" in: Proc. 11th Intl. Symposium on Graph Drawing, Lecture Notes in Computer Science 2912, Springer, Berlin, 2003, 37-46.

  11. Bokal, D., Czabarka, E., Szekely, L.A., Vrt'o, I, "Graph minors and the crossing number of graphs", Electronic Notes in Discrete Mathematics 28 (2007), 169-175.

  12. Torok, L., Vrt'o, I, "Antibandwidth of 3-dimensional meshes", Electronic Notes in Discrete Mathematics 28 (2007), 161-167.

  13. Sykora, O., Torok, L., Vrt'o, I., "The cyclic antibandwidth problem", Electronic Notes in Discrete Mathematics 22 (2005), 223-227.

  14. Hongmei He, Sykora, O., Vrt'o, I., "Crossing minimisation heuristics for 2-page drawings", Electronic Notes in Discrete Mathematics 22 (2005), 527-534.

  15. Monien, B., Vrt'o, I., "Improved bounds on cutwidths of shuffle-exchange and de Bruijn graphs", Parallel Processing Letters, 14 (2004) 361-366.

  16. Czabarka, E., Sykora,O., Szekely, L.A., Vrt'o, "Outerplanar crossing numbers, the circular arrangement problem and isoperimetric functions, The Electronic Journal of Combinatorics 11 (2004), R81, 20 pages.

  17. Schroeder, H., Sykora, O., Vrt'o, I. "Cyclic cutwidths of the 2-dimensional ordinary and cylindrical meshes", Discrete Applied Mathematics 143 2004, 123-120.
    CONFERENCE VERSION: in: Proc. SOFSEM'99: Theory and Practice of Informatics, Lecture Notes in Computer Science 1725, Springer, Berlin, 1999, 443-451.

  18. Sykora, O., Szekely, L.A., Vrt'o, I., "A note on Halton's conjecture", Information Sciences 164 (2004), 61-64.

  19. Dobrev, S., Vrt'o, I., "Dynamic faults have small effect on broadcasting in hypercubes", Discrete Applied Mathematics 137 (2004), 155-158.

  20. Djidjev, H.N., Vrt'o, I., "Crossing numbers and cutwidths", Journal of Graph Algorithms and Applications 7 (2003), 245-251.
    CONFERENCE VERSION: in: Proc. 9th Intl. Symp. on Graph Drawing, Lecture Notes in Computer Science 2265, Springer, Berlin 2001, 95-101.

  21. Calamoneri, T., Massini, A., Vrt'o, I., "New results on edge-bandwidth", Theoretical Computer Science 307 (2003), 503-513.

  22. Cimikowski, R., Vrt'o, I., "Improved bounds for the crossing number of the mesh of trees", Journal of Interconnection Networks 4 (2003), 17-36.

  23. Dobrev, S., Vrt'o, I, "Optimal broadcasting in even tori with dynamic faults", Parallel Processing Letters 12 (2002), 17-22.
    CONFERENCE VERSION: in: Proc. Euro-Par2000, Lecture Notes in Computer Science 1900, Springer, Berlin, 2000, 927-930.

  24. Paterson, M.S., Schroeder, H., Sykora, O., Vrt'o, I., "On permutation communications in all-optical rings", Parallel Processing Letters 12 (2002), 23-30.
    CONFERENCE VERSION: in: Proc. 5th Intl. Colloquium on Structural Information and Communication Complexity, SIROCCO 5, Proceedings in Informatics 3, Carleton Scientific, Ottawa, 1998, 1-9.

  25. Vrt'o, I., "Cutwidth of the r-dimensional mesh of d-ary trees", Informatique, Theorique et Applications/Theoretical Informatics and Applications 34 (2000), 515-520.
    CONFERENCE VERSION: in: Proc. Europar'97, Lecture Notes in Computer Science 1300, Springer, Berlin, 1997, 242-245.

  26. Shahrokhi, F., Sykora, O., Szekely, L.A., Vrt'o, I., "On bipartite drawings and the linear arrangement problem", SIAM J. Computing 30 (2000), 1773-1789.
    CONFERENCE VERSION: "On the bipartite crossings, largest biplanar subgraphs, and the linear arrangement problem", in: Proc. 5th Intl. Workshop on Algorithms and Data Structures, WADS'97, Lecture Notes in Computer Science 1272, Springer, Berlin, 1997, 55-68.

  27. Dobrev, S., Schroder, H., Sykora, O., Vrt'o, I., "Evolutionary graph colouring", Information Processing Letters 76 (2000), 91-94.
    CONFERENCE VERSION: in: Proc. 6th Intl. Colloquium on Structural Information and Communication Complexity, SIROCCO 6, (C. Gavoille, J.S.Bermond, A. Raspaud, eds.), Carleton Scientific, Ottawa, 1999, 105-110.

  28. Shahrokhi, F., Sykora, O., Szekely, L.A., Vrt'o, I., "A new lower bound for the bipartite crossing number with applications", Theoretical Computer Science 245 (2000), 281-294.
    CONFERENCE VERSION: "Bipartite crossing numbers of meshes and hypercubes", in: Proc. 5th Intl. Symposium on Graph Drawing, Lecture Notes in Computer Science 1353, Springer, Berlin, 1997, 37-46.

  29. Stacho, L., Vrt'o, I., "Virtual path layouts in ATM networks", SIAM J. Computing, 29 (2000), 1621-1629.
    CONFERENCE VERSION: in: Proc. Structure, Information and Communication Complexity, 3rd Colloquium SIROCCO'96, International Informatics Series 6, (N. Santoro, P. Spirakis, eds.), Carleton University Press, Ottawa, 1997, 269-278.

  30. Dobrev, S., Vrt'o, I., "Optimal broadcasting in hypercubes with dynamic faults", Information Processing Letters 71 (1999), 81-85.
    CONFERENCE VERSION: "Two broadcasting problems in faulty hypercubes", in: Proc. 25th Intl. Workshop on Graph-Theoretic Concepts in Computer Science , Lecture Notes in Computer Science 1665, Springer, Berlin, 1999, 173-178.

  31. Rolim, J., Trdlicka, J., Tvrdik, P., Vrt'o, I., "Bisecting de Bruijn and Kautz graphs", Discrete Applied Mathematics 85 (1998), 87-97.
    CONFERENCE VERSION: in: Proc. Structure, Information and Communication Complexity, 2nd Intl. Colloquium on Structural Information and Communication Complexity, Carleton University Press, Ottawa, 1996, 211-222.

  32. Shahrokhi, F., Sykora, O., Szekely, L.A., Vrt'o, I., Intersection of curves and crossing number of C_m x C_n on surfaces, Discrete and Computational Geometry 19 (1998), 237-247.
    CONFERENCE VERSION: "Crossing numbers of meshes", in: Proc. 4th Intl. Symposium on Graph Drawing, Lecture Notes in Computer Science 1027, Springer, Berlin, 1996, 462-471.

  33. Stacho, L., Vrt'o, I., "Bisection widths of transposition graphs", Discrete Applied Mathematics 84 (1998), 221-235.
    CONFERENCE VERSION: in: Proc. 7th IEEE Symposium on Parallel and Distributed Processing , IEEE Computer Society Press, Los Alamitos, 1995, 681-688.

  34. Shahrokhi, F., Sykora, O., Szekely, L. A., Vrt'o, I., "The crossing number of a graph on a compact 2-manifold", Advances in Mathematics 123 (1996), 105-119.

  35. Shahrokhi, F., Sykora, O., Szekely, L. A., Vrt'o, I., "Drawing graphs on surfaces with few crossings", Algorithmica 16 (1996), 118-131.
    CONFERENCE VERSION: "Improved bounds on the crossing numbers on surfaces of genus g in: Proc. 19th Intl. Workshop on Graph-Theoretic Concepts in Computer Science, WG'93, Lecture Notes in Computer Science 790, Springer, Berlin, 1994, 388-395.

  36. Shahrokhi, F., Sykora, O., Szekely, L. A., Vrt'o, I., "The book crossing number of a graph", J. Graph Theory 21 (1996) 413-424.
    CONFERENCE VERSION: "Book embeddings and crossing numbers", in: Proc. 20th Intl. Workshop on Graph-Theoretic Concepts in Computer Science, WG'94, Lecture Notes in Computer Science 903, Springer, Berlin, 1995, 256-268.

  37. Raspaud, A., Sykora, O., Vrt'o, I., "Cutwidth of the de Bruijn graph", RAIRO - Theoretical Informatics and Applications 29 (1995), 509-514.

  38. Vrt'o, I., "Two remarks on `Expanding and Forwarding' by P. Sole", Discrete Applied Mathematics 58 (1995), 85-89.

  39. Hromkovic, J., Muller, V., Sykora, O., Vrt'o, I., "On embeddings in cycles", Information and Computation 118 (1995), 302-305.
    CONFERENCE VERSION: "On embeddings interconnection networks into rings of processors", in: Proc. Parallel Architectures and Languages Europe, PARLE'92, Lecture Notes in Computer Science 605, Springer, Berlin, 1992, 53-62.

  40. Sykora, O., Vrt'o, I., "On VLSI layouts of the star graph and related networks", Integration, The VLSI Journal 17 (1994), 83-93.

  41. Paterson, M.S., Schroder, H., Sykora, O., Vrt'o, I., "A short proof of the dilation of a toroidal mesh in a path", Information Processing Letters 48 (1993), 197-199.
    CONFERENCE VERSION: Schroder, H., Sykora, O. and Vrt'o, I., "Optimal embedding of a toroidal array in a linear array", in: Proc. 8-th Intl. Symposium on Fundamentals of Computation Theory, FCT`91, Lecture Notes in Computer Science 529, Springer, Berlin, 1991, 390-394.

  42. Diks, K., Djidjev, H. N., Sykora, O., Vrt'o, I., "Edge separators for planar and outerplanar graphs with applications", J. of Algorithms 14 (1993), 258-279.
    CONFERENCE VERSION: in: Proc. 13-th Intl. Symposium on Mathematical Foundation of Computer Science, MFCS`88, Lecture Notes in Computer Science 324, Springer, Berlin, 1988, 280-290.

  43. Sykora, O., Vrt'o, I., "Edge separators for graphs of bounded genus with applications", Theoretical Computer Science A 112 (1993), 419-429.
    CONFERENCE VERSION: in: Proc. 17-th Intl. Workshop on Graph-Theoretic Concepts in Computer Science, WG'91, Lecture Notes in Computer Science 570, Springer, Berlin, 1992, 159-168.

  44. Sykora, O., Vrt'o, I., "On the crossing number of the hypercube and the cube connected cycles", BIT 33 (1993), 232-237.
    CONFERENCE VERSION: in: Proc. 17-th Intl. Workshop on Graph-Theoretic Concepts in Computer Science, WG'91, Lecture Notes in Computer Science 570, Springer, Berlin, 1992, 214-218.

  45. Palko, V., Sykora. O., Vrt'o, I., "Area complexity of merging", Theoretical Computer Science 82 (1991), 157-163.
    CONFERENCE VERSION: in: Proc. 14-th Intl. Symposium on Mathematical Foundation of Computer Science, MFCS'89, Lecture Notes in Computer Science 379, Springer, Berlin, 1989, 390-396.

  46. Chlebus, B., Vrt'o, I., "Parallel Quicksort", J. of Parallel and Distributed Computing 11 (1991), 332-337.

  47. Duris, P., Vrt'o, I., "Semelectivity is not sufficient", Information Processing Letters 37 (1991), 137-141.

  48. Vrt'o, I., "Area complexity of VLSI computations over a ring of integers modulo m, Computers and Artificial Intelligence 7 (1988), 113-119.

  49. Sykora, O., Vrt'o, I., "Tight chip area lower bounds for string matching", Information Processing Letters 26 (1987/88), 117-119.

  50. Vrt'o, I., "The area-time complexity of the VLSI counter", Information Processing Letters 25 (1987), 397-400.

  51. Duris, P., Sykora, O., Thompson, C.D., Vrt'o, I., "A minimum-area circuit for l-selection", Algorithmica 2 (1987), 251-265.

  52. Duris, P., Thompson, C.D., Sykora, O., Vrt'o, I., "Tight chip area bounds for sorting", Computers and Artificial Intelligence 4 (1985), 535-544.

  53. Duris, P., Thompson, C.D., Sykora, O., Vrt'o, I., "Tight chip area lower bounds for discrete Fourier and Walsh-Hadamard transformations", Information Processing Letters 21 (1985), 245-247.

  54. Vrt'o, I., "A lower bound on the area for n-bit multiplication chip", Computers and Artificial Intelligence 2 (1983), 161-165.

  55. Vrt'o, I., Znam, S., ``Minimal graphs of diameter two and given maximal degree", Studia Scientarum Mathematicarum Hungarica 17 (1982), 283-290.


Articles in Refereed Conference Proceedings:

(Not mentioned above)

  1. Torok, L., Vrt'o, I, "Antibandwidth of n-dimensional meshes", in: Proc. Combinatorial Algorithms, 20th International Workshop, IWOCA 2009 , Lecture Notes in Computer Science 5874, Springer, Berlin, 2009, 471-477.

  2. Djidjev, H., Vrt'o, I., "Planar crossing numbers of genus g graphs", in: Proc. 33rd International Colloquium on Automata, Languages and Programming , Lecture Notes in Computer Science 4051, Part I, Springer, Berlin, 2006, 419-430.

  3. Geyer, M., Kaufmann, M., Vrt'o, I., "Two trees which are self-intersecting when drawn simultaneously", in: Proc. 13th Intl. Symposium on Graph Drawing, Lecture Notes in Computer Science 3843, Springer, Berlin, 2006, 201-210.

  4. Fulek, R., Hongmei He, Sykora, O., Vrt'o, I., "Outerplanar crossing numbers of 3-row meshes, Halin graphs and complete p-partite graphs", in: Proc. 31st Annual Conference on Current Trends in Theory and Practice of Informatics, SOFSEM 2005, Lecture Notes in Computer Science 3381, Springer, Berlin, 2005, 371-374.

  5. Torok, L. Vrt'o, I., "Layout volumes of hypercubes" in: Proc. 12th Intl. Symp. Graph Drawing, Lecture Notes in Computer Science 3383, Springer, Berlin, 2004, 414-424.

  6. Newton, M., Sykora, O., Uzovic, M., Vrt'o, I., "New exact results and bounds for bipartite crossing numbers of meshes", in: Proc. 12th Intl. Symp. Graph Drawing , Lecture Notes in Computer Science 3383, Springer, Berlin, 2004, 360-370.

  7. Luecking, T., Mavronicolas, M., Monien, B., Rode, M., Spirakis, P., Vrt'o, I., ``Which is the worst-case Nash equilibrium?" in: Proc. 28th Intl. Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science 2747, Springer, Berlin, 2003, 551-561.

  8. Newton, M., Sykora, O., Withall, M., Vrt'o, I., ``A parallel approach to row-based VLSI layout using stochastic hill-climbing", in Proc. The 16th International Conference on Industrial & Engineering Applications of Artificial Intelligence and Expert Systems , Lecture Notes in Computer Science 2718, Springer, Berlin, 2003, 750-758.

  9. Sykora, O., Szekely, L.A., Vrt'o, I., ``Fractional lengths and crossing numbers", in Proc. 10th Intl. Symp. on Graph Drawing, Lecture Notes in Computer Science 2528, Springer, Berlin, 2002, 186-192.

  10. Newton, M., Sykora, O., Vrt'o, I., ``Two new heuristics for the 2-sided bipartite crossing number", in Proc. 10th Intl. Symp. on Graph Drawing, Lecture Notes in Computer Science 2528, Springer, Berlin, 2002, 312-319.

  11. Sykora, O., Szekely, L., Vrt'o, I., ``Two counterexamples in graph drawing", in: Proc. 28th Intl. Workshop on Graph-Theoretic Concepts in Computer Science , Lecture Notes in Computer Science 2573, Springer, Berlin, 2002, 389-396.

  12. Munoz, X.M., Unger, W., Vrt'o, I., ``One-side crossing minimization is NP-hard for forests of stars of degree 4", in Proc. 9th Intl. Symp. on Graph Drawing , Lecture Notes in Computer Science 2265, Springer, Berlin 2001, 115-123.

  13. Chlebus, B., Dobrev, S., Malewicz, G., Kowalski, D., Shvartsman, A., Vrt'o, I., ``Towards practical deterministic write-all algorithm", in: Proc. 13th ACM Symposium on parallel algorithms and architectures, ACM Press, 2001, 271-280.

  14. Fertin, G., Raspaud, A., Schroder, H., Sykora, O., Vrt'o, I., ``Diameter of the Knoedel graph", in: Proc. 26th Intl. Workshop on Graph Theoretic Concepts in Computer Science , Lecture Notes in Computer Science 1928, Springer, Berlin, 2000, 149-160.

  15. Raspaud, A., Sykora, O., Vrt'o, I., ``Congestion and dilation, similarities and differences - a survey", in: Proc. 7th Intl. Colloquium on Structural Information and Communication Complexity, SIROCCO 7, Carleton Scientific, Ottawa, 2000, 269-280.

  16. Shahrokhi, F., Vrt'o, I., "On 3-layer crossings and pseudolinear arrangements", in: Proc. 7th Symposium on Graph Drawing 1999, Lecture Notes in Computer Science 1731, Springer, Berlin, 1999, 225-231.

  17. Schroder, H., Sykora, O., Vrt'o, I., "Optical all-to-all communication for some product graphs", in: Proc. SOFSEM'97: Theory and Practice of Informatics, Lecture Notes in Computer Science 1338, Springer, Berlin, 1997, 555-562.

  18. Schroder, H., May, A.E., Sykora, O., Vrt'o, I., "Approximation algorithms for the vertex bipartization problem", in: Proc. SOFSEM'97: Theory and Practice of Informatics, Lecture Notes in Computer Science 1338, Springer, Berlin, 1997, 547-554.

  19. Shahrokhi, F., Szekely, L.A., Vrt'o, I., ``Crossing numbers of graphs, lower bound techniques and algorithms: a survey", in: Proc. 5th Intl. Symposium on Graph Drawing , Lecture Notes in Computer Science 894, Springer Verlag, Berlin, 1995, 131-142.

  20. Rolim, J., Sykora, O., Vrt'o, I., "Optimal cutwidths and bisection widths 2- and 3-dimensional meshes", in: Proc. 21st Intl. Workshop on Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science 1017, Springer, Berlin, 1995, 252-264.

  21. Chlebus, B., Vrt'o, I., "Unifying binary search trees and permutations", in: Proc. 8-th Intl. Conference on Fundementals of Computation Theory, FCT'91, Lecture Notes in Computer Science 529, Springer, Berlin, 1991, 190-199.

  22. Vrt'o, I., "Area-time tradeoffs for selection", in: Proc. Parallel Algorithms and Architectures, Lecture Notes in Computer Science 269, Springer, Berlin, 1987, 163-168.

  23. Sykora, O., Vajtersic, M., Vrt'o, I., "The proximity effect in the electron-beam lithography and its correction", (in Slovak), in: Proc. 13th Software Seminar, SOFSEM'86, 2nd Vol., VUSEIAR Bratislava, 1986, 244-246.

  24. Vrt'o, I., "Optimal VLSI algorithms for selection the maximum element of a set", in: Proc. 2nd Intl. Workshop on Parallel Processing by Cellular Automata and Arrays, PARCELLA'84, Akademie Verlag, Berlin, 1985, 232-239.

  25. Sykora, O., Vrt'o, I., "Optimal layouts of the tree of meshes with vertices on the perimeter of the bounding convex region", in: Proc. 1st Symposium on Theoretical Aspects of Computer Science, STACS'84, Lecture Notes in Computer Science 166, Springer, Berlin, 1984, 209-217.


    BACK