×

Clin d’oeil on \(L_1\)-embeddable planar graphs. (English) Zbl 0892.05018

Authors’ abstract: We present some properties of \(L_1\)-embeddable planar graphs. We also present a characterization of graphs isometrically embeddable into half-cubes. This result implies that every planar \(L_1\)-graph \(G\) has a scale 2 embedding into a hypercube. Further, under some additional conditions we show that for a simple circuit \(C\) of a planar \(L_1\)-graph \(G\) the subgraph \(H\) of \(G\) bounded by \(C\) is also \(L_1\)-embeddable. In many important cases, the length of \(C\) is the dimension of the smallest cube in which \(H\) has a scale embedding. Using these facts we establish the \(L_1\)-embeddability of a list of planar graphs.

MSC:

05C10 Planar graphs; geometric and topological aspects of graph theory
05C12 Distance in graphs
05C75 Structural characterization of families of graphs
92E10 Molecular structure (graph-theoretic methods, methods of differential topology, etc.)
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Assouad, P., Embeddability of regular polytopes and honeycombes in hypercubes te]The Geometric Vein: the Coxeter Festschrift, ((1981), Springer: Springer Berlin), 141-147
[2] Assouad, P.; Deza, M., Espaces métriques plongeables dans un hypercube: aspects combinatoires, Ann. Discrete Math., 8, 197-210 (1980) · Zbl 0464.05029
[3] H.-J. Bandelt, V. Chepoi, Weakly median graphs: decomposition, \(l_1\); H.-J. Bandelt, V. Chepoi, Weakly median graphs: decomposition, \(l_1\)
[4] Baracs, J., Juxtapositions, Structural Topology, 1, 59-72 (1979) · Zbl 0534.51015
[5] Bo-Yin, Yang, A circular argument on crowns, (Abstracts of 8th Franco-Japanese-Chinese Conference on Combinatorics and Computer Science. Abstracts of 8th Franco-Japanese-Chinese Conference on Combinatorics and Computer Science, Brest (1995)), 23-25
[6] Bretagnolle, J.; Castelle, D. Dacunha; Krivine, J. L., Lois stables et espaces \(L_p\), Ann. l’Institut Henri Poincaré, 2, 3, 231-259 (1966) · Zbl 0139.33501
[7] Chepoi, V., On distances in benzenoid systems, J. Chem. Inform. Comput. Sci., 36, 1169-1172 (1996)
[8] Chepoi, V.; Klavz̆ar, S., The Wiener index and the Szeged index of benzenoid systems in linear time, J.Chem.Inform.Comput.Sci., 37 (1997), in print
[9] Deza, M.; Grishukhin, V., Hypermetric graphs, Quart. J. Math. Oxford, 44, 2, 399-433 (1993) · Zbl 0795.05120
[10] Deza, M.; Grishukhin, V., A zoo of \(l_1\)-embeddable polytopal graphs, Bull. Math. Inst. Acad. Sinica (1997), in print · Zbl 0886.05056
[11] Deza, M.; Grishukhin, V.; Laurent, M., Hypermetrics in geometry of numbers, DIMACS Series in Discr. Math. And Theoretical Computer Sci., 20, 1-109 (1995) · Zbl 1071.52500
[12] Deza, M.; Laurent, M., \(l_1\)-rigid graphs, J. Algebra Combin., 3, 153-175 (1994) · Zbl 0802.05066
[13] Deza, M.; Laurent, M., Applications of cut polyhedra, J. Comput. Appl. Math., 55, 217-247 (1994) · Zbl 0826.52013
[14] Deza, M.; Shpectorov, S., Recognition of \(l_1\)-graphs with complexity \(O\) (nm), or football in a hypercube, Europ. J. Combin., 17, 279-289 (1996) · Zbl 0854.05093
[15] Deza, M.; Stogrin, M., Scale-isometric embeddings of Archimedian tilings, polytopes and their duals into cubic lattices and hypercubes, Uspechi Math. Nauk, 51, 199-200 (1996)
[16] Deza, M.; Tuma, J., A note on \(l_1\)-rigid planar graphs, Europ. J. Combin., 17, 157-160 (1996) · Zbl 0851.05047
[17] Dias, J. R., Indacenoid isomers of semibuckminsterfullerene (Buckybowl) and their topological characteristics, J. Chem. Inform. Comput. Sci., 35, 148-151 (1995)
[18] Djoković, D.Ž., Distance-preserving subgraphs of hypercubes, J. Combin. Theory Ser. B, 14, 263-267 (1973) · Zbl 0245.05113
[19] Grünbaum, B., Odd polyhedra, Geombinatorics, 1, 4-5 (1991) · Zbl 0843.52008
[20] Grünbaum, B.; Shepard, G. C., Tilings and Patterns, ((1986), Freeman: Freeman New York) · Zbl 0601.05001
[21] Gutman, I.; Klavz̆ar, S., A method for calculating Wiener numbers of benzenoid hydrocarbons, Models in Chemistry (Acta Chim. Hung.), 133, 389-399 (1996)
[22] Huck, A.; Kochol, M., Five cycle double covers of some cubic graphs, J. Combin. Theory Ser. B, 64, 119-125 (1995) · Zbl 0820.05045
[23] Jiang, Y.; Shao, Y.; Kirby, E. C., Topology and stability of trivalent polyhedral clusters, Fullerene Sci. Technol., 2, 4, 481-497 (1994)
[24] Klavz̆ar, S.; Gutman, I.; Mohar, B., Labeling of benzenoid systems which reflects the vertex-distance relations, J. Chem. Inform. Comput. Sci., 35, 590-593 (1995)
[25] Pedersen, J., Geometry: the unity and practice, Math. Intelligencer, 5, 4, 37-49 (1983) · Zbl 0536.51008
[26] Prisăcaru, Ch.; Soltan, P.; Chepoi, V., On embeddings of planar graphs into hypercubes, (Proc. Moldavian Academy of Sci. Math, 1 (1990)), 43-50, (in Russian)
[27] Roth, R. L.; Winkler, P. M., Collapse of the metric hierarchy for bipartite graphs, European J. Combin., 7, 371-375 (1983) · Zbl 0619.05042
[28] Shpectorov, S. V., On scale embeddings of graphs into hypercubes, European J. Combin., 14, 117-130 (1993) · Zbl 0773.05044
[29] van de Vel, M. L.J., Theory of Convex Structures, ((1993), North-Holland: North-Holland Amsterdam) · Zbl 0785.52001
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.