×
Cozzens, Margaret Barry; Roberts, Fred S.

On dimensional properties of graphs. (English) Zbl 0675.05054

Graphs Comb. 5, No. 1, 29-46 (1989).
Summary: A dimensional property of graphs is a property P such that every graph G is the intersection of graphs having property P. If P is a dimensional property, we describe a general method for computing the least integer k so that G is the intersection of k graphs having property P. We give simple applications of the method to computing the boxicity, the cubicity, the circular dimension, the rigid circuit dimension, and the overlap dimension, and mention connections to other concepts such as the threshold dimension.

Cited in 9 Documents

MSC:

05C75 Structural characterization of families of graphs

Keywords:

dimensional property of graphs; computing; boxicity; cubicity; circular dimension; rigid circuit dimension; overlap dimension; threshold dimension
PDF BibTeX XML Cite
\textit{M. B. Cozzens} and \textit{F. S. Roberts}, Graphs Comb. 5, No. 1, 29--46 (1989; Zbl 0675.05054)
Full Text: DOI
  • logo of hbz
  • logo of WorldCat

References:

[1] Balas, E.: Box Representations of a Family of Ellipsoids. Lecture at the Thirteenth Southeastern Conference on Graph Theory, Combinatorics, and Computing. Boca Raton, FL February 1982
[2] Bondy, J.A., Murty, U.S.R.: Graph Theory with Applications. New York: American Elsevier 1976 · Zbl 1226.05083
[3] Buckingham, M.: Circle graphs. Courant Computer Science Report No. 21. New York: New York University 1980
[4] Cozzens, M.B., Leibowitz, R.: Threshold dimension of graphs. SIAM J. Algebraic Discrete Methods,5, 579–595 (1984) · Zbl 0717.05069
[5] Cozzens, M.B., Leibowitz, R.: Multidimensional scaling and threshold graphs. J. Math. Psychol.31, 179–191 (1987) · Zbl 0649.92021
[6] Cozzens, M.B., Roberts, F.S.: Computing the boxicity of a graph by covering its complement by cointerval graphs. Discrete Appl. Math.6, 217–228 (1983) · Zbl 0524.05059
[7] Cozzens, M.B., Roberts, F.S.: Onk-suitable sets of arrangements and the boxicity of a graph. J. Comb. Inf. Syst. Sci.9, 14–24 (1984) · Zbl 0629.05059
[8] Donald, A.: An upper bound for the path number of a graph. J. Graph Theory4, 189–201 (1980) · Zbl 0427.05047
[9] Feinberg, R.B.: The circular dimension of a graph. Discrete Math.25, 27–31 (1979) · Zbl 0392.05057
[10] Fishburn, P.C.: On the sphericity and cubicity of graphs. J. Comb. Theory (B)35, 309–318 (1983) · Zbl 0533.05055
[11] Gavril, F.: Algorithms for a maximum clique and a maximum independent set of a circle graph. Networks3, 261–273 (1973) · Zbl 0259.05125
[12] Gilmore, P.C., Hoffman, A.J.: A characterization of comparability graphs and of interval graphs. Canad. J. Math.16, 539–548 (1964) · Zbl 0121.26003
[13] Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. New York: Academic Press 1980 · Zbl 0541.05054
[14] Hammer, P.L., Mahadev, N.V.R.: Bithreshold graphs. SIAM J. Algebraic Discrete Methods6, 497–506 (1985) · Zbl 0579.05052
[15] Kabell, J.A.: Intersection graphs: structure and invariants. Doctoral dissertation, University of Michigan. Ann Arbor, MI 1980
[16] Lekkerkerker, C.G., Boland, J. Ch.: Representation of a finite graph by a set of intervals on the real line. Fundam. Math.51, 45–64. (1962) · Zbl 0105.17501
[17] Lovasz, L.: On coverings of graphs. In: Theory of Graphs (Proc. Colloq. Tihany, Hungary, September 1966), pp. 231–236. New York: Academic Press 1968
[18] Maehara, H.: Sphericity exceeds cubicity for almost all complete bipartite graphs. J. Comb. Theory (B)40, 231–235 (1986) · Zbl 0595.05031
[19] Orlin, J.: Contentment in graph theory: Covering graphs with cliques. Proc. of the Koninklijke Nederlandse Academie van Wetenschappen Amsterdam, Series A80, 406–424 (1977) · Zbl 0374.05041
[20] Pullman, N.J.: Clique coverings of graphs IV: Algorithms. SIAM J. Comput.13, 57–75 (1984) · Zbl 0548.05050
[21] Pullman, N.J., DeCaen, D.: Clique coverings of graphs III: Clique coverings of regular graphs. Congr. Numerantium29, 795–808 (1980) · Zbl 0484.05048
[22] Roberts, F.S.: Indifference graphs. In: Proof Techniques in Graph Theory, edited by F. Harary pp. 139–146. New York: Academic Press 1969 (a)
[23] Roberts, F.S.: On the boxicity and cubicity of a graph. In: Recent Progress in Combinatorics, edited by W.T. Tutte pp. 301–310. New York: Academic Press 1969 (b) · Zbl 0193.24301
[24] Roberts, F.S.: Discrete Mathematical Models, with Applications to Social, Biological, and Environmental Problems. Englewood Cliffs, NJ: Prentice-Hall 1976 · Zbl 0363.90002
[25] Roberts, F.S.: Graph Theory and its Applications to Problems of Society, NSF-CBMS Monograph #29. Philadelphia, PA: SIAM Publications 1978
[26] Roberts, F.S.: Applications of edge coverings by cliques. Discrete Appl. Math.10, 93–109 (1985) · Zbl 0558.05046
[27] Shearer, J.B.: A note on circular dimension. Discrete Math.29, 103 (1980) · Zbl 0437.05049
[28] Trotter, W.T.: A characterization of Roberts’ inequality for boxicity. Discrete Math.28, 303–314 (1979) · Zbl 0421.05062
[29] Tucker, A.C.: Characterizing circular-arc graphs. Bull. Amer. Math. Soc.76, 1257–1260 (1970) · Zbl 0204.24401
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.