Skip to main content
Springer Nature Link
Log in

Representations of graphs and networks (coding, layouts and embeddings)

  • Published:
Journal of Soviet Mathematics Aims and scope Submit manuscript

Abstract

Special representations of graphs are defined and classes of graphs which admit effective special representations are characterized. Representations of graphs by families of sets of objects of different kinds are studied, and the topological themes involved in laying out graphs on surfaces are discussed. A description is given of metric and algebraic representations of graphs in arithmetical spaces. Some results pertaining to graph representations in terms of standard operations are presented. As applications we describe results pertaining to two spheres of knowledge: automated computer design and organization of programming work on computers; and graphical representation of molecules and chemical formulas in organic and inorganic chemistry.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Literature cited

  1. A. S. Azarenok, A. G. Rudenko, and V. Ya. Stepanets, “Two methods to compute feeder and ground buses in LSI/VLSI,” Vestsi Akad. Nauk BSSR, Ser. Fiz.-Mat. Nauk, No. 5, 93–100 (1988).

    Google Scholar 

  2. A. S. Azarenok and V. I. Sarvanov, “On an approach to global routing of integrated circuits,” Vestsi Akad. Nauk BSSR, Ser. Fiz.-Mat. Nauk, No. 6, 104–107 (1988).

    Google Scholar 

  3. S. A. Arustamov, “An algorithm for constructing a general plan of the topology of MaLSI,” Avtomatiz. Konstrukt. Proektir. v Radioelektron, i Vychisl. Tekhn. (Vil'nyus),7, 9–17 (1987).

    Google Scholar 

  4. I. M. Asel'derova, “On optimal encoding of some arithmetical graphs,” in: Theory of Optimization of Decisions [in Russian], Kiev (1987), pp. 47–54.

  5. I. M. Asel'derova and G. A. Donets, “Optimal encoding of cycles and uniform trees,” in: Theory and Practice of Development and Introduction of Integration. ASU [in Russian], Kiev (1988), pp. 87–94.

  6. A. R. Belkin, “Some models of optimal approximation of diagraphs,” in: Modeling and Optimization of Systems of Complex Structure [in Russian], Omsk (1987), pp. 13–23.

  7. V. V. Belyaevskii and N. A. Lepeshinskii, “Representation of trees by distance matrix between suspended and presuspended vertices,” in: Computers — Learning Process, Science and Technology [in Russian], Vysheishaya Shkola (1985), pp. 37–40.

  8. D. N. Gainanov, A. L. Plotnikov, and V. A. Ikonnikov, “Routing of plate connections of a wiring array using a directed graph of track dependences,” Inst. Mat. Mekh. UNTs Akad. Nauk SSSR, Sverdlovsk (1985); dep. at VINITI June 26, 1985, No. 4602-85.

    Google Scholar 

  9. A. I. Gorlin, V. N. Kovalenko, V. V. Martynyuk, and E. V. Khukhlaev, “Parametrization of drawings by sizes, based on specification of a sample. Construction of a copy by the method of element-wise computation,” Preprint, Inst. Prikl. Mat. Akad. Nauk SSSR, No. 184 (1987).

  10. Yu. G. Grigor'yan and G. K. Manoyan, “Some questions of arithmetical interpretation of undirected graphs,” Kibernetika, No. 3, 129–131 (1977).

    Google Scholar 

  11. G. A. Donets, “On analytically specified graphs,” in: Theory of Optimization of Decisions [in Russian], Kiev (1987), pp. 20–27.

  12. A. G. Evdokimov, N. V. Grinchak, and U. Zhalilov, “Development and use of positional-listing representation of the graph of a network in designing engineering networks,” Voprosy Vychisl. Prikl. Mat. (Tashkent), No. 83, 81–86 (1987).

    Google Scholar 

  13. V. A. Evstigneev, Programming Applications of Graph Theory [in Russian], Nauka, Moscow (1985).

    Google Scholar 

  14. K. A. Zaretskii, “Construction of a Tree Given the Set of Distances Between Its Leaves,” Usp. Mat. Nauk,20, No. 6, 90–92 (1965).

    Google Scholar 

  15. A. A. Zykov, Elements of Graph Theory [in Russian], Nauka, Moscow (1987).

    Google Scholar 

  16. A. V. Ivashchenko, “Geometrical Representation of a Graph,” Kibernetika, No. 5, 120–121 (1988).

    Google Scholar 

  17. V. B. Kalinin, “On a problem of Berge,” Mat. Zametki,34, No. 1, 131–133 (1983).

    Google Scholar 

  18. V. Yu. Kayurov, “An algebraic interpretation of P-graphs,” Kibernetika, No. 5, 17–21 (1986).

    Google Scholar 

  19. A. K. Kel'mans, “Design, reconstruction, and embedding of graphs,” Preprint, Inst. Probl. Upr., Moscow (1987).

  20. V. P. Kozyrev, “Graph theory,” Itogi Nauki i Tekhniki. VINITI. Teor. Veroyatn., Mat. Stat., Teor. Kibern.,10, 25–74 (1972).

    Google Scholar 

  21. V. P. Kozyrev, “Enumeration of transitive orientations of a graph and embedding of transitive graphs,” in: Voprosy Kibernetiki (Proc. 2nd All-Union Seminar on Combinatorial Math.) [in Russian], No. 15, 44–60 (1975).

    Google Scholar 

  22. V. P. Kozyrev, “Determination of skeleton trees which are optimal with respect to several ranked criteria,” Kombinator. Analiz, No. 7, 66–74 (1986).

    Google Scholar 

  23. V. P. Kozyrev and A. D. Korshunov, “On the size of a cut in a random graph,” Probl. Kibern., No. 29, 27–62 (1974).

    Google Scholar 

  24. V. P. Kozyrev and S. V. Maiskii, “Enumeration and generation of plane rooted trees with given parameters,” in: Materials, All-Union Sem. Discrete Math, and Its Appl. [in Russian], Moscow (1988), pp. 92–99.

  25. V. P. Kozyrev and S. V. Yushmanov, “Graph theory (algorithmic, algebraic, and metric problems),” Itogi Nauki i Tekhniki. VINITI, Teor. Veroyatn., Mat. Stat., Teor. Kibern.,23, 68–117 (1985).

    Google Scholar 

  26. V. P. Korzhik, “Application of current graphs of index 2 and 3 for construction of triangular embeddings of graphs of type Kn-Km,” Kombinator. Analiz, No. 7, 87–91 (1986).

    Google Scholar 

  27. S. A. Lavrenchenko, “Enumeration in explicit form of all automorphisms of irreducible triangulations of a torus and all embeddings of labeled graphs of these triangulations in the torus,” Khar'kov. Inst. Radioelektron., Khar'kov (1987); dep. at UkrNIINTI October 1, 1987, No. 2779-Uk87.

    Google Scholar 

  28. V. V. Lozin, “Vertex coding of graphs in automatic decoding,” in: Combinatorical and Algebraic Methods in Applied Mathematics [in Russian], Gor'kii (1986), pp. 73–83.

  29. A. Matuzyavichyus and A. Mitashyunas, “Machine routing of one-sided printed plates,” Prepr. Ernst-Moritz-Arndt Univ. Greifswald, Math., No. 18, 46–49 (1987).

    Google Scholar 

  30. E. V. Mzhel'skaya, “Graphs of polycyclic connections,” Vychisl. Sistemy, No. 119, 71–90 (1987).

    Google Scholar 

  31. V. G. Mirkin and S. N. Rodin, Graphs and Genes [in Russian], Nauka, Moscow (1977).

    Google Scholar 

  32. V. P. Nekrasov, “On plane graphs having external access,” in: Combinatorical Properties of Convex Sets and Graphs, Sverdlovsk (1983), pp. 34–44.

  33. V. V. Noskov, “On rationalization of scanning procedures and search for contractions,” in: Combinatorical and Algebraic Methods in Applied Mathematics [in Russian], Gor'kii (1986), pp. 139–163.

  34. V. I. Petrenyuk, “A list of 3-minimal plane graphs,” Kirovograd Inst. Agricultural Engng., Kirovograd (1986); dep. at UkrNIINTI, October 31, 1986, No. 2450-Uk.

    Google Scholar 

  35. A. V. Petrosyan, S. E. Markosyan, and Yu. G. Shukuryan, Mathematical Questions of Computer Design Automation [in Russian], Erevan (1977).

  36. N. S. Zefirov and S. I. Kuchanov (eds.), Application of Graph Theory in Chemistry [in Russian], Nauka, Novosibirsk (1988).

    Google Scholar 

  37. Z. Sh. Puturidze and Yu. A. Niauri, “Linear representation of nonstructural complexes of P-graph commands,” Soobshch. Akad. Nauk GSSR,127, No. 3, 489–491 (1987).

    Google Scholar 

  38. F. S. Roberts, Discrete Mathematical Models with Applications to Social, Biological, and Economic Problems [Russian translation], Nauka, Moscow (1986).

    Google Scholar 

  39. E. A. Smolenskii, “On a method for linear recording of graphs,” Zh. Vychisl. Mat. Mat. Fiz.,2, 371–372 (1962).

    Google Scholar 

  40. V. P. Soltan, “d-convexity in graphs,” Dokl. Akad. Nauk SSSR,272, No. 3, 535–537 (1983).

    Google Scholar 

  41. I. V. Stankevich, “Graphs in structural chemistry,” in: Application of Graph Theory in Chemistry [in Russian], Novosibirsk (1988), pp. 7–69.

  42. R. I. Tyshkevich and A. A. Chernyak, “Unigraphs. I,” Izv. Akad. Nauk BSSR, Ser. Fiz. Mat. Nauk, No. 5, 5–11 (1978).

    Google Scholar 

  43. R. I. Tyshkevich, O. I. Mel'nikov, and V. M. Kotov, “On graphs and power sequences,” Kibernetika, No. 6, 5–8 (1981).

    Google Scholar 

  44. A. T. Fedenko and V. M. Volodin, “Properties of the method of symmetric packing of rectangles,” Moscow Inst. Chem. Engng., Moscow (1988); dep. at VINITI, May 7, 1988, No. 3574-B88.

    Google Scholar 

  45. I. S. Filotti, “An embedding algorithm for a cubic graph,” Kibernet. Sbornik (Moscow), No. 23, 5–30 (1986).

    Google Scholar 

  46. V. V. Firsov, “Isometric embedding of graphs in a Boolean cube,” Kibernetika, No. 1 (1965), pp. 95–96.

    Google Scholar 

  47. V. D. Chepoi, “Some properties of d-convexity in triangulated graphs,” Mat. Issled., No. 87, 164–171 (1986).

    Google Scholar 

  48. V. D. Chepoi, “Isometric subgraphs of Hamming graphs and d-convexity,” Kibernetika, No. 1, 6–9 (1988).

    Google Scholar 

  49. A. A. Chernyak, “On Little's conjecture about planar graphs,” Izv. Akad. Nauk BSSR, Ser. Fiz.-Mat. Nauk, No. 2, 41–45 (1980).

    Google Scholar 

  50. S. V. Yushmanov, “On a method of specifying graphs,” Vopr. Kibern. (Moscow), No. 64, 97–111 (1980).

    Google Scholar 

  51. S. V. Yushmanov, “Reconstruction of an arbitrary graph based on a subset of rows and columns of its distance matrix,” Dokl. Akad. Nauk SSSR,359, No. 1, 49–51 (1981).

    Google Scholar 

  52. S. V. Yushmanov, “Specification of a tree with p leaves by 2p-3 elements of its distance matrix,” Mat. Zametki,35, No. 6, 877–887 (1984).

    Google Scholar 

  53. S. V. Yushmanov, “Methods of graph theory in evolution. Design of phylogenetic diagrams,” in: Mathematical Cybernetics and Its Application to Biology [in Russian], Moscow (1987), pp. 101–140.

  54. S. V. Yushmanov, “Reconstruction of a phylogenetic tree given the subtrees generated by quadruples of its leaves,” in: Mathematical Cybernetics and Its Application to Biology [in Russian], Moscow (1987), pp. 141–147.

  55. S. V. Yushmanov, “On metric properties of chordal and Ptolemaic graphs,” Dokl. Akad. Nauk SSSR,300, No. 2, 296–299 (1987).

    Google Scholar 

  56. N. Alon, “Covering graphs by the minimum number of equivalence relations,” Combinatorica,6, No. 3, 201–206 (1986).

    Google Scholar 

  57. I. Anderson, “On the toroidal thickness of graphs,” J. Graph Theory,6, No. 2, 177–188 (1982).

    Google Scholar 

  58. Th. Andreae, “On an extremal problem concerning the interval number of a graph,” Discrete Appl. Math.,14, No. 1, 1–9 (1986).

    Google Scholar 

  59. Th. Andreae, “On the interval number of a triangulated graph,” J. Graph Theory,11, No. 3, 273–280 (1987).

    Google Scholar 

  60. M. E. Aragno, “Sulla superiore immergibilita di particolari graphi,” Riv. Mat. Univ. Parma,12, 35–40 (1986).

    Google Scholar 

  61. G. O. Araujo, “Algebras asociadas a un p-grafo y sus aplicaciones a un modelo matematico de la quimica estructural,” Notes Mat. Univ. Andes, No. 62, 17 (1984).

    Google Scholar 

  62. C. Arbib, “A polynomial characterization of some graph partitioning problems,” Inform. Process. Lett.,26, No. 5, 223–230 (1988).

    Google Scholar 

  63. D. S. Archdeacon and P. Huneke, “On cubic graphs which are irreducible for nonorientable surfaces,” J. Combin. Theory,B39, No. 3, 233–264 (1985).

    Google Scholar 

  64. K. Asano, “On the genus and thickness of graphs,” J. Combin. Theory,B43, No. 3, 287–292 (1987).

    Google Scholar 

  65. H.-J. Bandelt and A. Dress, “Reconstructing the shape of a tree from observed dissimilarity data,” Adv. Appl. Math.,7, No. 3, 309–343 (1986).

    Google Scholar 

  66. H.-J. Bandelt and H. M. Mulder, “Distance-hereditary graphs,” J. Combin. Theory,B41, No. 2, 182–208 (1986).

    Google Scholar 

  67. H.-J. Bandelt and E. Wilkeit, “Dwarf, brick and triangulation of the torus,” Discrete Math.,67, No. 1, 1–14 (1987).

    Google Scholar 

  68. S. C. Basak, V. R. Magnuson, G. J. Niemi, and R. R. Regal, “Determining structural similarity of chemicals using graph-theoretic indices,” Discrete Appl. Math.,19, No. 1–3, 17–44 (1988).

    Google Scholar 

  69. C. Batini, E. Nardelli, and R. Tamassia, “A layout algorithm for data flow diagrams,” IEEE Trans. Software Eng.,12, No. 4, 538–546 (1986).

    Google Scholar 

  70. B. Becker and G. Holtz, “On the optimal layout of planar graphs with fixed boundary,” SIAM J. Comput.,16, No. 5, 946–972 (1987).

    Google Scholar 

  71. B. Becker and H. G. Osthof, “Layouts with wires of balanced length,” Lect. Notes Comput. Sci.,182, 21–31 (1985).

    Google Scholar 

  72. E. A. Bender, E. R. Canfield, and R. W. Robinson, “The asymptotic number of tree-rooted map on a surface,” J. Combin. Theory,A48, No. 2, 156–164 (1988).

    Google Scholar 

  73. C. Benzaken, P. L. Hammer, and D. de Werra, “Split graphs of Dilworth number 2,” Discrete Math.,55, No. 2, 123–127 (1985).

    Google Scholar 

  74. A. A. Bertossi, “Finding Hamiltonian circuits in proper interval graphs,” Inform. Process. Lett.,17, No. 2, 97–101 (1983).

    Google Scholar 

  75. A. A. Bertossi, “Dominating sets for split and bipartite graphs,” Inform. Process. Lett.,19, No. 1, 37–40 (1984).

    Google Scholar 

  76. S. N. Bhatt and F. T. Leighton, “A framework for solving VLSI graph layout problems,” Mass. Inst. Technol. Lab. Comput. Sci. Techn. Rept., No. 305 (1983).

  77. D. Bienstock and C. L. Monma, “On the complexity of covering vertices in a planar graph,” SIAM J. Comput.,17, No. 1, 53–76 (1988).

    Google Scholar 

  78. R. Bodendiek, “On graphs not being embeddable into the torus,” Graphs, Hypergraphs and Appl., Proc. Conf. Graph Theory, Eyba, Oct. 1–5, 1984, Leipzig, 7–14 (1985).

  79. R. Bodendiek and K. Wagner, “A characterization of the minimal basis of the torus,” Combinatorica.6, No. 3, 245–260 (1986).

    Google Scholar 

  80. M. A. Bonuccelli, “Dominanting sets and domatic number of circular arc graphs,” Discrete Appl. Math.,12, No. 3, 203–213 (1985).

    Google Scholar 

  81. K. S. Booth and J. H. Johnson, “Dominanting sets in chordal graphs,” SIAM J. Comput.,11, No. 1, 191–199 (1982).

    Google Scholar 

  82. K. S. Booth and G. S. Lucker, “Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms,” J. Comput. and Syst. Sci.,13, No. 3, 335–379 (1976).

    Google Scholar 

  83. A. Bouchet, “Characterizing and recognizing circle graphs,” Graph Theory, Proc. 6th Yugosl. Semin., Dubrovnik, April 18–19, 1985, Novi Sad, 57–69 (1986).

  84. A. Bouchet, “Un algorithme polynomial pour reconnaitre les graphes d'alternance,” C. R. Acad. Sci., sér. 1,300, No. 16, 569–572 (1985).

    Google Scholar 

  85. A. Bouchet, “Reducing prime graphs and recognizing circle graphs,” Combinatorica,7, No. 3, 243–254 (1987).

    Google Scholar 

  86. A. Brandstädt, “Characterizations of split permutation graphs,” Algebra und Graphentheor. Beitr. Jahrestag, Siebenlehn, Oct. 28–Nov. 1, 1985, Freiberg, 21–24 (1986).

  87. N. Breier, “Pattiell-rekursive Graphwortfunktionen,” J. Inf. Process. and Cybern. EIK.,23, No. 4–5, 171–179 (1987).

    Google Scholar 

  88. S. Bublitz, “Decomposition of graphs and monotone formula size of homogeneous functions,” Acta Inform.,23, No. 6, 689–696 (1986).

    Google Scholar 

  89. P. Buneman, “The recovery of trees from measures of dissimilarity,” in: Mathematics in Archaeological and Historical Sciences, Edinburgh, University Press, 387–395 (1971).

    Google Scholar 

  90. P. Buneman, “A note on the metric properties of trees,” J. Combin. Theory,B17, No. 1, 48–50 (1974).

    Google Scholar 

  91. P. Buneman, “A characterization of rigid circuit graphs,” Discrete Math.,9, No. 3, 205–212 (1974).

    Google Scholar 

  92. M. Carpano, “Automatic display of hierarchized graphs for computer-aided decision analysis,” IEEE Trans. Syst., Man, and Cybern.,10, No. 11, 705–715 (1980).

    Google Scholar 

  93. S. Chaiken, A. K. Dewdney, and P. J. Slater, “An optimal diagonal tree code,” SIAM J. Alg. Disc. Math.,4, No. 1, 42–49 (1983).

    Google Scholar 

  94. G. J. Chang and G. L. Nemhauser, “The k-domination and k-stability problems on sunfree chordal graphs,” SIAM J. Algebraic and Discrete Methods,5, No. 3, 332–345 (1984).

    Google Scholar 

  95. P. Charrier and J. Roman, “Étude de la séparation et de l'élimination sur une famille de graphes quotients déduite d'une méthode de dissections emboitées,” RARIO. Inf. Théor. et Appl.,22, No. 2, 245–265 (1988).

    Google Scholar 

  96. N. Chiba, K. Onoguchi, and T. Nishizeki, “Drawing planar graphs nicely,” Acta inform.,22, 187–201 (1985).

    Google Scholar 

  97. N. Chiba, T. Yamanouchi, and T. Nishizeki, “Linear algorithms for convex drawings of planar graphs,” in: Progress in Graph Theory, J. A. Bondy and V. S. R. Murty (eds.), Acad. Press, N.Y., 153–173 (1984).

    Google Scholar 

  98. F. Y. Chin, “Security in statistical databases for queries with small counts,” ACM Transaction on Database Systems,3, No. 1, 92–104 (1978).

    Google Scholar 

  99. F. R. K. Chung, R. L. Graham, and P. M. Winkler, “On the addressing problem for directed graphs,” Graphs and Comb.,1, No. 1, 41–50 (1985).

    Google Scholar 

  100. H. Colonius and H. H. Schulze, “Tree structures for proximity data,” Brit. J. Math. and Statist. Psychol.,34, 167–180 (1981).

    Google Scholar 

  101. M. B. Cozzens and F. S. Roberts, “Computing the boxicity of a graph by covering its complement by cointerval graphs,” Discrete Appl. Math.,6, No. 3, 217–228 (1983).

    Google Scholar 

  102. J. P. Cunningham, “Free trees and bidirectional trees as representations of psychological distance,” J. Math. Psychol.,17, No. 2, 165–188 (1978).

    Google Scholar 

  103. W. H. Cunningham, “Decomposition of directed graphs,” SIAM J. Algebraic Discrete Methods,3, No. 3, 214–228 (1982).

    Google Scholar 

  104. D. Cvetkovic and I. Pevac, “Man-machine theorem proving in graph theory,” Artif. Intell.,35, No. 1, 1–23 (1988).

    Google Scholar 

  105. P. Czerwinski and V. Ramachandran, “Optimal VLSI graph embeddings in variable aspect ratio rectangles,” Algorithmica,3, No. 4, 487–510 (1988).

    Google Scholar 

  106. H. De Fraysseix and P. Rosenstiehl, “A depth-firat-search characterization of planarity,” Graph Theory, Amsterdam, 75–80 (1982).

  107. G. Di Battista and E. Nardelli, “An algorithm for testing planarity of hierarchical graphs,” in: Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science 246, G. Tinhofer and G. Schmidt (eds.), Springer, Berlin, 277–289 (1987).

    Google Scholar 

  108. G. Di Battista and R. Tamassia, “Algorithms for plane representations of acyclic diagraphs,” Theoretical Computer Science,61, No. 2–3, 175–198 (1988).

    Google Scholar 

  109. R. Diestel, “Simplicial decompositions of graphs — some uniqueness results,” J. Combin. Theory,B42, No. 2, 133–145 (1987).

    Google Scholar 

  110. R. Diestel, “Tree-decompositions, tree-representability, and chordal graphs,” Discrete Math.,71, No. 2, 181–184 (1988).

    Google Scholar 

  111. P. F. Dietz, “Intersection graph algorithms,” Ph. D. Thesis, Cornell University, 1984.

  112. G. A. Dirac, “On rigid circuit graphs,” Abh. Math. Semin. Univ. Hamburg,25, No. 1–2, 71–76 (1961).

    Google Scholar 

  113. D. Z. Djoković, “Distance-preserving subgraphs of hypercubes,” J. Combin. Theory,B14, No. 3, 263–267 (1973).

    Google Scholar 

  114. A. W. M. Dress, “Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: A note on combinatorial properties of metric spaces,” Adv. Math.,53, 321–402 (1984).

    Google Scholar 

  115. P. Duchet, Y. Hamidoune, M. Las Vergnas, and H. Meyniel, “Representing a planar graph by vertical lines joining different levels,” Discrete Math.,46, No. 3, 319–321 (1983).

    Google Scholar 

  116. M. E. Dyer and A. M. Frieze, “On the complexity of partitioning graphs into connected subgraphs,” Discrete Appl. Math.,10, No. 2, 139–153 (1985).

    Google Scholar 

  117. M. E. Dyer and A. M. Frieze, “Planar 3DM is NP-complete,” J. Algorithms,7, No. 2, 174–184 (1986).

    Google Scholar 

  118. P. Eades and D. Kelly, “Heuristics for reducing crossings in 2-layered networks,” Ars Combin.,21, No. 1, 89–98 (1986).

    Google Scholar 

  119. P. Eades, B. McKay, and N. Wormald, “An NP-hard crossing number problem for bipartite graphs,” Tech. Rept. 60, Dept. of Computer Science, Univ. of Queensland, 1985.

  120. G. Ehrlich, S. Even, and R. E. Tarjan, “Intersection graphs of curves in the plane,” J. Combin. Theory,B21, No. 1, 8–20 (1976).

    Google Scholar 

  121. P. Erdös, R. Faudree, and E. T. Ordman, “Clique partitions and clique coverings,” Discrete Math.,72, No. 1–3, 93–101 (1988).

    Google Scholar 

  122. P. Erdös and D. B. West, “A note on the interval number of a graph,” Discrete Math.,55, No. 2, 129–133 (1985).

    Google Scholar 

  123. S. Even and A. Itai, “Queues, stacks and graphs,” in: Theory of Machines and Computations, Acad. Press, N.Y., 71–80 (1971).

    Google Scholar 

  124. S. Even, A. Pnueli, and A. Lempel, “Permutation graphs and transitive graphs,” J. Assoc. Comput. Mach.,19, No. 3, 400–410 (1972).

    Google Scholar 

  125. J. Feigenbaum, J. Herhberger, A. A. Schäffer, “A polynomial time algorithm for finding the prime factors of Cartesian-product graphs,” Discrete Appl. Math.,12, No. 2, 123–138 (1985).

    Google Scholar 

  126. R. B. Feinberg, “The circular dimension of a graph,” Discrete Math.,25, No. 1, 27–31 (1979).

    Google Scholar 

  127. J. Felsenstein, “Numerical methods for inferring evolutionary trees,” Quart. Rev. Biol.,57, No. 4, 379–404 (1982).

    Google Scholar 

  128. I. S. Filotti, G. Miller, and J. Reif, “On determining the genus of a graph in O(n0(g)) steps,” Proc. 11th Annu. ACM Symp. Theory Comput., 27–37 (1979).

  129. P. C. Fishburn, “On the sphericity and cubicity of graphs,” J. Combin. Theory,B35, No. 3, 309–318 (1983).

    Google Scholar 

  130. P. C. Fishburn, Interval orders and interval graphs: A study of partially ordered sets, New York (1985).

  131. E. Flapan, “Symmetries of knotted hypothetical molecular graphs,” Discrete Appl. Math.,19, No. 1–3, 157–166 (1988).

    Google Scholar 

  132. S. Foldes and P. L. Hammer, “Split graphs,” Proc. 8th South-Eastern Conf. on Combinatorics, Graph Theory and Comput. (Bosa Raton, 1977); Bosa Raton, Florida Atlant. Univ., 1977, 311–315.

  133. J. C. Fourier, “Une caracterization des graphs de cordes,” C. R. Acad. Sci. Paris,A286, 811–813 (1978).

    Google Scholar 

  134. P. Frankl and H. Maehara, “On the contact dimensions of graphs,” Discrete Comput. Geom.,3, No. 1, 89–96 (1987).

    Google Scholar 

  135. P. Frankl and H. Maehara, “The Johnson-Lindenstrauss lemma and the sphericity of some graphs,” J. Combin. Theory,B44, No. 3, 355–362 (1988).

    Google Scholar 

  136. H. de Fraysseix, “A characterization of circle graphs,” Eur. J. Comb.,5, No. 3, 223–238 (1984).

    Google Scholar 

  137. L. C. Freeman, “Spheres, cubes, and boxes: graph dimensionality and network structure,” Soc. Networks,5, No. 2, 139–156 (1983).

    Google Scholar 

  138. D. R. Fulkerson and O. A. Gross, “Incidence matrices and interval graphs,” Pacif. J. Math.,15, 835–855 (1965).

    Google Scholar 

  139. C. P. Gabor, W.-L. Hsu, and K. J. Supowit, “Recognizing circle graphs in polynomial time,” in: 26th Annu. Symp. Found. Comput. Sci., Portland, Ore., October 21–23, 1985, Washington, D. C, 1985, 106–116.

  140. H. Galina and M. M. Systo, “Some applications of graph theory to the study of polymer configuration,” Discrete Appl. Math.,19, No. 1–3, 167–176 (1988).

    Google Scholar 

  141. M. R. Garey and D. S. Johnson, “Crossing number is NP-complete,” SIAM J. Alg. Disc. Math.,4, No. 3, 312–316 (1983).

    Google Scholar 

  142. M. R. Garey, D. S. Johnson, G. L. Miller, and C. H. Papadimitriou, “The complexity of coloring circular arcs and chords,” SIAM J. Algebraic and Discrete Methods,1, 216–227 (1980).

    Google Scholar 

  143. E. A. Gattass and G. L. Nemhauser, “An application of vertex packing to data analysis in the evaluation of pavement deterioration,” Oper. Res. Lett.,1, No. 1, 13–17 (1981).

    Google Scholar 

  144. F. Gavril, “Algorithms for a maximum clique and a maximum independent set of a circle graph,” Networks,3, 261–273 (1973).

    Google Scholar 

  145. F. Gavril, “The intersection graphs of subtrees in trees are exactly the chordal graphs,” J. Combin. Theory,B16, No. 1, 47–56 (1974).

    Google Scholar 

  146. F. Gavril, “A recognition algorithm for the intersection graphs of directed paths in directed trees,” Discrete Math.,13, No. 3, 237–249 (1975).

    Google Scholar 

  147. F. Gavril, “A recognition algorithm for the intersection graphs of paths in trees,” Discrete Math.,23, No. 3, 211–227 (1978).

    Google Scholar 

  148. P. C. Gilmore and A. J. Hoffman, “A characterization of comparability graphs and of interval graphs,” Can. J. Math.,16, No. 3, 539–548 (1964).

    Google Scholar 

  149. J. Gimbel, “End vertices in interval graphs,” Discrete Appl. Math.,21, No. 3, 257–259 (1988).

    Google Scholar 

  150. M. C. Golumbic, Algorithmic graph theory and perfect graphs, N. Y., Adad. Press, 1980.

    Google Scholar 

  151. M. C. Golumbic, “Algorithmic aspects of intersection graphs and representation hypergraphs,” Graphs and Comb,4, No. 4, 307–327 (1988).

    Google Scholar 

  152. M. C. Golumbic and P. L. Hammer, “Stability in circular are graphs,” J. Algorithms,9, No. 3, 314–320 (1988).

    Google Scholar 

  153. M. C. Golumbic and R. E. Jamison, “The edge intersection graphs of paths in a tree,” J. Combin. Theory,B38, No. 1, 8–22 (1985).

    Google Scholar 

  154. M. C. Golumbic and R. E. Jamison, “Edge and vertex intersection of paths in a tree,” Discrete Math.,55, No. 2, 151–159 (1985).

    Google Scholar 

  155. M. C. Golumbic and C. L. Monma, “A generalization of interval graphs with tolerances,” Congressus Numerantium35, 321–331 (1982).

    Google Scholar 

  156. M. C. Golumbic, C. L. Monma, and W. T. Trotter (Jr.), “Tolerance graphs,” Discrete Appl. Math.,9, No. 2, 157–170 (1984).

    Google Scholar 

  157. M. C. Golumbic, D. Rotem, and J. Urrutia, “Comparability graphs and intersection graphs,” Discrete Math.,43, No. 1, 37–46 (1983).

    Google Scholar 

  158. R. L. Graham and H. O. Pollak, “On the addressing problem for loop switching,” J. Bell Syst. Techn.,50, No. 8, 2495–2519 (1971).

    Google Scholar 

  159. R. L. Graham and H. O. Pollak, “On embedding graphs in squashed cubes,” Lect. Notes Math.,303, 99–110 (1972).

    Google Scholar 

  160. R. L. Graham and P. M. Winkler, “Isometric embeddings of graphs,” Proc. Nat. Acad. Sci. USA, Phys. Sci.,81, No. 2, 7259–7260 (1984).

    Google Scholar 

  161. R. L. Graham and P. M. Winkler, “On isometric embeddings of graphs,” Trans. Amer. Math. Soc,288, No. 2, 527–536 (1985).

    Google Scholar 

  162. J. R. Griggs, “Extremal values of the interval number of a graph. II,” Discrete Math.,28, No. 1, 37–47 (1979).

    Google Scholar 

  163. J. R. Griggs and D. B. West, “Extremal values of the interval number of a graph,” SIAM J. Algebraic Discrete Methods,1, No. 1, 1–7 (1980).

    Google Scholar 

  164. U. I. Gupta, D. T. Lee, and J. Y.-T. Leung, “Efficient algorithms for interval graphs and circular-arc graphs,” Networks,12, No. 4, 459–467 (1982).

    Google Scholar 

  165. S. E. Hambrusch and J. Simon, “Solving undirected graph problems on VLSI,” SIAM J. Comput.,14, No. 3, 527–544 (1985).

    Google Scholar 

  166. P. L. Hammer and B. Simeone, “The splittance of a graph,” Combinatorica,1, No. 3, 275–284 (1981).

    Google Scholar 

  167. F. Harary and F. Buckley, “On the euclidean dimension of a wheel,” Graphs and Comb.,4, No. 1, 23–30 (1988).

    Google Scholar 

  168. F. Harary, J. A. Kabell, and F. R. McMorris, “Bipartite intersection graphs,” Comment. Math. Univ. Carol.,23, No. 4, 739–745 (1982).

    Google Scholar 

  169. F. Harary, R. A. Melter, and I. Tomescu, “Digital metrics: A graph-theoretical approach,” Pattern Recogn. Lett.,2, No. 3, 159–163 (1984).

    Google Scholar 

  170. N. Hartsfield, “The toroidal splitting number of the complete graph Kn,” Discrete Math.,62, 35–47 (1986).

    Google Scholar 

  171. N. Hartsfield, “The splitting number of the complete graph in the projective plane,” Graphs and Comb.,3, No. 4, 349–356 (1987).

    Google Scholar 

  172. N. Hartsfield, B. Jackson, and G. Ringel, “The splitting number of the complete graph,” Graphs and Comb.,1, 311–329 (1985).

    Google Scholar 

  173. T. E. Havel, The combinatorial distance geometry approach to the calculation of molecular conformation, Ph. D. Thesis, University of California, Berkeley, 1982.

    Google Scholar 

  174. F. Hoffmann and K. Kriegel, “Embedding rectilinear graphs in linear time,” Inform. Process. Lett.,29, No. 2, 75–79 (1988).

    Google Scholar 

  175. P. Horák and J. Siran, “On a modified concept of thickness of a graph,” Math. Nachr.,108, 305–306 (1982).

    Google Scholar 

  176. E. Howe, C. R. Johnson, and J. Lawrece, “The structure of distances in networks,” Networks,16, No. 1, 87–106 (1986).

    Google Scholar 

  177. E. Howorka, “A characterization of Ptolemaic graphs,” J. Graph. Theory,5, No. 3, 323–331 (1981).

    Google Scholar 

  178. W.-L. Hsu, “Maximum weight clique algorithms for circular-arc graphs and circle graphs,” SIAM J. Comput.,14, No. 1, 224–231 (1985).

    Google Scholar 

  179. W.-L. Hsu, “Recognizing planar perfect graphs,” J. Assoc. Comput. Mach.,34, No. 2, 255–288 (1987).

    Google Scholar 

  180. L. Hubert, “Some applications of graph theory and related nonmetric techniques to problems of approximate seriation: the case of symmetric proximity measures,” Brit. J. Math. Statist. Psychol.,27, No. 2, 133–153 (1974).

    Google Scholar 

  181. J. P. Hutchinson, “Automorphism properties of embedded graphs,” J. Graph Theory, No. 1, 35–49 (1984).

    Google Scholar 

  182. W. Imrich and G. Schwartz, “Trees and length functions in groups,” Ann. Discrete Math.,17, 347–359 (1983).

    Google Scholar 

  183. X. Jin, “Large processors are good in VLSI chips,” Inform. Process. Lett.,18, No. 1, 47–49 (1984).

    Google Scholar 

  184. D. S. Johnson, “The NP-completeness column: an ongoing guide,” J. Algorithms.6, No. 3, 434–451 (1985).

    Google Scholar 

  185. A. D. Jovanovic, “Combinatorial characterization of hexagonal systems,” Discrete Appl. Math.,19, No. 1–3, 259–270 (1988).

    Google Scholar 

  186. J. R. Jungch, G. Dick, and A. G. Dick, “Computer-assisted sequencing, interval graphs, and molecular evolution,” Biosystems,15, 259–273 (1982).

    Google Scholar 

  187. M. Karpinski and K. W. Wagner, “The computational complexity of graph problems with succinct multigraph representation,” ZOR: Z. Oper. Res.,32, No. 3–4, 201–211 (1988).

    Google Scholar 

  188. D. Kelly, “Fundamentals of planar ordered sets,” Discrete Math.,63, No. 2–3, 197–216 (1987).

    Google Scholar 

  189. D. G. Kendall, “Some problems and methods in statistical archaeology,” World Archaeology,1, No. 1, 61–76 (1969).

    Google Scholar 

  190. S. Klavzar and M. Petkovsek, “Intersection graphs of halflines and halfplanes,” Discrete Math.,66, No. 1–2, 133–137 (1987).

    Google Scholar 

  191. D. Kleitman, F. T. Leighton, M. Lepley, and G. L. Miller, “An asymptotically optimal layout for the suffle-exchange graph,” MIT Lab. Comput. Sci. Techn. Memo., No. 231 (1982).

  192. D. Kleitman and K. J. Winston, “On the number of graphs without 4-cycles,” Discrete Math.,41, No. 2, 167–172 (1982).

    Google Scholar 

  193. P. Klenovcan, “Direct product decompositions of diagraphs,” Math. Slov.,38, No. 1, 3–10 (1988).

    Google Scholar 

  194. L. T. Kou, L. J. Stockmeyer, and C. K. Wong, “Covering edges by cliques with regard to keyword conflicts and intersection graphs,” Comm. ACM,21, 231–236 (1978).

    Google Scholar 

  195. J. Kratochvil, M. Goljan, and P. Kucera, “String graphs,” Rozpr. CSAV MPV,96, No. 3, (1986).

  196. S. Lavrenchenko, “An infinite set of torus triangulations of connectivity 5 whose graphs are not uniquely embeddable in the torus,” Discrete Math.,66, No. 3, 299–301 (1987).

    Google Scholar 

  197. M. Leclerc, “A graph-theoretical approach to a problem in circuit design,” Mitt. Math. Semin. Giessen., No. 175, 19–26 (1986).

    Google Scholar 

  198. F. T. Leighton, “New lower bound techniques for VLSI,” Math. Syst. Theory,17, No. 1, 47–70 (1984).

    Google Scholar 

  199. F. T. Leighton and A. L. Rosenberg, “Three-dimensional circuit layouts,” SIAM J. Cornput.,15, No. 3, 793–813 (1986).

    Google Scholar 

  200. E. Leiss, “Data base security and the representation of graphs as query graphs,” Congressus Numerantium,33, 167–183 (1981).

    Google Scholar 

  201. C. G. Lekkerkerker and J. Ch. Boland, “Representation of a finite graph by a set of intervals on the real line,” Fund. Math.,51, No. 1, 45–64 (1962).

    Google Scholar 

  202. N. Linial, L. Lovasz, and A. Wigderson, “Rubber bands, convex embeddings, and graph connectivity,” Combinatorica,8, No. 1, 91–102 (1988).

    Google Scholar 

  203. C. H. C. Little, “On rings of circuits in planar graphs,” Lect. Notes Math.,622, 133–140 (1977).

    Google Scholar 

  204. L. Lovasz, “Perfect graphs,” in: Selected Topics in Graph Theory 2, Acad. Press, N.Y., 55–87 (1983).

    Google Scholar 

  205. F. Luccio, S. Mazzone, and C. K. Wong, “A note on visibility graphs,” Discrete Math.,64, No. 2–3, 209–219 (1987).

    Google Scholar 

  206. C. Maas, “Some results about the interval numbers of a graph,” Discrete Appl. Math.,6, No. 1, 99–102 (1983).

    Google Scholar 

  207. C. Maas, “Determining the interval number of triangle-free graph,” Computing,31, No. 4, 347–354 (1983).

    Google Scholar 

  208. H. Maehara, “On time graphs,” Discrete Math.,32, No. 3, 281–289 (1980).

    Google Scholar 

  209. H. Maehara, “Space graphs and sphericity,” Discrete Appl. Math.,7, No. 1, 55–64 (1984).

    Google Scholar 

  210. H. Maehara, “A digraph represented by a family of boxes or spheres,” J. Graph Theory,8, No. 3, 431–439 (1984).

    Google Scholar 

  211. H. Maehara, “Sphericity exceeds cubicity for almost all complete bipartite graphs,” J. Combin. Theory,B40, No. 2, 231–235 (1986).

    Google Scholar 

  212. H. Maehara, “On the euclidean dimension of a complete multipartite graph,” Discrete Math.,72, No.1–3, 285–289 (1988).

    Google Scholar 

  213. H. Maehara, J. Reiterman, V. Rödl, and E. Sinajova, “Embedding of trees in euclidean space,” Graphs Comb.,4, No. 1, 43–47 (1988).

    Google Scholar 

  214. N. V. R. Mahadev and U. N. Peled, “Strict 2-threshold graphs,” Discrete Appl. Math.,21, No. 2, 113–131 (1988).

    Google Scholar 

  215. M. May and K. Szkatula, “On the bipartite crossing number,” Contr. and Cybern.,17, No. 1, 85–98 (1988).

    Google Scholar 

  216. F. R. McMorris and D. R. Shier, “Representing chordal graphs on K1,n,” Comment. Math. Univ. Carol.,24, No. 3, 489–494 (1983).

    Google Scholar 

  217. G. L. Miller, “Finding small simple cycle separators for 2-connected planar graphs,” J. Comput. and Syst. Sci.,32, No. 3, 265–279 (1986).

    Google Scholar 

  218. G. L. Miller, “An additivity theorem for the genus of a graph,” J. Combin. Theory,B43, No. 1, 25–47 (1987).

    Google Scholar 

  219. B. Mohar, “Embeddings of infinite graphs,” J. Combin. Theory,44, No. 1, 29–43 (1988).

    Google Scholar 

  220. B. Mohar, “Nonorientable genus of nearly complete bipartite graphs,” Discrete and Comput. Geom.,3, No. 2, 137–146 (1988).

    Google Scholar 

  221. B. Monien and I. H. Sudborough, “Min Cut is NP-complete for edge weighted trees,” Theor. Comput. Sci.,58, No. 1–3, 209–229 (1988).

    Google Scholar 

  222. C. L. Monma and V. K. Wei, “Intersection graphs of paths in a tree,” J. Combin. Theory,B41, No. 2, 141–181 (1986).

    Google Scholar 

  223. B. P. Mull, R. G. Rieper, and A. T. White, “Enumerating 2-cell imbeddings of connected graphs,” Proc. Amer. Math. Soc.,103, No. 1, 321–330 (1988).

    Google Scholar 

  224. W. Naji, “Reconnaissance des graphes de cordes,” Discrete Math.,54, No. 3, 329–337 (1985).

    Google Scholar 

  225. K. Nakajima and M. Sun, “On an efficient implementation of a planarity testing algorithm for a graph with local constraints,” Proc. 20th Annu. Allerton Conf., Commun., Contr. and Comput. Monticello, Ill., October 6–8, 1982. S. 1, s.a., 656–664.

  226. S. Negami, “Uniqueness and faithfulness of embedding of toroidal graphs,” Discrete Math.,44, No. 2, 161–180 (1983).

    Google Scholar 

  227. S. Negami, “Uniquely and faithfully embeddable projective-planar triangulations,” J. Combin. Theory,B36, No. 2, 189–193 (1984).

    Google Scholar 

  228. S. Negami, “Enumeration of projective-planar embeddings of graphs,” Discrete Math.,62, No. 3, 299–306 (1986).

    Google Scholar 

  229. S. Negami, “Re-embedding of projective-planar graphs,” J. Combin. Theory,B44, No. 3, 276–299 (1988).

    Google Scholar 

  230. S. Negami, “The spherical genus and virtually planar graphs,” Discrete Math.,70, No. 2, 159–168 (1988).

    Google Scholar 

  231. J. Nesetril and R. Thomas, “A note on spatial representation of graphs,” Comment. Math. Univ. Carol.,26, No. 4, 655–659 (1985).

    Google Scholar 

  232. R. J. Opsut and F. S. Roberts, “On the fleet maintenance, mobile radio frequency, task assignment, and traffic phasing problems,” in: The Theory and Applications of Graphs, G. Chartrand, Y. Alavi, D. L. Goldsmith, L. Lesniak-Foster, and D. R. Lick (eds.), Wiley, New York, 1981, 479–492.

    Google Scholar 

  233. R. J. Opsut and F. S. Roberts, “Optimal I-intersection assignments for graphs: A linear programming approach,” Networks,13, No. 3, 317–326 (1983).

    Google Scholar 

  234. J. B. Orlin, M. A. Bonuccelli, and D. P. Bovet, “An O(n2) algorithm for coloring proper circular-arc graphs,” SIAM J. Algebraic and Discrete Methods,2, No. 1, 88–93 (1981).

    Google Scholar 

  235. R. H. J. M. Otten and J. G. van Wijk, “Graph representations in interactive layout design,” Proc. IEEE Int. Symp. on Circuits and Systems, 914–918, New York, 1978.

  236. L. Oubina and R. Zucchello, “A generalization of outerplanar graphs,” Discrete Math.,51, No. 3, 243–249 (1984).

    Google Scholar 

  237. T. D. Parsons, G. Pica, T. Pisanski, and A. G. S. Ventre, “Orientably simple graphs,” Math. Slov.,37, No. 4, 391–394 (1987).

    Google Scholar 

  238. T. D. Parsons and T. Pisanski, “Inner-product representations of graphs,” Graph Theory, Proc. 6th Yugosl. Semin., Dubrovnik, April 18–19, 1985, Novi Sad, 1986, 151–157.

  239. G. W. Peck, “A new proof of a theorem of Graham and Pollak,” Discrete Math.,49, No. 3, 327–328 (1984).

    Google Scholar 

  240. B. Perunicic and Z. Duric, “An efficient algorithm for embedding graphs in the projective plane,” Graph Theory. Proc. 6th Yugosl. Semin., Dubrovnik, April 18–19, 1985, Novi Sad, 1986, 159–171.

  241. M. Petrovsek and T. Pisanski, “A note on function graphs, ” Graph Theory. Proc. 6th Yugosl. Semin., Dubrovnik, April 18–19, 1985, Novi Sad, 1986, 179–182.

  242. T. Pisanski, “Nonorientable genus of Cartesian products of regular graphs,” J. Graph Theory,6, No. 4, 391–402 (1982).

    Google Scholar 

  243. M. D. Plummer, “Matching extension and the genus of a graph,” J. Combin. Theory,B44 No. 3, 329–337 (1988).

    Google Scholar 

  244. A. Pnueli, A. Lempel, and S. Even, “Transitive orientation of graphs and identification of permutation graphs,” Can. J. Math.,23, No. 1, 160–175 (1971).

    Google Scholar 

  245. S. Poljak, V. Rödl, and D. Turzik, “Complexity of representation of graphs by set systems,” Discrete Appl. Math.,3, 301–312 (1981).

    Google Scholar 

  246. R. Raghavan, J. Cohoon, and S. Sahni, “Single bend wiring,” J. Algorithms,7, No. 2, 232–257 (1986).

    Google Scholar 

  247. I. V. Ramakrishnan and P. J. Varman, “On mapping cube graphs onto VLSI arrays,” Lect. Notes Comput. Sci.,181, 296–316 (1984).

    Google Scholar 

  248. R. C. Read, D. Rotem, and J. Urrutia, “Orientations of circle graphs,” J. Graph Theory,6, No. 3, 325–341 (1982).

    Google Scholar 

  249. P. L. Renz, “Intersection representations of graphs by arcs,” Pacif. J. Math.,34, No. 2, 501–510 (1970).

    Google Scholar 

  250. R. B. Richter, “On the nonorientable genus of a 2-connected graph,” J. Combin. Theory,B43, No. 1, 48–59 (1987).

    Google Scholar 

  251. R. B. Richter, “On the Eulerian genus of a 2-connected graph,” J. Combin. Theory,B43, No. 1, 60–69 (1987).

    Google Scholar 

  252. R. B. Richter and H. Shank, “The cycle space of an embedded graph,” J. Graph Theory,8, No. 3, 365–369 (1984).

    Google Scholar 

  253. F. S. Roberts, “Indifference graphs,” in: Proof Techn. Graph Theory, N.Y., Acad. Press, 1969, 139–146.

    Google Scholar 

  254. F. S. Roberts, “On the boxicity and cubicity of a graph,” in: Recent Progr. in Combinator., N.Y., Acad. Press, 1969, 301–310.

    Google Scholar 

  255. F. S. Roberts, “Food webs, competition graphs, and the boxicity of ecological phase space,” in: Theory and Applications of Graphs, Y. Alavi and D. Lick (eds.), Springer, New York, 1978), 477–490.

    Google Scholar 

  256. F. S. Roberts, “Applications of edge coverings by cliques,” Discrete Appl. Math.,10, No. 1, 93–109 (1985).

    Google Scholar 

  257. N. Robertson and P. D. Seymour, “Graph minors. VI. Disjoint paths across a disc,” J. Combin. Theory,B41, No. 1, 115–138 (1986).

    Google Scholar 

  258. N. Robertson and P. D. Seymour, “Graph minors. VII. Disjoint paths on a surface,” J. Combin. Theory,B45, No. 2, 212–254 (1988).

    Google Scholar 

  259. P. Rosenstiehl and R. E. Tarjan, “Gauss codes, planar Hamiltonian graphs, and stack-sortable permutations,” J. Algorithms,5, No. 3, 375–390 (1984).

    Google Scholar 

  260. P. Rosenstiehl and R. E. Tarjan, “Rectilinear planar layouts of planar graphs and bi-polar orientations,” Discrete & Comput. Geom.,1, 342–351 (1986).

    Google Scholar 

  261. D. Rotem and J. Urrutia, “Circular permutation graphs,” Networks,12, No. 4, 429–437 (1982).

    Google Scholar 

  262. Ryu Hae Dong and Li Chong I, “The study on the maximum genus of graphs,” Suhak, No. 3, 13–16 (1986).

    Google Scholar 

  263. H. Sachs, “On a spatial analogue of Kuratowski's theorem on planar graphs — an open problem,” Lect. Notes Math.,1018, 230–241 (1983).

    Google Scholar 

  264. S. Sattath and A. Tversky, “Additive similarity trees,” Psychometrica,42, No. 3, 319–345 (1977).

    Google Scholar 

  265. E. R. Scheinerman, “Characterizing intersection classes of graphs,” Discrete Math.,55, No. 2, 185–193 (1985).

    Google Scholar 

  266. E. R. Scheinerman, “Irrepresentability by multiple intersection, or why the interval number is unbounded,” Discrete Math.,55, No. 2, 195–211 (1985).

    Google Scholar 

  267. E. R. Scheinerman, “Irredundancy in multiple interval representations,” Discrete Math.,63, No. 1, 101–108 (1987).

    Google Scholar 

  268. E. R. Scheinerman, “The maximum interval number of graphs with given genus,” J. Graph Theory,11, No. 3, 441–446 (1987).

    Google Scholar 

  269. E. R. Scheinerman and D. B. West, “The interval number of a planar graph: three intervals suffice,” J. Combin. Theory,B35, No. 3, 224–239 (1983).

    Google Scholar 

  270. M. Schlag, F. Luccio, P. Maestrini, D. T. Lee, and C. K. Wong, “A visibility problem in VLSI layout compaction,” in: Advances in Computing Research, Vol. 2, JAI Press Inc., Greenwich, CT, 1985, 259–282.

    Google Scholar 

  271. F. Scotti, “II complementare di un grafo non superiormente immergibile é superiormente immergibile,” Boll. Unione mat. ital.,A3, No. 1, 111–118 (1984).

    Google Scholar 

  272. J. Sedlacek, “O jednom zobeeneni vnejskove rivinnych grafu,” Cas. pestov. mat.,113, No. 2, 213–218 (1988).

    Google Scholar 

  273. Shaohan Majand W. D. Wallis, “Maximal-clique partitions of interval graphs,” J. Austral Math. Soc. A,45, No. 2, 227–232 (1988).

    Google Scholar 

  274. J. B. Shearer, “A note on circular dimension,” Discrete Math.,29, No. 1, 103 (1980).

    Google Scholar 

  275. X. Shen and H. Edelsbrunner, “A tight lower bound on the size of visibility graphs,” Inform. Process. Lett.,26, No. 2, 61–64 (1987).

    Google Scholar 

  276. Yoschi Shiraishi, “A planar description algorithm of a vertex-grouped graph and its application to a channel assignment problem,” Int. Symp. Circuits and Syst., Proc., Kyoto, June 5–7, 1985, Vol. 1, New York, N.Y., s.a., 195–198.

    Google Scholar 

  277. J. M. S. Simoes-Pereira, “A note on the tree realizability of a distance matrix,” J. Combin. Theory,6, No. 3, 303–310 (1969).

    Google Scholar 

  278. F. W. Sinden, “Topology of thin film RC-circuits,” Theorie graphes. Journées internat. étude, Rome, 1966, Paris-New York, 1967, 389–393.

  279. J. Sirán, “Crossing-critical edges and Kuratowski subgraphs of a graph,” J. Combin. Theory,B35, No. 2, 83–92 (1983).

    Google Scholar 

  280. J. Sirán, “Edges and Kuratowski subgraphs of nonplanar graphs,” Math. Nachr.,113, 187–190 (1983).

    Google Scholar 

  281. J. Siráň and P. Horak, “A construction of thickness-minimal graphs,” Discrete Math.,64, No. 2–3, 263–268 (1987).

    Google Scholar 

  282. J. Siráň and M. Skoviera, “Relative embeddings of graphs on closed surfaces,” Math. Nachr.,136, 275–284 (1988).

    Google Scholar 

  283. J. Siráň and M. Škoviera, “Oriented relative embeddings of graphs,” Zastos. mat.,19, No. 3–4, 589–597 (1987).

    Google Scholar 

  284. D. Skrien, “Chronological orderings of interval graphs,” Discrete Appl. Math.,8, No. 1, 69–83 (1984).

    Google Scholar 

  285. D. Skrien and J. Gimbel, “Homogeneously representable interval graphs,” Discrete Math.,55, No. 2, 213–216 (1985).

    Google Scholar 

  286. J. Spinrad, “On comparability and permutation graphs,” SIAM J. Comput.,14, No. 3, 658–670 (1985).

    Google Scholar 

  287. J. Spinrad and D. B. West, “An improved edge bound on the interval number of a graph,” J. Graph Theory,11, No. 3, 447–449 (1987).

    Google Scholar 

  288. F. W. Stahl, “Circular genetic maps,” J. Cell Physiol.,70, No. 1, 1–12 (1967).

    Google Scholar 

  289. W. Stanczak, “An efficient algorithm for partitioning a network into minimally inter-connected subnetworks,” Contr. and Cybern.,13, No. 1–2, 97–112 (1984).

    Google Scholar 

  290. J. E. Steif, “The frame dimension and the complete overlap dimension of a graph,” J. Graph Theory,9, No. 2, 285–299 (1985).

    Google Scholar 

  291. K. E. Stoffers, “Scheduling of traffic lights — a new approach,” Transp. Res.,2, 199–234 (1968).

    Google Scholar 

  292. J. A. Storer, “On minimal node-cost planar embeddings,” Networks,14, 181–212 (1984).

    Google Scholar 

  293. G. Sugihara, “Graph theory, homology and food webs,” Popul. Biol. Lect. Notes, Amer. Math. Soc. Short Course, Albany, N.Y., August 6–7, 1983, Providence, R.I., 1984, 83–101.

  294. K. Sugiyama, S. Tagawa, and M. Toda, “Methods for visual understanding of hierarchical systems,” IEEE Trans, on Syst., Man, and Cybern.,SMC-11, 109–125 (1981).

    Google Scholar 

  295. M. M. Syslo, “Triangulated edge intersection graphs of paths in a tree,” Discrete Math.,55, No. 2, 217–220 (1985).

    Google Scholar 

  296. R. Tamassia, “On embedding a graph in the grid with the minimum number of bends,” SIAM J. Comput.,16, No. 1, 421–444 (1987).

    Google Scholar 

  297. R. Tamassia and I. G. Tollis, “A unified approach to visibility representations of planar graphs,” Discrete Comput. Geom.,1, 321–341 (1986).

    Google Scholar 

  298. R. E. Tarjan, “Decomposition by clique separators,” Discrete Math.,55, No. 2, 221–231 (1985).

    Google Scholar 

  299. R. E. Tarjan and M. Yannakakis, “Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs,” SIAM J. Comput.,13, No. 3, 566–579 (1984).

    Google Scholar 

  300. C. Thomassen, “Plane representations of graphs,” in: Progress in Graph Theory, Academic Press, N.Y., 1984, 43–69.

    Google Scholar 

  301. C. Thomassen, “Planarity and duality of finite and infinite graphs,” J. Combin. Theory,B29, No. 2, 244–271 (1980).

    Google Scholar 

  302. C. Thomassen, “Interval representations of planar graphs,” J. Combin. Theory,B40, No. 1, 9–20 (1986).

    Google Scholar 

  303. W. T. Trotter (Jr.), “A characterization of Roberts' inequality for boxity,” Discrete Math.,28, No. 3, 303–313 (1979).

    Google Scholar 

  304. W. T. Trotter (Jr.) and F. Harary, “On double and multiple interval graphs,” J. Graph Theory,3, No. 3, 205–211 (1979).

    Google Scholar 

  305. W. T. Trotter (Jr.) and D. B. West, “Poset boxicity of graphs,” Discrete Math.,64, No. 1, 105–107 (1987).

    Google Scholar 

  306. A. Tucker, “Matrix characterizations of circular-arc graphs,” Pacif. J. Math.,39, No. 2, 535–545 (1971).

    Google Scholar 

  307. A. Tucker, “Structure theorems for some circular-arc graphs,” Discrete Math.,7, No. 1–2, 167–195 (1974).

    Google Scholar 

  308. A. Tucker, “Circular arc graphs: new uses and new algorithm,” Lect. Notes Math., No. 642, 580–589 (1978).

    Google Scholar 

  309. A. Tucker, “An efficient test for circular-arc graphs,” SIAM J. Comput.,9, No. 1, 1–24 (1980).

    Google Scholar 

  310. W. T. Tutte, “Convex representations of graphs,” Proc. London Math. Soc.,10, No. 38, 304–320 (1960).

    Google Scholar 

  311. M. Veldhorst, “The optimal representation of disjoint iso-oriented rectangles in two-dimensional trees,” J. Algorithms,7, No. 1, 1–34 (1986).

    Google Scholar 

  312. H.-J. Voss, “Note on a paper of McMorris and Shier,” Comment. Math. Univ. Carol.,26, No. 2, 319–322 (1985).

    Google Scholar 

  313. J. R. Walter, “Representations of chordal graphs as subtrees of a tree,” J. Graph. Theory,2, No. 3, 265–267 (1978).

    Google Scholar 

  314. H. J. Walther, “On a conjecture of W. Klotz concerning clique-decomposition of graphs,” Graphs, Hypergraphs, and Matroids. II. Zielona Góra, 83–88 (1987).

  315. J. Warfield, “Crossing theory and hierarchy mapping,” IEEE Trans. Syst., Man, and Cybern.,SMC-7, 502–523 (1977).

    Google Scholar 

  316. G. Wegner, “Eigenschaften der Nerven homolgish-eigenfacher Familien in Rh,” Ph. Thesis Göttingen, 1967.

  317. E. Welzl, “Constructing the visibility graph for n-line segments in O(n2) time,” Inform. Process. Lett.,20, No. 4, 167–171 (1985).

    Google Scholar 

  318. W. Wessel, “Chord graphs — new means for representing graphs,” Zastos, Mat.,19, No. 3–4, 619–627 (1987).

    Google Scholar 

  319. W. Wessel, “The non-biplanar character of the graph K10-K3,” Prepr. Akad. Wiss. DDR, Karl-Weierstrass Inst. Math., No. 3, 1–21 (1988).

    Google Scholar 

  320. D. B. West and D. B. Shmoys, “Recognizing graphs with fixed interval number is NP-complete,” Discrete Appl. Math.,8, No. 3, 295–305 (1984).

    Google Scholar 

  321. K. White, M. Farber, and W. Pulleyblank, “Steiner trees, connected domination and strongly chordal graphs,” Networks,15, No. 1, 109–124 (1985).

    Google Scholar 

  322. H. S. Wilf, “Finite lists of obstructions,” Amer. Math. Mon.,94, No. 3, 267–271 (1987).

    Google Scholar 

  323. P. M. Winkler, “Proof of the squashed cube conjecture,” Combinatorica,3, No. 1, 135–139 (1983).

    Google Scholar 

  324. P. M. Winkler, “Isometric embedding in products of complete graphs,” Discrete Appl. Math.,7, No. 2, 221–225 (1984).

    Google Scholar 

  325. P. M. Winkler, “Every connected graph is a query graph,” J. Combinatorics, Inf. and Syst. Sci.,10, No. 1–2, 1–4 (1985).

    Google Scholar 

  326. P. M. Winkler, “The metric structure of graphs: theory and applications,” London Math. Soc. Lect. Note Ser., No. 123, 197–221 (1987).

    Google Scholar 

  327. H. S. Witsenhausen, “On intersections of interval graphs,” Discrete Math.,31, No. 2, 211–216 (1980).

    Google Scholar 

  328. H. S. Witsenhausen, “Minimum dimension embedding of finite metric spaces,” J. Combin. Theory,A42, No. 4, 184–199 (1986).

    Google Scholar 

  329. D. Wolfe, “Imbedding a finite metric set in an N-dimensional Minkowski space,” Proc. Koninkl. nederl. akad. wet.,A70, No. 1, 136–140 (1967).

    Google Scholar 

  330. D. Woods, “Drawing planar graphs, Ph. D. Thesis,” Computer Science Dept., Stanford Univ., 1982.

  331. Chiko Yoshioka and Chieko Tanabe, “On some embedding of complete graphs,” Mem. Fac. Educ. Niigata Univ. Nat. Sci.,28, No. 2, 57–62 (1987).

    Google Scholar 

  332. V. Zeleznik, “Quadrilateral embeddings of the conjunction of graphs,” Math. Slov.,38, No. 2, 89–98 (1988).

    Google Scholar 

  333. T. P. Zivkovic, “Graphical representation of regular resonance structures and their linear dependence,” Discrete Appl. Math.,19, No. 1–3, 397–414 (1988).

    Google Scholar 

Download references

Authors
  1. V. P. Kozyrev
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. S. V. Yushmanov
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Translated from Itogi Nauki i Tekhniki, Seriya Teoriya Veroyatnostei, Matematicheskaya Statistika, Teoreticheskaya Kibernetika, Vol. 27, pp. 129–196, 1990.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Kozyrev, V.P., Yushmanov, S.V. Representations of graphs and networks (coding, layouts and embeddings). J Math Sci 61, 2152–2194 (1992). https://doi.org/10.1007/BF01097528

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01097528

Keywords

Search

Navigation