Representations of graphs and networks (coding, layouts and embeddings). (English. Russian original) Zbl 0784.05054
J. Sov. Math. 61, No. 3, 2152-2194 (1992); translation from Itogi Nauki Tekh., Ser. Teor. Veroyatn., Mat. Stat., Teor. Kibern. 27, 129-196 (1990).
See the review in Zbl 0748.05076.
MSC:
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 68R10 | Graph theory (including graph drawing) in computer science |
Citations:
Zbl 0748.05076References:
| [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). |
| [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). |
| [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). |
| [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. |
| [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). |
| [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). |
| [13] | V. A. Evstigneev, Programming Applications of Graph Theory [in Russian], Nauka, Moscow (1985). · Zbl 0561.90060 |
| [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). |
| [15] | A. A. Zykov, Elements of Graph Theory [in Russian], Nauka, Moscow (1987). · Zbl 0645.05001 |
| [16] | A. V. Ivashchenko, ?Geometrical Representation of a Graph,? Kibernetika, No. 5, 120?121 (1988). |
| [17] | V. B. Kalinin, ?On a problem of Berge,? Mat. Zametki,34, No. 1, 131?133 (1983). · Zbl 0529.05056 |
| [18] | V. Yu. Kayurov, ?An algebraic interpretation of P-graphs,? Kibernetika, No. 5, 17?21 (1986). |
| [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). |
| [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). |
| [22] | V. P. Kozyrev, ?Determination of skeleton trees which are optimal with respect to several ranked criteria,? Kombinator. Analiz, No. 7, 66?74 (1986). |
| [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). |
| [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). · Zbl 0606.05057 |
| [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). |
| [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. |
| [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). |
| [30] | E. V. Mzhel’skaya, ?Graphs of polycyclic connections,? Vychisl. Sistemy, No. 119, 71?90 (1987). |
| [31] | V. G. Mirkin and S. N. Rodin, Graphs and Genes [in Russian], Nauka, Moscow (1977). |
| [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. |
| [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). |
| [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). · Zbl 0709.68503 |
| [38] | F. S. Roberts, Discrete Mathematical Models with Applications to Social, Biological, and Economic Problems [Russian translation], Nauka, Moscow (1986). |
| [39] | E. A. Smolenskii, ?On a method for linear recording of graphs,? Zh. Vychisl. Mat. Mat. Fiz.,2, 371?372 (1962). |
| [40] | V. P. Soltan, ?d-convexity in graphs,? Dokl. Akad. Nauk SSSR,272, No. 3, 535?537 (1983). |
| [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). |
| [43] | R. I. Tyshkevich, O. I. Mel’nikov, and V. M. Kotov, ?On graphs and power sequences,? Kibernetika, No. 6, 5?8 (1981). |
| [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. |
| [45] | I. S. Filotti, ?An embedding algorithm for a cubic graph,? Kibernet. Sbornik (Moscow), No. 23, 5?30 (1986). · Zbl 0607.05029 |
| [46] | V. V. Firsov, ?Isometric embedding of graphs in a Boolean cube,? Kibernetika, No. 1 (1965), pp. 95?96. · Zbl 0152.41102 |
| [47] | V. D. Chepoi, ?Some properties of d-convexity in triangulated graphs,? Mat. Issled., No. 87, 164?171 (1986). |
| [48] | V. D. Chepoi, ?Isometric subgraphs of Hamming graphs and d-convexity,? Kibernetika, No. 1, 6?9 (1988). |
| [49] | A. A. Chernyak, ?On Little’s conjecture about planar graphs,? Izv. Akad. Nauk BSSR, Ser. Fiz.-Mat. Nauk, No. 2, 41?45 (1980). |
| [50] | S. V. Yushmanov, ?On a method of specifying graphs,? Vopr. Kibern. (Moscow), No. 64, 97?111 (1980). |
| [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). · Zbl 0485.05047 |
| [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). · Zbl 0561.05041 |
| [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). · Zbl 0662.05037 |
| [56] | N. Alon, ?Covering graphs by the minimum number of equivalence relations,? Combinatorica,6, No. 3, 201?206 (1986). · Zbl 0646.05053 · doi:10.1007/BF02579381 |
| [57] | I. Anderson, ?On the toroidal thickness of graphs,? J. Graph Theory,6, No. 2, 177?188 (1982). · Zbl 0487.05024 · doi:10.1002/jgt.3190060212 |
| [58] | Th. Andreae, ?On an extremal problem concerning the interval number of a graph,? Discrete Appl. Math.,14, No. 1, 1?9 (1986). · Zbl 0606.05034 · doi:10.1016/0166-218X(86)90002-8 |
| [59] | Th. Andreae, ?On the interval number of a triangulated graph,? J. Graph Theory,11, No. 3, 273?280 (1987). · Zbl 0652.05054 · doi:10.1002/jgt.3190110303 |
| [60] | M. E. Aragno, ?Sulla superiore immergibilita di particolari graphi,? Riv. Mat. Univ. Parma,12, 35?40 (1986). |
| [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). |
| [62] | C. Arbib, ?A polynomial characterization of some graph partitioning problems,? Inform. Process. Lett.,26, No. 5, 223?230 (1988). · Zbl 0654.68093 · doi:10.1016/0020-0190(88)90144-5 |
| [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). · Zbl 0578.05018 · doi:10.1016/0095-8956(85)90053-X |
| [64] | K. Asano, ?On the genus and thickness of graphs,? J. Combin. Theory,B43, No. 3, 287?292 (1987). · Zbl 0627.05022 · doi:10.1016/0095-8956(87)90004-9 |
| [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). · Zbl 0613.62083 · doi:10.1016/0196-8858(86)90038-2 |
| [66] | H.-J. Bandelt and H. M. Mulder, ?Distance-hereditary graphs,? J. Combin. Theory,B41, No. 2, 182?208 (1986). · Zbl 0605.05024 · doi:10.1016/0095-8956(86)90043-2 |
| [67] | H.-J. Bandelt and E. Wilkeit, ?Dwarf, brick and triangulation of the torus,? Discrete Math.,67, No. 1, 1?14 (1987). · Zbl 0634.05065 · doi:10.1016/0012-365X(87)90162-2 |
| [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). · doi:10.1016/0166-218X(88)90004-2 |
| [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). · doi:10.1109/TSE.1986.6312901 |
| [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). · Zbl 0625.05020 · doi:10.1137/0216061 |
| [71] | B. Becker and H. G. Osthof, ?Layouts with wires of balanced length,? Lect. Notes Comput. Sci.,182, 21?31 (1985). · Zbl 0567.94028 · doi:10.1007/BFb0023991 |
| [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). · Zbl 0644.05027 · doi:10.1016/0097-3165(88)90002-7 |
| [73] | C. Benzaken, P. L. Hammer, and D. de Werra, ?Split graphs of Dilworth number 2,? Discrete Math.,55, No. 2, 123?127 (1985). · Zbl 0573.05047 · doi:10.1016/0012-365X(85)90040-8 |
| [74] | A. A. Bertossi, ?Finding Hamiltonian circuits in proper interval graphs,? Inform. Process. Lett.,17, No. 2, 97?101 (1983). · Zbl 0512.68046 · doi:10.1016/0020-0190(83)90078-9 |
| [75] | A. A. Bertossi, ?Dominating sets for split and bipartite graphs,? Inform. Process. Lett.,19, No. 1, 37?40 (1984). · Zbl 0539.68058 · doi:10.1016/0020-0190(84)90126-1 |
| [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). · Zbl 0543.68052 |
| [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). · Zbl 0646.68085 · doi:10.1137/0217004 |
| [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). · Zbl 0611.05020 · doi:10.1007/BF02579385 |
| [80] | M. A. Bonuccelli, ?Dominanting sets and domatic number of circular arc graphs,? Discrete Appl. Math.,12, No. 3, 203?213 (1985). · Zbl 0579.05051 · doi:10.1016/0166-218X(85)90025-3 |
| [81] | K. S. Booth and J. H. Johnson, ?Dominanting sets in chordal graphs,? SIAM J. Comput.,11, No. 1, 191?199 (1982). · Zbl 0485.05055 · doi:10.1137/0211015 |
| [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). · Zbl 0367.68034 · doi:10.1016/S0022-0000(76)80045-1 |
| [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). |
| [85] | A. Bouchet, ?Reducing prime graphs and recognizing circle graphs,? Combinatorica,7, No. 3, 243?254 (1987). · Zbl 0666.05037 · doi:10.1007/BF02579301 |
| [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). |
| [88] | S. Bublitz, ?Decomposition of graphs and monotone formula size of homogeneous functions,? Acta Inform.,23, No. 6, 689?696 (1986). · Zbl 0585.05031 · doi:10.1007/BF00264314 |
| [89] | P. Buneman, ?The recovery of trees from measures of dissimilarity,? in: Mathematics in Archaeological and Historical Sciences, Edinburgh, University Press, 387?395 (1971). |
| [90] | P. Buneman, ?A note on the metric properties of trees,? J. Combin. Theory,B17, No. 1, 48?50 (1974). · Zbl 0286.05102 · doi:10.1016/0095-8956(74)90047-1 |
| [91] | P. Buneman, ?A characterization of rigid circuit graphs,? Discrete Math.,9, No. 3, 205?212 (1974). · Zbl 0288.05128 · doi:10.1016/0012-365X(74)90002-8 |
| [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). · doi:10.1109/TSMC.1980.4308390 |
| [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). · Zbl 0512.05023 · doi:10.1137/0604006 |
| [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). · Zbl 0576.05054 · doi:10.1137/0605034 |
| [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). · Zbl 0645.68073 · doi:10.1051/ita/1988220202451 |
| [96] | N. Chiba, K. Onoguchi, and T. Nishizeki, ?Drawing planar graphs nicely,? Acta inform.,22, 187?201 (1985). · Zbl 0545.68057 · doi:10.1007/BF00264230 |
| [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). · Zbl 0556.05023 |
| [98] | F. Y. Chin, ?Security in statistical databases for queries with small counts,? ACM Transaction on Database Systems,3, No. 1, 92?104 (1978). · doi:10.1145/320241.320250 |
| [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). · Zbl 0581.05030 · doi:10.1007/BF02582927 |
| [100] | H. Colonius and H. H. Schulze, ?Tree structures for proximity data,? Brit. J. Math. and Statist. Psychol.,34, 167?180 (1981). · Zbl 0472.62107 · doi:10.1111/j.2044-8317.1981.tb00626.x |
| [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). · Zbl 0524.05059 · doi:10.1016/0166-218X(83)90077-X |
| [102] | J. P. Cunningham, ?Free trees and bidirectional trees as representations of psychological distance,? J. Math. Psychol.,17, No. 2, 165?188 (1978). · Zbl 0383.94041 · doi:10.1016/0022-2496(78)90029-9 |
| [103] | W. H. Cunningham, ?Decomposition of directed graphs,? SIAM J. Algebraic Discrete Methods,3, No. 3, 214?228 (1982). · Zbl 0497.05031 · doi:10.1137/0603021 |
| [104] | D. Cvetkovic and I. Pevac, ?Man-machine theorem proving in graph theory,? Artif. Intell.,35, No. 1, 1?23 (1988). · Zbl 0646.68107 · doi:10.1016/0004-3702(88)90030-6 |
| [105] | P. Czerwinski and V. Ramachandran, ?Optimal VLSI graph embeddings in variable aspect ratio rectangles,? Algorithmica,3, No. 4, 487?510 (1988). · doi:10.1007/BF01762128 |
| [106] | H. De Fraysseix and P. Rosenstiehl, ?A depth-firat-search characterization of planarity,? Graph Theory, Amsterdam, 75?80 (1982). · Zbl 0497.05026 |
| [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). · Zbl 0643.68085 |
| [108] | G. Di Battista and R. Tamassia, ?Algorithms for plane representations of acyclic diagraphs,? Theoretical Computer Science,61, No. 2?3, 175?198 (1988). · Zbl 0678.68059 · doi:10.1016/0304-3975(88)90123-5 |
| [109] | R. Diestel, ?Simplicial decompositions of graphs ? some uniqueness results,? J. Combin. Theory,B42, No. 2, 133?145 (1987). · Zbl 0582.05045 · doi:10.1016/0095-8956(87)90035-9 |
| [110] | R. Diestel, ?Tree-decompositions, tree-representability, and chordal graphs,? Discrete Math.,71, No. 2, 181?184 (1988). · Zbl 0648.05047 · doi:10.1016/0012-365X(88)90071-4 |
| [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). · Zbl 0098.14703 · doi:10.1007/BF02992776 |
| [113] | D. Z. Djokovi?, ?Distance-preserving subgraphs of hypercubes,? J. Combin. Theory,B14, No. 3, 263?267 (1973). · Zbl 0245.05113 · doi:10.1016/0095-8956(73)90010-5 |
| [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). · Zbl 0562.54041 · doi:10.1016/0001-8708(84)90029-X |
| [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). · Zbl 0516.05023 · doi:10.1016/0012-365X(83)90128-0 |
| [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). · Zbl 0562.68030 · doi:10.1016/0166-218X(85)90008-3 |
| [117] | M. E. Dyer and A. M. Frieze, ?Planar 3DM is NP-complete,? J. Algorithms,7, No. 2, 174?184 (1986). · Zbl 0606.68065 · doi:10.1016/0196-6774(86)90002-7 |
| [118] | P. Eades and D. Kelly, ?Heuristics for reducing crossings in 2-layered networks,? Ars Combin.,21, No. 1, 89?98 (1986). |
| [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). · Zbl 0348.05113 · doi:10.1016/0095-8956(76)90022-8 |
| [121] | P. Erdös, R. Faudree, and E. T. Ordman, ?Clique partitions and clique coverings,? Discrete Math.,72, No. 1?3, 93?101 (1988). · Zbl 0679.05040 · doi:10.1016/0012-365X(88)90197-5 |
| [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). · Zbl 0576.05019 · doi:10.1016/0012-365X(85)90041-X |
| [123] | S. Even and A. Itai, ?Queues, stacks and graphs,? in: Theory of Machines and Computations, Acad. Press, N.Y., 71?80 (1971). |
| [124] | S. Even, A. Pnueli, and A. Lempel, ?Permutation graphs and transitive graphs,? J. Assoc. Comput. Mach.,19, No. 3, 400?410 (1972). · Zbl 0251.05113 · doi:10.1145/321707.321710 |
| [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). · Zbl 0579.68028 · doi:10.1016/0166-218X(85)90066-6 |
| [126] | R. B. Feinberg, ?The circular dimension of a graph,? Discrete Math.,25, No. 1, 27?31 (1979). · Zbl 0392.05057 · doi:10.1016/0012-365X(79)90149-3 |
| [127] | J. Felsenstein, ?Numerical methods for inferring evolutionary trees,? Quart. Rev. Biol.,57, No. 4, 379?404 (1982). · doi:10.1086/412935 |
| [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). · Zbl 0533.05055 · doi:10.1016/0095-8956(83)90057-6 |
| [130] | P. C. Fishburn, Interval orders and interval graphs: A study of partially ordered sets, New York (1985). · Zbl 0551.06001 |
| [131] | E. Flapan, ?Symmetries of knotted hypothetical molecular graphs,? Discrete Appl. Math.,19, No. 1?3, 157?166 (1988). · Zbl 0633.05066 · doi:10.1016/0166-218X(88)90011-X |
| [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. · Zbl 0407.05071 |
| [133] | J. C. Fourier, ?Une caracterization des graphs de cordes,? C. R. Acad. Sci. Paris,A286, 811?813 (1978). |
| [134] | P. Frankl and H. Maehara, ?On the contact dimensions of graphs,? Discrete Comput. Geom.,3, No. 1, 89?96 (1987). · Zbl 0625.05048 · doi:10.1007/BF02187899 |
| [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). · Zbl 0675.05049 · doi:10.1016/0095-8956(88)90043-3 |
| [136] | H. de Fraysseix, ?A characterization of circle graphs,? Eur. J. Comb.,5, No. 3, 223?238 (1984). · Zbl 0551.05056 · doi:10.1016/S0195-6698(84)80005-0 |
| [137] | L. C. Freeman, ?Spheres, cubes, and boxes: graph dimensionality and network structure,? Soc. Networks,5, No. 2, 139?156 (1983). · doi:10.1016/0378-8733(83)90022-9 |
| [138] | D. R. Fulkerson and O. A. Gross, ?Incidence matrices and interval graphs,? Pacif. J. Math.,15, 835?855 (1965). · Zbl 0132.21001 · doi:10.2140/pjm.1965.15.835 |
| [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). · Zbl 0633.05067 · doi:10.1016/0166-218X(88)90012-1 |
| [141] | M. R. Garey and D. S. Johnson, ?Crossing number is NP-complete,? SIAM J. Alg. Disc. Math.,4, No. 3, 312?316 (1983). · Zbl 0536.05016 · doi:10.1137/0604033 |
| [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). · Zbl 0499.05058 · doi:10.1137/0601025 |
| [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). · Zbl 0487.90054 · doi:10.1016/0167-6377(81)90018-3 |
| [144] | F. Gavril, ?Algorithms for a maximum clique and a maximum independent set of a circle graph,? Networks,3, 261?273 (1973). · Zbl 0259.05125 · doi:10.1002/net.3230030305 |
| [145] | F. Gavril, ?The intersection graphs of subtrees in trees are exactly the chordal graphs,? J. Combin. Theory,B16, No. 1, 47?56 (1974). · Zbl 0266.05101 · doi:10.1016/0095-8956(74)90094-X |
| [146] | F. Gavril, ?A recognition algorithm for the intersection graphs of directed paths in directed trees,? Discrete Math.,13, No. 3, 237?249 (1975). · Zbl 0312.05108 · doi:10.1016/0012-365X(75)90021-7 |
| [147] | F. Gavril, ?A recognition algorithm for the intersection graphs of paths in trees,? Discrete Math.,23, No. 3, 211?227 (1978). · doi:10.1016/0012-365X(78)90070-5 |
| [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). · Zbl 0121.26003 · doi:10.4153/CJM-1964-055-5 |
| [149] | J. Gimbel, ?End vertices in interval graphs,? Discrete Appl. Math.,21, No. 3, 257?259 (1988). · Zbl 0671.05035 · doi:10.1016/0166-218X(88)90071-6 |
| [150] | M. C. Golumbic, Algorithmic graph theory and perfect graphs, N. Y., Adad. Press, 1980. · Zbl 0541.05054 |
| [151] | M. C. Golumbic, ?Algorithmic aspects of intersection graphs and representation hypergraphs,? Graphs and Comb,4, No. 4, 307?327 (1988). · Zbl 0671.05034 · doi:10.1007/BF01864170 |
| [152] | M. C. Golumbic and P. L. Hammer, ?Stability in circular are graphs,? J. Algorithms,9, No. 3, 314?320 (1988). · Zbl 0651.68083 · doi:10.1016/0196-6774(88)90023-5 |
| [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). · Zbl 0537.05063 · doi:10.1016/0095-8956(85)90088-7 |
| [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). · Zbl 0568.05023 · doi:10.1016/0012-365X(85)90043-3 |
| [155] | M. C. Golumbic and C. L. Monma, ?A generalization of interval graphs with tolerances,? Congressus Numerantium35, 321?331 (1982). |
| [156] | M. C. Golumbic, C. L. Monma, and W. T. Trotter (Jr.), ?Tolerance graphs,? Discrete Appl. Math.,9, No. 2, 157?170 (1984). · Zbl 0547.05054 · doi:10.1016/0166-218X(84)90016-7 |
| [157] | M. C. Golumbic, D. Rotem, and J. Urrutia, ?Comparability graphs and intersection graphs,? Discrete Math.,43, No. 1, 37?46 (1983). · Zbl 0502.05050 · doi:10.1016/0012-365X(83)90019-5 |
| [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). · Zbl 0228.94020 · doi:10.1002/j.1538-7305.1971.tb02618.x |
| [159] | R. L. Graham and H. O. Pollak, ?On embedding graphs in squashed cubes,? Lect. Notes Math.,303, 99?110 (1972). · Zbl 0251.05123 · doi:10.1007/BFb0067362 |
| [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). · Zbl 0554.05057 · doi:10.1073/pnas.81.22.7259 |
| [161] | R. L. Graham and P. M. Winkler, ?On isometric embeddings of graphs,? Trans. Amer. Math. Soc,288, No. 2, 527?536 (1985). · Zbl 0576.05017 · doi:10.1090/S0002-9947-1985-0776391-5 |
| [162] | J. R. Griggs, ?Extremal values of the interval number of a graph. II,? Discrete Math.,28, No. 1, 37?47 (1979). · Zbl 0446.05027 · doi:10.1016/0012-365X(79)90183-3 |
| [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). · Zbl 0499.05033 · doi:10.1137/0601001 |
| [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). · Zbl 0493.68066 · doi:10.1002/net.3230120410 |
| [165] | S. E. Hambrusch and J. Simon, ?Solving undirected graph problems on VLSI,? SIAM J. Comput.,14, No. 3, 527?544 (1985). · Zbl 0565.68061 · doi:10.1137/0214040 |
| [166] | P. L. Hammer and B. Simeone, ?The splittance of a graph,? Combinatorica,1, No. 3, 275?284 (1981). · Zbl 0492.05043 · doi:10.1007/BF02579333 |
| [167] | F. Harary and F. Buckley, ?On the euclidean dimension of a wheel,? Graphs and Comb.,4, No. 1, 23?30 (1988). · Zbl 0642.05018 · doi:10.1007/BF01864150 |
| [168] | F. Harary, J. A. Kabell, and F. R. McMorris, ?Bipartite intersection graphs,? Comment. Math. Univ. Carol.,23, No. 4, 739?745 (1982). |
| [169] | F. Harary, R. A. Melter, and I. Tomescu, ?Digital metrics: A graph-theoretical approach,? Pattern Recogn. Lett.,2, No. 3, 159?163 (1984). · Zbl 0546.05058 · doi:10.1016/0167-8655(84)90040-0 |
| [170] | N. Hartsfield, ?The toroidal splitting number of the complete graph Kn,? Discrete Math.,62, 35?47 (1986). · Zbl 0598.05029 · doi:10.1016/0012-365X(86)90039-7 |
| [171] | N. Hartsfield, ?The splitting number of the complete graph in the projective plane,? Graphs and Comb.,3, No. 4, 349?356 (1987). · Zbl 0628.05027 · doi:10.1007/BF01788557 |
| [172] | N. Hartsfield, B. Jackson, and G. Ringel, ?The splitting number of the complete graph,? Graphs and Comb.,1, 311?329 (1985). · Zbl 0617.05027 · doi:10.1007/BF02582960 |
| [173] | T. E. Havel, The combinatorial distance geometry approach to the calculation of molecular conformation, Ph. D. Thesis, University of California, Berkeley, 1982. · Zbl 0516.05060 |
| [174] | F. Hoffmann and K. Kriegel, ?Embedding rectilinear graphs in linear time,? Inform. Process. Lett.,29, No. 2, 75?79 (1988). · Zbl 0658.68086 · doi:10.1016/0020-0190(88)90032-4 |
| [175] | P. Horák and J. Siran, ?On a modified concept of thickness of a graph,? Math. Nachr.,108, 305?306 (1982). · Zbl 0524.05046 · doi:10.1002/mana.19821080124 |
| [176] | E. Howe, C. R. Johnson, and J. Lawrece, ?The structure of distances in networks,? Networks,16, No. 1, 87?106 (1986). · Zbl 0653.05044 · doi:10.1002/net.3230160109 |
| [177] | E. Howorka, ?A characterization of Ptolemaic graphs,? J. Graph. Theory,5, No. 3, 323?331 (1981). · Zbl 0437.05046 · doi:10.1002/jgt.3190050314 |
| [178] | W.-L. Hsu, ?Maximum weight clique algorithms for circular-arc graphs and circle graphs,? SIAM J. Comput.,14, No. 1, 224?231 (1985). · Zbl 0567.68042 · doi:10.1137/0214018 |
| [179] | W.-L. Hsu, ?Recognizing planar perfect graphs,? J. Assoc. Comput. Mach.,34, No. 2, 255?288 (1987). · doi:10.1145/23005.31330 |
| [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). · Zbl 0285.92029 · doi:10.1111/j.2044-8317.1974.tb00534.x |
| [181] | J. P. Hutchinson, ?Automorphism properties of embedded graphs,? J. Graph Theory, No. 1, 35?49 (1984). · Zbl 0534.05029 · doi:10.1002/jgt.3190080105 |
| [182] | W. Imrich and G. Schwartz, ?Trees and length functions in groups,? Ann. Discrete Math.,17, 347?359 (1983). |
| [183] | X. Jin, ?Large processors are good in VLSI chips,? Inform. Process. Lett.,18, No. 1, 47?49 (1984). · Zbl 0526.94024 · doi:10.1016/0020-0190(84)90074-7 |
| [184] | D. S. Johnson, ?The NP-completeness column: an ongoing guide,? J. Algorithms.6, No. 3, 434?451 (1985). · Zbl 0608.68032 · doi:10.1016/0196-6774(85)90012-4 |
| [185] | A. D. Jovanovic, ?Combinatorial characterization of hexagonal systems,? Discrete Appl. Math.,19, No. 1?3, 259?270 (1988). · Zbl 0633.05068 · doi:10.1016/0166-218X(88)90018-2 |
| [186] | J. R. Jungch, G. Dick, and A. G. Dick, ?Computer-assisted sequencing, interval graphs, and molecular evolution,? Biosystems,15, 259?273 (1982). · doi:10.1016/0303-2647(82)90010-7 |
| [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). · Zbl 0655.05063 |
| [188] | D. Kelly, ?Fundamentals of planar ordered sets,? Discrete Math.,63, No. 2?3, 197?216 (1987). · Zbl 0609.06002 · doi:10.1016/0012-365X(87)90008-2 |
| [189] | D. G. Kendall, ?Some problems and methods in statistical archaeology,? World Archaeology,1, No. 1, 61?76 (1969). · doi:10.1080/00438243.1969.9979428 |
| [190] | S. Klavzar and M. Petkovsek, ?Intersection graphs of halflines and halfplanes,? Discrete Math.,66, No. 1?2, 133?137 (1987). · Zbl 0651.05059 · doi:10.1016/0012-365X(87)90126-9 |
| [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). · Zbl 0509.68061 |
| [192] | D. Kleitman and K. J. Winston, ?On the number of graphs without 4-cycles,? Discrete Math.,41, No. 2, 167?172 (1982). · Zbl 0491.05035 · doi:10.1016/0012-365X(82)90204-7 |
| [193] | P. Klenovcan, ?Direct product decompositions of diagraphs,? Math. Slov.,38, No. 1, 3?10 (1988). |
| [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). · Zbl 0367.68035 · doi:10.1145/359340.359346 |
| [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). · Zbl 0618.05019 · doi:10.1016/0012-365X(87)90105-1 |
| [197] | M. Leclerc, ?A graph-theoretical approach to a problem in circuit design,? Mitt. Math. Semin. Giessen., No. 175, 19?26 (1986). · Zbl 0608.94014 |
| [198] | F. T. Leighton, ?New lower bound techniques for VLSI,? Math. Syst. Theory,17, No. 1, 47?70 (1984). · Zbl 0488.94048 · doi:10.1007/BF01744433 |
| [199] | F. T. Leighton and A. L. Rosenberg, ?Three-dimensional circuit layouts,? SIAM J. Cornput.,15, No. 3, 793?813 (1986). · Zbl 0612.68063 · doi:10.1137/0215057 |
| [200] | E. Leiss, ?Data base security and the representation of graphs as query graphs,? Congressus Numerantium,33, 167?183 (1981). · Zbl 0491.68068 |
| [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). · Zbl 0105.17501 |
| [202] | N. Linial, L. Lovasz, and A. Wigderson, ?Rubber bands, convex embeddings, and graph connectivity,? Combinatorica,8, No. 1, 91?102 (1988). · Zbl 0674.05046 · doi:10.1007/BF02122557 |
| [203] | C. H. C. Little, ?On rings of circuits in planar graphs,? Lect. Notes Math.,622, 133?140 (1977). · doi:10.1007/BFb0069187 |
| [204] | L. Lovasz, ?Perfect graphs,? in: Selected Topics in Graph Theory 2, Acad. Press, N.Y., 55?87 (1983). |
| [205] | F. Luccio, S. Mazzone, and C. K. Wong, ?A note on visibility graphs,? Discrete Math.,64, No. 2?3, 209?219 (1987). · Zbl 0638.05050 · doi:10.1016/0012-365X(87)90190-7 |
| [206] | C. Maas, ?Some results about the interval numbers of a graph,? Discrete Appl. Math.,6, No. 1, 99?102 (1983). · Zbl 0531.05054 · doi:10.1016/0166-218X(83)90106-3 |
| [207] | C. Maas, ?Determining the interval number of triangle-free graph,? Computing,31, No. 4, 347?354 (1983). · Zbl 0516.05058 · doi:10.1007/BF02251237 |
| [208] | H. Maehara, ?On time graphs,? Discrete Math.,32, No. 3, 281?289 (1980). · Zbl 0454.05037 · doi:10.1016/0012-365X(80)90266-6 |
| [209] | H. Maehara, ?Space graphs and sphericity,? Discrete Appl. Math.,7, No. 1, 55?64 (1984). · Zbl 0527.05028 · doi:10.1016/0166-218X(84)90113-6 |
| [210] | H. Maehara, ?A digraph represented by a family of boxes or spheres,? J. Graph Theory,8, No. 3, 431?439 (1984). · Zbl 0552.05030 · doi:10.1002/jgt.3190080312 |
| [211] | H. Maehara, ?Sphericity exceeds cubicity for almost all complete bipartite graphs,? J. Combin. Theory,B40, No. 2, 231?235 (1986). · Zbl 0595.05031 · doi:10.1016/0095-8956(86)90081-X |
| [212] | H. Maehara, ?On the euclidean dimension of a complete multipartite graph,? Discrete Math.,72, No.1?3, 285?289 (1988). · Zbl 0657.05022 · doi:10.1016/0012-365X(88)90217-8 |
| [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). · Zbl 0639.05017 · doi:10.1007/BF01864152 |
| [214] | N. V. R. Mahadev and U. N. Peled, ?Strict 2-threshold graphs,? Discrete Appl. Math.,21, No. 2, 113?131 (1988). · Zbl 0658.05063 · doi:10.1016/0166-218X(88)90048-0 |
| [215] | M. May and K. Szkatula, ?On the bipartite crossing number,? Contr. and Cybern.,17, No. 1, 85?98 (1988). |
| [216] | F. R. McMorris and D. R. Shier, ?Representing chordal graphs on K1,n,? Comment. Math. Univ. Carol.,24, No. 3, 489?494 (1983). · Zbl 0536.05054 |
| [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). · Zbl 0607.05028 · doi:10.1016/0022-0000(86)90030-9 |
| [218] | G. L. Miller, ?An additivity theorem for the genus of a graph,? J. Combin. Theory,B43, No. 1, 25?47 (1987). · Zbl 0618.05020 · doi:10.1016/0095-8956(87)90028-1 |
| [219] | B. Mohar, ?Embeddings of infinite graphs,? J. Combin. Theory,44, No. 1, 29?43 (1988). · Zbl 0591.05028 · doi:10.1016/0095-8956(88)90094-9 |
| [220] | B. Mohar, ?Nonorientable genus of nearly complete bipartite graphs,? Discrete and Comput. Geom.,3, No. 2, 137?146 (1988). · Zbl 0628.05026 · doi:10.1007/BF02187903 |
| [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). · Zbl 0657.68034 · doi:10.1016/0304-3975(88)90028-X |
| [222] | C. L. Monma and V. K. Wei, ?Intersection graphs of paths in a tree,? J. Combin. Theory,B41, No. 2, 141?181 (1986). · Zbl 0595.05062 · doi:10.1016/0095-8956(86)90042-0 |
| [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). · Zbl 0653.05028 |
| [224] | W. Naji, ?Reconnaissance des graphes de cordes,? Discrete Math.,54, No. 3, 329?337 (1985). · Zbl 0567.05033 · doi:10.1016/0012-365X(85)90117-7 |
| [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). · Zbl 0508.05033 · doi:10.1016/0012-365X(83)90057-2 |
| [227] | S. Negami, ?Uniquely and faithfully embeddable projective-planar triangulations,? J. Combin. Theory,B36, No. 2, 189?193 (1984). · Zbl 0518.05030 · doi:10.1016/0095-8956(84)90024-8 |
| [228] | S. Negami, ?Enumeration of projective-planar embeddings of graphs,? Discrete Math.,62, No. 3, 299?306 (1986). · Zbl 0611.05019 · doi:10.1016/0012-365X(86)90217-7 |
| [229] | S. Negami, ?Re-embedding of projective-planar graphs,? J. Combin. Theory,B44, No. 3, 276?299 (1988). · Zbl 0609.05033 · doi:10.1016/0095-8956(88)90037-8 |
| [230] | S. Negami, ?The spherical genus and virtually planar graphs,? Discrete Math.,70, No. 2, 159?168 (1988). · Zbl 0656.05031 · doi:10.1016/0012-365X(88)90090-8 |
| [231] | J. Nesetril and R. Thomas, ?A note on spatial representation of graphs,? Comment. Math. Univ. Carol.,26, No. 4, 655?659 (1985). |
| [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. · Zbl 0471.05032 |
| [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). · Zbl 0528.90085 · doi:10.1002/net.3230130301 |
| [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). · Zbl 0496.68047 · doi:10.1137/0602012 |
| [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). · Zbl 0548.05027 · doi:10.1016/0012-365X(84)90005-0 |
| [237] | T. D. Parsons, G. Pica, T. Pisanski, and A. G. S. Ventre, ?Orientably simple graphs,? Math. Slov.,37, No. 4, 391?394 (1987). · Zbl 0643.05027 |
| [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). · Zbl 0533.05049 · doi:10.1016/0012-365X(84)90174-2 |
| [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). · Zbl 0465.05030 · doi:10.1002/jgt.3190060403 |
| [243] | M. D. Plummer, ?Matching extension and the genus of a graph,? J. Combin. Theory,B44 No. 3, 329?337 (1988). · Zbl 0653.05054 · doi:10.1016/0095-8956(88)90041-X |
| [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). · Zbl 0204.24604 · doi:10.4153/CJM-1971-016-5 |
| [245] | S. Poljak, V. Rödl, and D. Turzik, ?Complexity of representation of graphs by set systems,? Discrete Appl. Math.,3, 301?312 (1981). · Zbl 0473.68064 · doi:10.1016/0166-218X(81)90007-X |
| [246] | R. Raghavan, J. Cohoon, and S. Sahni, ?Single bend wiring,? J. Algorithms,7, No. 2, 232?257 (1986). · Zbl 0606.94019 · doi:10.1016/0196-6774(86)90006-4 |
| [247] | I. V. Ramakrishnan and P. J. Varman, ?On mapping cube graphs onto VLSI arrays,? Lect. Notes Comput. Sci.,181, 296?316 (1984). · Zbl 0574.68023 · doi:10.1007/3-540-13883-8_79 |
| [248] | R. C. Read, D. Rotem, and J. Urrutia, ?Orientations of circle graphs,? J. Graph Theory,6, No. 3, 325?341 (1982). · Zbl 0494.05025 · doi:10.1002/jgt.3190060309 |
| [249] | P. L. Renz, ?Intersection representations of graphs by arcs,? Pacif. J. Math.,34, No. 2, 501?510 (1970). · Zbl 0191.55103 · doi:10.2140/pjm.1970.34.501 |
| [250] | R. B. Richter, ?On the nonorientable genus of a 2-connected graph,? J. Combin. Theory,B43, No. 1, 48?59 (1987). · Zbl 0591.05026 · doi:10.1016/0095-8956(87)90029-3 |
| [251] | R. B. Richter, ?On the Eulerian genus of a 2-connected graph,? J. Combin. Theory,B43, No. 1, 60?69 (1987). · Zbl 0591.05025 · doi:10.1016/0095-8956(87)90030-X |
| [252] | R. B. Richter and H. Shank, ?The cycle space of an embedded graph,? J. Graph Theory,8, No. 3, 365?369 (1984). · Zbl 0547.05028 · doi:10.1002/jgt.3190080304 |
| [253] | F. S. Roberts, ?Indifference graphs,? in: Proof Techn. Graph Theory, N.Y., Acad. Press, 1969, 139?146. |
| [254] | F. S. Roberts, ?On the boxicity and cubicity of a graph,? in: Recent Progr. in Combinator., N.Y., Acad. Press, 1969, 301?310. · Zbl 0193.24301 |
| [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. · Zbl 0389.90036 |
| [256] | F. S. Roberts, ?Applications of edge coverings by cliques,? Discrete Appl. Math.,10, No. 1, 93?109 (1985). · Zbl 0558.05046 · doi:10.1016/0166-218X(85)90061-7 |
| [257] | N. Robertson and P. D. Seymour, ?Graph minors. VI. Disjoint paths across a disc,? J. Combin. Theory,B41, No. 1, 115?138 (1986). · Zbl 0598.05042 · doi:10.1016/0095-8956(86)90031-6 |
| [258] | N. Robertson and P. D. Seymour, ?Graph minors. VII. Disjoint paths on a surface,? J. Combin. Theory,B45, No. 2, 212?254 (1988). · Zbl 0658.05044 · doi:10.1016/0095-8956(88)90070-6 |
| [259] | P. Rosenstiehl and R. E. Tarjan, ?Gauss codes, planar Hamiltonian graphs, and stack-sortable permutations,? J. Algorithms,5, No. 3, 375?390 (1984). · Zbl 0588.68034 · doi:10.1016/0196-6774(84)90018-X |
| [260] | P. Rosenstiehl and R. E. Tarjan, ?Rectilinear planar layouts of planar graphs and bi-polar orientations,? Discrete & Comput. Geom.,1, 342?351 (1986). · Zbl 0607.05027 |
| [261] | D. Rotem and J. Urrutia, ?Circular permutation graphs,? Networks,12, No. 4, 429?437 (1982). · Zbl 0508.05060 · doi:10.1002/net.3230120407 |
| [262] | Ryu Hae Dong and Li Chong I, ?The study on the maximum genus of graphs,? Suhak, No. 3, 13?16 (1986). |
| [263] | H. Sachs, ?On a spatial analogue of Kuratowski’s theorem on planar graphs ? an open problem,? Lect. Notes Math.,1018, 230?241 (1983). · Zbl 0525.05024 · doi:10.1007/BFb0071633 |
| [264] | S. Sattath and A. Tversky, ?Additive similarity trees,? Psychometrica,42, No. 3, 319?345 (1977). · doi:10.1007/BF02293654 |
| [265] | E. R. Scheinerman, ?Characterizing intersection classes of graphs,? Discrete Math.,55, No. 2, 185?193 (1985). · Zbl 0597.05056 · doi:10.1016/0012-365X(85)90047-0 |
| [266] | E. R. Scheinerman, ?Irrepresentability by multiple intersection, or why the interval number is unbounded,? Discrete Math.,55, No. 2, 195?211 (1985). · Zbl 0576.05030 · doi:10.1016/0012-365X(85)90048-2 |
| [267] | E. R. Scheinerman, ?Irredundancy in multiple interval representations,? Discrete Math.,63, No. 1, 101?108 (1987). · Zbl 0624.05060 · doi:10.1016/0012-365X(87)90157-9 |
| [268] | E. R. Scheinerman, ?The maximum interval number of graphs with given genus,? J. Graph Theory,11, No. 3, 441?446 (1987). · Zbl 0652.05026 · doi:10.1002/jgt.3190110317 |
| [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). · Zbl 0528.05053 · doi:10.1016/0095-8956(83)90050-3 |
| [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. |
| [271] | F. Scotti, ?II complementare di un grafo non superiormente immergibile é superiormente immergibile,? Boll. Unione mat. ital.,A3, No. 1, 111?118 (1984). |
| [272] | J. Sedlacek, ?O jednom zobeeneni vnejskove rivinnych grafu,? Cas. pestov. mat.,113, No. 2, 213?218 (1988). |
| [273] | Shaohan Majand W. D. Wallis, ?Maximal-clique partitions of interval graphs,? J. Austral Math. Soc. A,45, No. 2, 227?232 (1988). · doi:10.1017/S1446788700030147 |
| [274] | J. B. Shearer, ?A note on circular dimension,? Discrete Math.,29, No. 1, 103 (1980). · Zbl 0437.05049 · doi:10.1016/0012-365X(90)90290-X |
| [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). · Zbl 0637.68076 · doi:10.1016/0020-0190(87)90038-X |
| [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. |
| [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). · Zbl 0177.26903 · doi:10.1016/S0021-9800(69)80092-X |
| [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). · Zbl 0535.05025 · doi:10.1016/0095-8956(83)90064-3 |
| [280] | J. Sirán, ?Edges and Kuratowski subgraphs of nonplanar graphs,? Math. Nachr.,113, 187?190 (1983). · Zbl 0539.05028 · doi:10.1002/mana.19831130118 |
| [281] | J. Sirá? and P. Horak, ?A construction of thickness-minimal graphs,? Discrete Math.,64, No. 2?3, 263?268 (1987). · Zbl 0614.05022 · doi:10.1016/0012-365X(87)90195-6 |
| [282] | J. Sirá? and M. Skoviera, ?Relative embeddings of graphs on closed surfaces,? Math. Nachr.,136, 275?284 (1988). · Zbl 0646.05024 · doi:10.1002/mana.19881360120 |
| [283] | J. Sirá? and M. ?koviera, ?Oriented relative embeddings of graphs,? Zastos. mat.,19, No. 3?4, 589?597 (1987). |
| [284] | D. Skrien, ?Chronological orderings of interval graphs,? Discrete Appl. Math.,8, No. 1, 69?83 (1984). · Zbl 0543.05059 · doi:10.1016/0166-218X(84)90080-5 |
| [285] | D. Skrien and J. Gimbel, ?Homogeneously representable interval graphs,? Discrete Math.,55, No. 2, 213?216 (1985). · Zbl 0579.05054 · doi:10.1016/0012-365X(85)90049-4 |
| [286] | J. Spinrad, ?On comparability and permutation graphs,? SIAM J. Comput.,14, No. 3, 658?670 (1985). · Zbl 0568.68051 · doi:10.1137/0214048 |
| [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). · Zbl 0653.05058 · doi:10.1002/jgt.3190110318 |
| [288] | F. W. Stahl, ?Circular genetic maps,? J. Cell Physiol.,70, No. 1, 1?12 (1967). · doi:10.1002/jcp.1040700403 |
| [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). |
| [290] | J. E. Steif, ?The frame dimension and the complete overlap dimension of a graph,? J. Graph Theory,9, No. 2, 285?299 (1985). · Zbl 0582.05053 · doi:10.1002/jgt.3190090210 |
| [291] | K. E. Stoffers, ?Scheduling of traffic lights ? a new approach,? Transp. Res.,2, 199?234 (1968). · doi:10.1016/0041-1647(68)90016-6 |
| [292] | J. A. Storer, ?On minimal node-cost planar embeddings,? Networks,14, 181?212 (1984). · Zbl 0546.94033 · doi:10.1002/net.3230140202 |
| [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). · doi:10.1109/TSMC.1981.4308636 |
| [295] | M. M. Syslo, ?Triangulated edge intersection graphs of paths in a tree,? Discrete Math.,55, No. 2, 217?220 (1985). · Zbl 0569.05045 · doi:10.1016/0012-365X(85)90050-0 |
| [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). · Zbl 0654.68090 · doi:10.1137/0216030 |
| [297] | R. Tamassia and I. G. Tollis, ?A unified approach to visibility representations of planar graphs,? Discrete Comput. Geom.,1, 321?341 (1986). · Zbl 0607.05026 · doi:10.1007/BF02187705 |
| [298] | R. E. Tarjan, ?Decomposition by clique separators,? Discrete Math.,55, No. 2, 221?231 (1985). · Zbl 0572.05039 · doi:10.1016/0012-365X(85)90051-2 |
| [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). · Zbl 0545.68062 · doi:10.1137/0213035 |
| [300] | C. Thomassen, ?Plane representations of graphs,? in: Progress in Graph Theory, Academic Press, N.Y., 1984, 43?69. |
| [301] | C. Thomassen, ?Planarity and duality of finite and infinite graphs,? J. Combin. Theory,B29, No. 2, 244?271 (1980). · Zbl 0441.05023 · doi:10.1016/0095-8956(80)90083-0 |
| [302] | C. Thomassen, ?Interval representations of planar graphs,? J. Combin. Theory,B40, No. 1, 9?20 (1986). · Zbl 0595.05027 · doi:10.1016/0095-8956(86)90061-4 |
| [303] | W. T. Trotter (Jr.), ?A characterization of Roberts’ inequality for boxity,? Discrete Math.,28, No. 3, 303?313 (1979). · Zbl 0421.05062 · doi:10.1016/0012-365X(79)90137-7 |
| [304] | W. T. Trotter (Jr.) and F. Harary, ?On double and multiple interval graphs,? J. Graph Theory,3, No. 3, 205?211 (1979). · Zbl 0417.05050 · doi:10.1002/jgt.3190030302 |
| [305] | W. T. Trotter (Jr.) and D. B. West, ?Poset boxicity of graphs,? Discrete Math.,64, No. 1, 105?107 (1987). · Zbl 0646.05064 · doi:10.1016/0012-365X(87)90247-0 |
| [306] | A. Tucker, ?Matrix characterizations of circular-arc graphs,? Pacif. J. Math.,39, No. 2, 535?545 (1971). · Zbl 0226.05125 · doi:10.2140/pjm.1971.39.535 |
| [307] | A. Tucker, ?Structure theorems for some circular-arc graphs,? Discrete Math.,7, No. 1?2, 167?195 (1974). · Zbl 0269.05119 · doi:10.1016/S0012-365X(74)80027-0 |
| [308] | A. Tucker, ?Circular arc graphs: new uses and new algorithm,? Lect. Notes Math., No. 642, 580?589 (1978). · doi:10.1007/BFb0070412 |
| [309] | A. Tucker, ?An efficient test for circular-arc graphs,? SIAM J. Comput.,9, No. 1, 1?24 (1980). · Zbl 0453.05054 · doi:10.1137/0209001 |
| [310] | W. T. Tutte, ?Convex representations of graphs,? Proc. London Math. Soc.,10, No. 38, 304?320 (1960). · Zbl 0094.36301 · doi:10.1112/plms/s3-10.1.304 |
| [311] | M. Veldhorst, ?The optimal representation of disjoint iso-oriented rectangles in two-dimensional trees,? J. Algorithms,7, No. 1, 1?34 (1986). · Zbl 0597.68053 · doi:10.1016/0196-6774(86)90036-2 |
| [312] | H.-J. Voss, ?Note on a paper of McMorris and Shier,? Comment. Math. Univ. Carol.,26, No. 2, 319?322 (1985). · Zbl 0569.05047 |
| [313] | J. R. Walter, ?Representations of chordal graphs as subtrees of a tree,? J. Graph. Theory,2, No. 3, 265?267 (1978). · Zbl 0441.05022 · doi:10.1002/jgt.3190020311 |
| [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). · Zbl 0367.93004 |
| [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). · Zbl 0573.68036 · doi:10.1016/0020-0190(85)90044-4 |
| [318] | W. Wessel, ?Chord graphs ? new means for representing graphs,? Zastos, Mat.,19, No. 3?4, 619?627 (1987). · Zbl 0726.05057 |
| [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). |
| [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). · Zbl 0554.68041 · doi:10.1016/0166-218X(84)90127-6 |
| [321] | K. White, M. Farber, and W. Pulleyblank, ?Steiner trees, connected domination and strongly chordal graphs,? Networks,15, No. 1, 109?124 (1985). · Zbl 0579.05050 · doi:10.1002/net.3230150109 |
| [322] | H. S. Wilf, ?Finite lists of obstructions,? Amer. Math. Mon.,94, No. 3, 267?271 (1987). · Zbl 0622.05019 · doi:10.2307/2323393 |
| [323] | P. M. Winkler, ?Proof of the squashed cube conjecture,? Combinatorica,3, No. 1, 135?139 (1983). · Zbl 0522.05064 · doi:10.1007/BF02579350 |
| [324] | P. M. Winkler, ?Isometric embedding in products of complete graphs,? Discrete Appl. Math.,7, No. 2, 221?225 (1984). · Zbl 0529.05055 · doi:10.1016/0166-218X(84)90069-6 |
| [325] | P. M. Winkler, ?Every connected graph is a query graph,? J. Combinatorics, Inf. and Syst. Sci.,10, No. 1?2, 1?4 (1985). · Zbl 0636.05046 |
| [326] | P. M. Winkler, ?The metric structure of graphs: theory and applications,? London Math. Soc. Lect. Note Ser., No. 123, 197?221 (1987). |
| [327] | H. S. Witsenhausen, ?On intersections of interval graphs,? Discrete Math.,31, No. 2, 211?216 (1980). · Zbl 0443.05061 · doi:10.1016/0012-365X(80)90038-2 |
| [328] | H. S. Witsenhausen, ?Minimum dimension embedding of finite metric spaces,? J. Combin. Theory,A42, No. 4, 184?199 (1986). · Zbl 0594.05024 · doi:10.1016/0097-3165(86)90089-0 |
| [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). · Zbl 0147.22405 · doi:10.1016/S1385-7258(67)50022-7 |
| [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). |
| [332] | V. Zeleznik, ?Quadrilateral embeddings of the conjunction of graphs,? Math. Slov.,38, No. 2, 89?98 (1988). |
| [333] | T. P. Zivkovic, ?Graphical representation of regular resonance structures and their linear dependence,? Discrete Appl. Math.,19, No. 1?3, 397?414 (1988). · doi:10.1016/0166-218X(88)90027-3 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
