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.
Similar content being viewed by others
Literature cited
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).
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).
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).
I. M. Asel'derova, “On optimal encoding of some arithmetical graphs,” in: Theory of Optimization of Decisions [in Russian], Kiev (1987), pp. 47–54.
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.
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.
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.
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.
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).
Yu. G. Grigor'yan and G. K. Manoyan, “Some questions of arithmetical interpretation of undirected graphs,” Kibernetika, No. 3, 129–131 (1977).
G. A. Donets, “On analytically specified graphs,” in: Theory of Optimization of Decisions [in Russian], Kiev (1987), pp. 20–27.
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).
V. A. Evstigneev, Programming Applications of Graph Theory [in Russian], Nauka, Moscow (1985).
K. A. Zaretskii, “Construction of a Tree Given the Set of Distances Between Its Leaves,” Usp. Mat. Nauk,20, No. 6, 90–92 (1965).
A. A. Zykov, Elements of Graph Theory [in Russian], Nauka, Moscow (1987).
A. V. Ivashchenko, “Geometrical Representation of a Graph,” Kibernetika, No. 5, 120–121 (1988).
V. B. Kalinin, “On a problem of Berge,” Mat. Zametki,34, No. 1, 131–133 (1983).
V. Yu. Kayurov, “An algebraic interpretation of P-graphs,” Kibernetika, No. 5, 17–21 (1986).
A. K. Kel'mans, “Design, reconstruction, and embedding of graphs,” Preprint, Inst. Probl. Upr., Moscow (1987).
V. P. Kozyrev, “Graph theory,” Itogi Nauki i Tekhniki. VINITI. Teor. Veroyatn., Mat. Stat., Teor. Kibern.,10, 25–74 (1972).
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).
V. P. Kozyrev, “Determination of skeleton trees which are optimal with respect to several ranked criteria,” Kombinator. Analiz, No. 7, 66–74 (1986).
V. P. Kozyrev and A. D. Korshunov, “On the size of a cut in a random graph,” Probl. Kibern., No. 29, 27–62 (1974).
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.
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).
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).
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.
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.
A. Matuzyavichyus and A. Mitashyunas, “Machine routing of one-sided printed plates,” Prepr. Ernst-Moritz-Arndt Univ. Greifswald, Math., No. 18, 46–49 (1987).
E. V. Mzhel'skaya, “Graphs of polycyclic connections,” Vychisl. Sistemy, No. 119, 71–90 (1987).
V. G. Mirkin and S. N. Rodin, Graphs and Genes [in Russian], Nauka, Moscow (1977).
V. P. Nekrasov, “On plane graphs having external access,” in: Combinatorical Properties of Convex Sets and Graphs, Sverdlovsk (1983), pp. 34–44.
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.
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.
A. V. Petrosyan, S. E. Markosyan, and Yu. G. Shukuryan, Mathematical Questions of Computer Design Automation [in Russian], Erevan (1977).
N. S. Zefirov and S. I. Kuchanov (eds.), Application of Graph Theory in Chemistry [in Russian], Nauka, Novosibirsk (1988).
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).
F. S. Roberts, Discrete Mathematical Models with Applications to Social, Biological, and Economic Problems [Russian translation], Nauka, Moscow (1986).
E. A. Smolenskii, “On a method for linear recording of graphs,” Zh. Vychisl. Mat. Mat. Fiz.,2, 371–372 (1962).
V. P. Soltan, “d-convexity in graphs,” Dokl. Akad. Nauk SSSR,272, No. 3, 535–537 (1983).
I. V. Stankevich, “Graphs in structural chemistry,” in: Application of Graph Theory in Chemistry [in Russian], Novosibirsk (1988), pp. 7–69.
R. I. Tyshkevich and A. A. Chernyak, “Unigraphs. I,” Izv. Akad. Nauk BSSR, Ser. Fiz. Mat. Nauk, No. 5, 5–11 (1978).
R. I. Tyshkevich, O. I. Mel'nikov, and V. M. Kotov, “On graphs and power sequences,” Kibernetika, No. 6, 5–8 (1981).
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.
I. S. Filotti, “An embedding algorithm for a cubic graph,” Kibernet. Sbornik (Moscow), No. 23, 5–30 (1986).
V. V. Firsov, “Isometric embedding of graphs in a Boolean cube,” Kibernetika, No. 1 (1965), pp. 95–96.
V. D. Chepoi, “Some properties of d-convexity in triangulated graphs,” Mat. Issled., No. 87, 164–171 (1986).
V. D. Chepoi, “Isometric subgraphs of Hamming graphs and d-convexity,” Kibernetika, No. 1, 6–9 (1988).
A. A. Chernyak, “On Little's conjecture about planar graphs,” Izv. Akad. Nauk BSSR, Ser. Fiz.-Mat. Nauk, No. 2, 41–45 (1980).
S. V. Yushmanov, “On a method of specifying graphs,” Vopr. Kibern. (Moscow), No. 64, 97–111 (1980).
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).
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).
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.
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.
S. V. Yushmanov, “On metric properties of chordal and Ptolemaic graphs,” Dokl. Akad. Nauk SSSR,300, No. 2, 296–299 (1987).
N. Alon, “Covering graphs by the minimum number of equivalence relations,” Combinatorica,6, No. 3, 201–206 (1986).
I. Anderson, “On the toroidal thickness of graphs,” J. Graph Theory,6, No. 2, 177–188 (1982).
Th. Andreae, “On an extremal problem concerning the interval number of a graph,” Discrete Appl. Math.,14, No. 1, 1–9 (1986).
Th. Andreae, “On the interval number of a triangulated graph,” J. Graph Theory,11, No. 3, 273–280 (1987).
M. E. Aragno, “Sulla superiore immergibilita di particolari graphi,” Riv. Mat. Univ. Parma,12, 35–40 (1986).
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).
C. Arbib, “A polynomial characterization of some graph partitioning problems,” Inform. Process. Lett.,26, No. 5, 223–230 (1988).
D. S. Archdeacon and P. Huneke, “On cubic graphs which are irreducible for nonorientable surfaces,” J. Combin. Theory,B39, No. 3, 233–264 (1985).
K. Asano, “On the genus and thickness of graphs,” J. Combin. Theory,B43, No. 3, 287–292 (1987).
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).
H.-J. Bandelt and H. M. Mulder, “Distance-hereditary graphs,” J. Combin. Theory,B41, No. 2, 182–208 (1986).
H.-J. Bandelt and E. Wilkeit, “Dwarf, brick and triangulation of the torus,” Discrete Math.,67, No. 1, 1–14 (1987).
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).
C. Batini, E. Nardelli, and R. Tamassia, “A layout algorithm for data flow diagrams,” IEEE Trans. Software Eng.,12, No. 4, 538–546 (1986).
B. Becker and G. Holtz, “On the optimal layout of planar graphs with fixed boundary,” SIAM J. Comput.,16, No. 5, 946–972 (1987).
B. Becker and H. G. Osthof, “Layouts with wires of balanced length,” Lect. Notes Comput. Sci.,182, 21–31 (1985).
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).
C. Benzaken, P. L. Hammer, and D. de Werra, “Split graphs of Dilworth number 2,” Discrete Math.,55, No. 2, 123–127 (1985).
A. A. Bertossi, “Finding Hamiltonian circuits in proper interval graphs,” Inform. Process. Lett.,17, No. 2, 97–101 (1983).
A. A. Bertossi, “Dominating sets for split and bipartite graphs,” Inform. Process. Lett.,19, No. 1, 37–40 (1984).
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).
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).
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).
R. Bodendiek and K. Wagner, “A characterization of the minimal basis of the torus,” Combinatorica.6, No. 3, 245–260 (1986).
M. A. Bonuccelli, “Dominanting sets and domatic number of circular arc graphs,” Discrete Appl. Math.,12, No. 3, 203–213 (1985).
K. S. Booth and J. H. Johnson, “Dominanting sets in chordal graphs,” SIAM J. Comput.,11, No. 1, 191–199 (1982).
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).
A. Bouchet, “Characterizing and recognizing circle graphs,” Graph Theory, Proc. 6th Yugosl. Semin., Dubrovnik, April 18–19, 1985, Novi Sad, 57–69 (1986).
A. Bouchet, “Un algorithme polynomial pour reconnaitre les graphes d'alternance,” C. R. Acad. Sci., sér. 1,300, No. 16, 569–572 (1985).
A. Bouchet, “Reducing prime graphs and recognizing circle graphs,” Combinatorica,7, No. 3, 243–254 (1987).
A. Brandstädt, “Characterizations of split permutation graphs,” Algebra und Graphentheor. Beitr. Jahrestag, Siebenlehn, Oct. 28–Nov. 1, 1985, Freiberg, 21–24 (1986).
N. Breier, “Pattiell-rekursive Graphwortfunktionen,” J. Inf. Process. and Cybern. EIK.,23, No. 4–5, 171–179 (1987).
S. Bublitz, “Decomposition of graphs and monotone formula size of homogeneous functions,” Acta Inform.,23, No. 6, 689–696 (1986).
P. Buneman, “The recovery of trees from measures of dissimilarity,” in: Mathematics in Archaeological and Historical Sciences, Edinburgh, University Press, 387–395 (1971).
P. Buneman, “A note on the metric properties of trees,” J. Combin. Theory,B17, No. 1, 48–50 (1974).
P. Buneman, “A characterization of rigid circuit graphs,” Discrete Math.,9, No. 3, 205–212 (1974).
M. Carpano, “Automatic display of hierarchized graphs for computer-aided decision analysis,” IEEE Trans. Syst., Man, and Cybern.,10, No. 11, 705–715 (1980).
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).
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).
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).
N. Chiba, K. Onoguchi, and T. Nishizeki, “Drawing planar graphs nicely,” Acta inform.,22, 187–201 (1985).
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).
F. Y. Chin, “Security in statistical databases for queries with small counts,” ACM Transaction on Database Systems,3, No. 1, 92–104 (1978).
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).
H. Colonius and H. H. Schulze, “Tree structures for proximity data,” Brit. J. Math. and Statist. Psychol.,34, 167–180 (1981).
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).
J. P. Cunningham, “Free trees and bidirectional trees as representations of psychological distance,” J. Math. Psychol.,17, No. 2, 165–188 (1978).
W. H. Cunningham, “Decomposition of directed graphs,” SIAM J. Algebraic Discrete Methods,3, No. 3, 214–228 (1982).
D. Cvetkovic and I. Pevac, “Man-machine theorem proving in graph theory,” Artif. Intell.,35, No. 1, 1–23 (1988).
P. Czerwinski and V. Ramachandran, “Optimal VLSI graph embeddings in variable aspect ratio rectangles,” Algorithmica,3, No. 4, 487–510 (1988).
H. De Fraysseix and P. Rosenstiehl, “A depth-firat-search characterization of planarity,” Graph Theory, Amsterdam, 75–80 (1982).
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).
G. Di Battista and R. Tamassia, “Algorithms for plane representations of acyclic diagraphs,” Theoretical Computer Science,61, No. 2–3, 175–198 (1988).
R. Diestel, “Simplicial decompositions of graphs — some uniqueness results,” J. Combin. Theory,B42, No. 2, 133–145 (1987).
R. Diestel, “Tree-decompositions, tree-representability, and chordal graphs,” Discrete Math.,71, No. 2, 181–184 (1988).
P. F. Dietz, “Intersection graph algorithms,” Ph. D. Thesis, Cornell University, 1984.
G. A. Dirac, “On rigid circuit graphs,” Abh. Math. Semin. Univ. Hamburg,25, No. 1–2, 71–76 (1961).
D. Z. Djoković, “Distance-preserving subgraphs of hypercubes,” J. Combin. Theory,B14, No. 3, 263–267 (1973).
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).
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).
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).
M. E. Dyer and A. M. Frieze, “Planar 3DM is NP-complete,” J. Algorithms,7, No. 2, 174–184 (1986).
P. Eades and D. Kelly, “Heuristics for reducing crossings in 2-layered networks,” Ars Combin.,21, No. 1, 89–98 (1986).
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.
G. Ehrlich, S. Even, and R. E. Tarjan, “Intersection graphs of curves in the plane,” J. Combin. Theory,B21, No. 1, 8–20 (1976).
P. Erdös, R. Faudree, and E. T. Ordman, “Clique partitions and clique coverings,” Discrete Math.,72, No. 1–3, 93–101 (1988).
P. Erdös and D. B. West, “A note on the interval number of a graph,” Discrete Math.,55, No. 2, 129–133 (1985).
S. Even and A. Itai, “Queues, stacks and graphs,” in: Theory of Machines and Computations, Acad. Press, N.Y., 71–80 (1971).
S. Even, A. Pnueli, and A. Lempel, “Permutation graphs and transitive graphs,” J. Assoc. Comput. Mach.,19, No. 3, 400–410 (1972).
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).
R. B. Feinberg, “The circular dimension of a graph,” Discrete Math.,25, No. 1, 27–31 (1979).
J. Felsenstein, “Numerical methods for inferring evolutionary trees,” Quart. Rev. Biol.,57, No. 4, 379–404 (1982).
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).
P. C. Fishburn, “On the sphericity and cubicity of graphs,” J. Combin. Theory,B35, No. 3, 309–318 (1983).
P. C. Fishburn, Interval orders and interval graphs: A study of partially ordered sets, New York (1985).
E. Flapan, “Symmetries of knotted hypothetical molecular graphs,” Discrete Appl. Math.,19, No. 1–3, 157–166 (1988).
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.
J. C. Fourier, “Une caracterization des graphs de cordes,” C. R. Acad. Sci. Paris,A286, 811–813 (1978).
P. Frankl and H. Maehara, “On the contact dimensions of graphs,” Discrete Comput. Geom.,3, No. 1, 89–96 (1987).
P. Frankl and H. Maehara, “The Johnson-Lindenstrauss lemma and the sphericity of some graphs,” J. Combin. Theory,B44, No. 3, 355–362 (1988).
H. de Fraysseix, “A characterization of circle graphs,” Eur. J. Comb.,5, No. 3, 223–238 (1984).
L. C. Freeman, “Spheres, cubes, and boxes: graph dimensionality and network structure,” Soc. Networks,5, No. 2, 139–156 (1983).
D. R. Fulkerson and O. A. Gross, “Incidence matrices and interval graphs,” Pacif. J. Math.,15, 835–855 (1965).
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.
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).
M. R. Garey and D. S. Johnson, “Crossing number is NP-complete,” SIAM J. Alg. Disc. Math.,4, No. 3, 312–316 (1983).
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).
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).
F. Gavril, “Algorithms for a maximum clique and a maximum independent set of a circle graph,” Networks,3, 261–273 (1973).
F. Gavril, “The intersection graphs of subtrees in trees are exactly the chordal graphs,” J. Combin. Theory,B16, No. 1, 47–56 (1974).
F. Gavril, “A recognition algorithm for the intersection graphs of directed paths in directed trees,” Discrete Math.,13, No. 3, 237–249 (1975).
F. Gavril, “A recognition algorithm for the intersection graphs of paths in trees,” Discrete Math.,23, No. 3, 211–227 (1978).
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).
J. Gimbel, “End vertices in interval graphs,” Discrete Appl. Math.,21, No. 3, 257–259 (1988).
M. C. Golumbic, Algorithmic graph theory and perfect graphs, N. Y., Adad. Press, 1980.
M. C. Golumbic, “Algorithmic aspects of intersection graphs and representation hypergraphs,” Graphs and Comb,4, No. 4, 307–327 (1988).
M. C. Golumbic and P. L. Hammer, “Stability in circular are graphs,” J. Algorithms,9, No. 3, 314–320 (1988).
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).
M. C. Golumbic and R. E. Jamison, “Edge and vertex intersection of paths in a tree,” Discrete Math.,55, No. 2, 151–159 (1985).
M. C. Golumbic and C. L. Monma, “A generalization of interval graphs with tolerances,” Congressus Numerantium35, 321–331 (1982).
M. C. Golumbic, C. L. Monma, and W. T. Trotter (Jr.), “Tolerance graphs,” Discrete Appl. Math.,9, No. 2, 157–170 (1984).
M. C. Golumbic, D. Rotem, and J. Urrutia, “Comparability graphs and intersection graphs,” Discrete Math.,43, No. 1, 37–46 (1983).
R. L. Graham and H. O. Pollak, “On the addressing problem for loop switching,” J. Bell Syst. Techn.,50, No. 8, 2495–2519 (1971).
R. L. Graham and H. O. Pollak, “On embedding graphs in squashed cubes,” Lect. Notes Math.,303, 99–110 (1972).
R. L. Graham and P. M. Winkler, “Isometric embeddings of graphs,” Proc. Nat. Acad. Sci. USA, Phys. Sci.,81, No. 2, 7259–7260 (1984).
R. L. Graham and P. M. Winkler, “On isometric embeddings of graphs,” Trans. Amer. Math. Soc,288, No. 2, 527–536 (1985).
J. R. Griggs, “Extremal values of the interval number of a graph. II,” Discrete Math.,28, No. 1, 37–47 (1979).
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).
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).
S. E. Hambrusch and J. Simon, “Solving undirected graph problems on VLSI,” SIAM J. Comput.,14, No. 3, 527–544 (1985).
P. L. Hammer and B. Simeone, “The splittance of a graph,” Combinatorica,1, No. 3, 275–284 (1981).
F. Harary and F. Buckley, “On the euclidean dimension of a wheel,” Graphs and Comb.,4, No. 1, 23–30 (1988).
F. Harary, J. A. Kabell, and F. R. McMorris, “Bipartite intersection graphs,” Comment. Math. Univ. Carol.,23, No. 4, 739–745 (1982).
F. Harary, R. A. Melter, and I. Tomescu, “Digital metrics: A graph-theoretical approach,” Pattern Recogn. Lett.,2, No. 3, 159–163 (1984).
N. Hartsfield, “The toroidal splitting number of the complete graph Kn,” Discrete Math.,62, 35–47 (1986).
N. Hartsfield, “The splitting number of the complete graph in the projective plane,” Graphs and Comb.,3, No. 4, 349–356 (1987).
N. Hartsfield, B. Jackson, and G. Ringel, “The splitting number of the complete graph,” Graphs and Comb.,1, 311–329 (1985).
T. E. Havel, The combinatorial distance geometry approach to the calculation of molecular conformation, Ph. D. Thesis, University of California, Berkeley, 1982.
F. Hoffmann and K. Kriegel, “Embedding rectilinear graphs in linear time,” Inform. Process. Lett.,29, No. 2, 75–79 (1988).
P. Horák and J. Siran, “On a modified concept of thickness of a graph,” Math. Nachr.,108, 305–306 (1982).
E. Howe, C. R. Johnson, and J. Lawrece, “The structure of distances in networks,” Networks,16, No. 1, 87–106 (1986).
E. Howorka, “A characterization of Ptolemaic graphs,” J. Graph. Theory,5, No. 3, 323–331 (1981).
W.-L. Hsu, “Maximum weight clique algorithms for circular-arc graphs and circle graphs,” SIAM J. Comput.,14, No. 1, 224–231 (1985).
W.-L. Hsu, “Recognizing planar perfect graphs,” J. Assoc. Comput. Mach.,34, No. 2, 255–288 (1987).
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).
J. P. Hutchinson, “Automorphism properties of embedded graphs,” J. Graph Theory, No. 1, 35–49 (1984).
W. Imrich and G. Schwartz, “Trees and length functions in groups,” Ann. Discrete Math.,17, 347–359 (1983).
X. Jin, “Large processors are good in VLSI chips,” Inform. Process. Lett.,18, No. 1, 47–49 (1984).
D. S. Johnson, “The NP-completeness column: an ongoing guide,” J. Algorithms.6, No. 3, 434–451 (1985).
A. D. Jovanovic, “Combinatorial characterization of hexagonal systems,” Discrete Appl. Math.,19, No. 1–3, 259–270 (1988).
J. R. Jungch, G. Dick, and A. G. Dick, “Computer-assisted sequencing, interval graphs, and molecular evolution,” Biosystems,15, 259–273 (1982).
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).
D. Kelly, “Fundamentals of planar ordered sets,” Discrete Math.,63, No. 2–3, 197–216 (1987).
D. G. Kendall, “Some problems and methods in statistical archaeology,” World Archaeology,1, No. 1, 61–76 (1969).
S. Klavzar and M. Petkovsek, “Intersection graphs of halflines and halfplanes,” Discrete Math.,66, No. 1–2, 133–137 (1987).
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).
D. Kleitman and K. J. Winston, “On the number of graphs without 4-cycles,” Discrete Math.,41, No. 2, 167–172 (1982).
P. Klenovcan, “Direct product decompositions of diagraphs,” Math. Slov.,38, No. 1, 3–10 (1988).
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).
J. Kratochvil, M. Goljan, and P. Kucera, “String graphs,” Rozpr. CSAV MPV,96, No. 3, (1986).
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).
M. Leclerc, “A graph-theoretical approach to a problem in circuit design,” Mitt. Math. Semin. Giessen., No. 175, 19–26 (1986).
F. T. Leighton, “New lower bound techniques for VLSI,” Math. Syst. Theory,17, No. 1, 47–70 (1984).
F. T. Leighton and A. L. Rosenberg, “Three-dimensional circuit layouts,” SIAM J. Cornput.,15, No. 3, 793–813 (1986).
E. Leiss, “Data base security and the representation of graphs as query graphs,” Congressus Numerantium,33, 167–183 (1981).
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).
N. Linial, L. Lovasz, and A. Wigderson, “Rubber bands, convex embeddings, and graph connectivity,” Combinatorica,8, No. 1, 91–102 (1988).
C. H. C. Little, “On rings of circuits in planar graphs,” Lect. Notes Math.,622, 133–140 (1977).
L. Lovasz, “Perfect graphs,” in: Selected Topics in Graph Theory 2, Acad. Press, N.Y., 55–87 (1983).
F. Luccio, S. Mazzone, and C. K. Wong, “A note on visibility graphs,” Discrete Math.,64, No. 2–3, 209–219 (1987).
C. Maas, “Some results about the interval numbers of a graph,” Discrete Appl. Math.,6, No. 1, 99–102 (1983).
C. Maas, “Determining the interval number of triangle-free graph,” Computing,31, No. 4, 347–354 (1983).
H. Maehara, “On time graphs,” Discrete Math.,32, No. 3, 281–289 (1980).
H. Maehara, “Space graphs and sphericity,” Discrete Appl. Math.,7, No. 1, 55–64 (1984).
H. Maehara, “A digraph represented by a family of boxes or spheres,” J. Graph Theory,8, No. 3, 431–439 (1984).
H. Maehara, “Sphericity exceeds cubicity for almost all complete bipartite graphs,” J. Combin. Theory,B40, No. 2, 231–235 (1986).
H. Maehara, “On the euclidean dimension of a complete multipartite graph,” Discrete Math.,72, No.1–3, 285–289 (1988).
H. Maehara, J. Reiterman, V. Rödl, and E. Sinajova, “Embedding of trees in euclidean space,” Graphs Comb.,4, No. 1, 43–47 (1988).
N. V. R. Mahadev and U. N. Peled, “Strict 2-threshold graphs,” Discrete Appl. Math.,21, No. 2, 113–131 (1988).
M. May and K. Szkatula, “On the bipartite crossing number,” Contr. and Cybern.,17, No. 1, 85–98 (1988).
F. R. McMorris and D. R. Shier, “Representing chordal graphs on K1,n,” Comment. Math. Univ. Carol.,24, No. 3, 489–494 (1983).
G. L. Miller, “Finding small simple cycle separators for 2-connected planar graphs,” J. Comput. and Syst. Sci.,32, No. 3, 265–279 (1986).
G. L. Miller, “An additivity theorem for the genus of a graph,” J. Combin. Theory,B43, No. 1, 25–47 (1987).
B. Mohar, “Embeddings of infinite graphs,” J. Combin. Theory,44, No. 1, 29–43 (1988).
B. Mohar, “Nonorientable genus of nearly complete bipartite graphs,” Discrete and Comput. Geom.,3, No. 2, 137–146 (1988).
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).
C. L. Monma and V. K. Wei, “Intersection graphs of paths in a tree,” J. Combin. Theory,B41, No. 2, 141–181 (1986).
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).
W. Naji, “Reconnaissance des graphes de cordes,” Discrete Math.,54, No. 3, 329–337 (1985).
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.
S. Negami, “Uniqueness and faithfulness of embedding of toroidal graphs,” Discrete Math.,44, No. 2, 161–180 (1983).
S. Negami, “Uniquely and faithfully embeddable projective-planar triangulations,” J. Combin. Theory,B36, No. 2, 189–193 (1984).
S. Negami, “Enumeration of projective-planar embeddings of graphs,” Discrete Math.,62, No. 3, 299–306 (1986).
S. Negami, “Re-embedding of projective-planar graphs,” J. Combin. Theory,B44, No. 3, 276–299 (1988).
S. Negami, “The spherical genus and virtually planar graphs,” Discrete Math.,70, No. 2, 159–168 (1988).
J. Nesetril and R. Thomas, “A note on spatial representation of graphs,” Comment. Math. Univ. Carol.,26, No. 4, 655–659 (1985).
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.
R. J. Opsut and F. S. Roberts, “Optimal I-intersection assignments for graphs: A linear programming approach,” Networks,13, No. 3, 317–326 (1983).
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).
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.
L. Oubina and R. Zucchello, “A generalization of outerplanar graphs,” Discrete Math.,51, No. 3, 243–249 (1984).
T. D. Parsons, G. Pica, T. Pisanski, and A. G. S. Ventre, “Orientably simple graphs,” Math. Slov.,37, No. 4, 391–394 (1987).
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.
G. W. Peck, “A new proof of a theorem of Graham and Pollak,” Discrete Math.,49, No. 3, 327–328 (1984).
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.
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.
T. Pisanski, “Nonorientable genus of Cartesian products of regular graphs,” J. Graph Theory,6, No. 4, 391–402 (1982).
M. D. Plummer, “Matching extension and the genus of a graph,” J. Combin. Theory,B44 No. 3, 329–337 (1988).
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).
S. Poljak, V. Rödl, and D. Turzik, “Complexity of representation of graphs by set systems,” Discrete Appl. Math.,3, 301–312 (1981).
R. Raghavan, J. Cohoon, and S. Sahni, “Single bend wiring,” J. Algorithms,7, No. 2, 232–257 (1986).
I. V. Ramakrishnan and P. J. Varman, “On mapping cube graphs onto VLSI arrays,” Lect. Notes Comput. Sci.,181, 296–316 (1984).
R. C. Read, D. Rotem, and J. Urrutia, “Orientations of circle graphs,” J. Graph Theory,6, No. 3, 325–341 (1982).
P. L. Renz, “Intersection representations of graphs by arcs,” Pacif. J. Math.,34, No. 2, 501–510 (1970).
R. B. Richter, “On the nonorientable genus of a 2-connected graph,” J. Combin. Theory,B43, No. 1, 48–59 (1987).
R. B. Richter, “On the Eulerian genus of a 2-connected graph,” J. Combin. Theory,B43, No. 1, 60–69 (1987).
R. B. Richter and H. Shank, “The cycle space of an embedded graph,” J. Graph Theory,8, No. 3, 365–369 (1984).
F. S. Roberts, “Indifference graphs,” in: Proof Techn. Graph Theory, N.Y., Acad. Press, 1969, 139–146.
F. S. Roberts, “On the boxicity and cubicity of a graph,” in: Recent Progr. in Combinator., N.Y., Acad. Press, 1969, 301–310.
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.
F. S. Roberts, “Applications of edge coverings by cliques,” Discrete Appl. Math.,10, No. 1, 93–109 (1985).
N. Robertson and P. D. Seymour, “Graph minors. VI. Disjoint paths across a disc,” J. Combin. Theory,B41, No. 1, 115–138 (1986).
N. Robertson and P. D. Seymour, “Graph minors. VII. Disjoint paths on a surface,” J. Combin. Theory,B45, No. 2, 212–254 (1988).
P. Rosenstiehl and R. E. Tarjan, “Gauss codes, planar Hamiltonian graphs, and stack-sortable permutations,” J. Algorithms,5, No. 3, 375–390 (1984).
P. Rosenstiehl and R. E. Tarjan, “Rectilinear planar layouts of planar graphs and bi-polar orientations,” Discrete & Comput. Geom.,1, 342–351 (1986).
D. Rotem and J. Urrutia, “Circular permutation graphs,” Networks,12, No. 4, 429–437 (1982).
Ryu Hae Dong and Li Chong I, “The study on the maximum genus of graphs,” Suhak, No. 3, 13–16 (1986).
H. Sachs, “On a spatial analogue of Kuratowski's theorem on planar graphs — an open problem,” Lect. Notes Math.,1018, 230–241 (1983).
S. Sattath and A. Tversky, “Additive similarity trees,” Psychometrica,42, No. 3, 319–345 (1977).
E. R. Scheinerman, “Characterizing intersection classes of graphs,” Discrete Math.,55, No. 2, 185–193 (1985).
E. R. Scheinerman, “Irrepresentability by multiple intersection, or why the interval number is unbounded,” Discrete Math.,55, No. 2, 195–211 (1985).
E. R. Scheinerman, “Irredundancy in multiple interval representations,” Discrete Math.,63, No. 1, 101–108 (1987).
E. R. Scheinerman, “The maximum interval number of graphs with given genus,” J. Graph Theory,11, No. 3, 441–446 (1987).
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).
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.
F. Scotti, “II complementare di un grafo non superiormente immergibile é superiormente immergibile,” Boll. Unione mat. ital.,A3, No. 1, 111–118 (1984).
J. Sedlacek, “O jednom zobeeneni vnejskove rivinnych grafu,” Cas. pestov. mat.,113, No. 2, 213–218 (1988).
Shaohan Majand W. D. Wallis, “Maximal-clique partitions of interval graphs,” J. Austral Math. Soc. A,45, No. 2, 227–232 (1988).
J. B. Shearer, “A note on circular dimension,” Discrete Math.,29, No. 1, 103 (1980).
X. Shen and H. Edelsbrunner, “A tight lower bound on the size of visibility graphs,” Inform. Process. Lett.,26, No. 2, 61–64 (1987).
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.
J. M. S. Simoes-Pereira, “A note on the tree realizability of a distance matrix,” J. Combin. Theory,6, No. 3, 303–310 (1969).
F. W. Sinden, “Topology of thin film RC-circuits,” Theorie graphes. Journées internat. étude, Rome, 1966, Paris-New York, 1967, 389–393.
J. Sirán, “Crossing-critical edges and Kuratowski subgraphs of a graph,” J. Combin. Theory,B35, No. 2, 83–92 (1983).
J. Sirán, “Edges and Kuratowski subgraphs of nonplanar graphs,” Math. Nachr.,113, 187–190 (1983).
J. Siráň and P. Horak, “A construction of thickness-minimal graphs,” Discrete Math.,64, No. 2–3, 263–268 (1987).
J. Siráň and M. Skoviera, “Relative embeddings of graphs on closed surfaces,” Math. Nachr.,136, 275–284 (1988).
J. Siráň and M. Škoviera, “Oriented relative embeddings of graphs,” Zastos. mat.,19, No. 3–4, 589–597 (1987).
D. Skrien, “Chronological orderings of interval graphs,” Discrete Appl. Math.,8, No. 1, 69–83 (1984).
D. Skrien and J. Gimbel, “Homogeneously representable interval graphs,” Discrete Math.,55, No. 2, 213–216 (1985).
J. Spinrad, “On comparability and permutation graphs,” SIAM J. Comput.,14, No. 3, 658–670 (1985).
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).
F. W. Stahl, “Circular genetic maps,” J. Cell Physiol.,70, No. 1, 1–12 (1967).
W. Stanczak, “An efficient algorithm for partitioning a network into minimally inter-connected subnetworks,” Contr. and Cybern.,13, No. 1–2, 97–112 (1984).
J. E. Steif, “The frame dimension and the complete overlap dimension of a graph,” J. Graph Theory,9, No. 2, 285–299 (1985).
K. E. Stoffers, “Scheduling of traffic lights — a new approach,” Transp. Res.,2, 199–234 (1968).
J. A. Storer, “On minimal node-cost planar embeddings,” Networks,14, 181–212 (1984).
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.
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).
M. M. Syslo, “Triangulated edge intersection graphs of paths in a tree,” Discrete Math.,55, No. 2, 217–220 (1985).
R. Tamassia, “On embedding a graph in the grid with the minimum number of bends,” SIAM J. Comput.,16, No. 1, 421–444 (1987).
R. Tamassia and I. G. Tollis, “A unified approach to visibility representations of planar graphs,” Discrete Comput. Geom.,1, 321–341 (1986).
R. E. Tarjan, “Decomposition by clique separators,” Discrete Math.,55, No. 2, 221–231 (1985).
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).
C. Thomassen, “Plane representations of graphs,” in: Progress in Graph Theory, Academic Press, N.Y., 1984, 43–69.
C. Thomassen, “Planarity and duality of finite and infinite graphs,” J. Combin. Theory,B29, No. 2, 244–271 (1980).
C. Thomassen, “Interval representations of planar graphs,” J. Combin. Theory,B40, No. 1, 9–20 (1986).
W. T. Trotter (Jr.), “A characterization of Roberts' inequality for boxity,” Discrete Math.,28, No. 3, 303–313 (1979).
W. T. Trotter (Jr.) and F. Harary, “On double and multiple interval graphs,” J. Graph Theory,3, No. 3, 205–211 (1979).
W. T. Trotter (Jr.) and D. B. West, “Poset boxicity of graphs,” Discrete Math.,64, No. 1, 105–107 (1987).
A. Tucker, “Matrix characterizations of circular-arc graphs,” Pacif. J. Math.,39, No. 2, 535–545 (1971).
A. Tucker, “Structure theorems for some circular-arc graphs,” Discrete Math.,7, No. 1–2, 167–195 (1974).
A. Tucker, “Circular arc graphs: new uses and new algorithm,” Lect. Notes Math., No. 642, 580–589 (1978).
A. Tucker, “An efficient test for circular-arc graphs,” SIAM J. Comput.,9, No. 1, 1–24 (1980).
W. T. Tutte, “Convex representations of graphs,” Proc. London Math. Soc.,10, No. 38, 304–320 (1960).
M. Veldhorst, “The optimal representation of disjoint iso-oriented rectangles in two-dimensional trees,” J. Algorithms,7, No. 1, 1–34 (1986).
H.-J. Voss, “Note on a paper of McMorris and Shier,” Comment. Math. Univ. Carol.,26, No. 2, 319–322 (1985).
J. R. Walter, “Representations of chordal graphs as subtrees of a tree,” J. Graph. Theory,2, No. 3, 265–267 (1978).
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).
J. Warfield, “Crossing theory and hierarchy mapping,” IEEE Trans. Syst., Man, and Cybern.,SMC-7, 502–523 (1977).
G. Wegner, “Eigenschaften der Nerven homolgish-eigenfacher Familien in Rh,” Ph. Thesis Göttingen, 1967.
E. Welzl, “Constructing the visibility graph for n-line segments in O(n2) time,” Inform. Process. Lett.,20, No. 4, 167–171 (1985).
W. Wessel, “Chord graphs — new means for representing graphs,” Zastos, Mat.,19, No. 3–4, 619–627 (1987).
W. Wessel, “The non-biplanar character of the graph K10-K3,” Prepr. Akad. Wiss. DDR, Karl-Weierstrass Inst. Math., No. 3, 1–21 (1988).
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).
K. White, M. Farber, and W. Pulleyblank, “Steiner trees, connected domination and strongly chordal graphs,” Networks,15, No. 1, 109–124 (1985).
H. S. Wilf, “Finite lists of obstructions,” Amer. Math. Mon.,94, No. 3, 267–271 (1987).
P. M. Winkler, “Proof of the squashed cube conjecture,” Combinatorica,3, No. 1, 135–139 (1983).
P. M. Winkler, “Isometric embedding in products of complete graphs,” Discrete Appl. Math.,7, No. 2, 221–225 (1984).
P. M. Winkler, “Every connected graph is a query graph,” J. Combinatorics, Inf. and Syst. Sci.,10, No. 1–2, 1–4 (1985).
P. M. Winkler, “The metric structure of graphs: theory and applications,” London Math. Soc. Lect. Note Ser., No. 123, 197–221 (1987).
H. S. Witsenhausen, “On intersections of interval graphs,” Discrete Math.,31, No. 2, 211–216 (1980).
H. S. Witsenhausen, “Minimum dimension embedding of finite metric spaces,” J. Combin. Theory,A42, No. 4, 184–199 (1986).
D. Wolfe, “Imbedding a finite metric set in an N-dimensional Minkowski space,” Proc. Koninkl. nederl. akad. wet.,A70, No. 1, 136–140 (1967).
D. Woods, “Drawing planar graphs, Ph. D. Thesis,” Computer Science Dept., Stanford Univ., 1982.
Chiko Yoshioka and Chieko Tanabe, “On some embedding of complete graphs,” Mem. Fac. Educ. Niigata Univ. Nat. Sci.,28, No. 2, 57–62 (1987).
V. Zeleznik, “Quadrilateral embeddings of the conjunction of graphs,” Math. Slov.,38, No. 2, 89–98 (1988).
T. P. Zivkovic, “Graphical representation of regular resonance structures and their linear dependence,” Discrete Appl. Math.,19, No. 1–3, 397–414 (1988).
Additional information
Translated from Itogi Nauki i Tekhniki, Seriya Teoriya Veroyatnostei, Matematicheskaya Statistika, Teoreticheskaya Kibernetika, Vol. 27, pp. 129–196, 1990.
Rights 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
Issue Date:
DOI: https://doi.org/10.1007/BF01097528