×

The excluded minors for isometric realizability in the plane. (English) Zbl 1358.05076

Summary: Let \(G\) be a graph and \(p \in [1, \infty]\). The parameter \(f_p(G)\) is the least integer \(k\) such that for all \(m\) and all vectors \((r_v)_{v \in V(G)} \subseteq \mathbb{R}^m\), there exist vectors \((q_v)_{v \in V(G)} \subseteq \mathbb{R}^k\) satisfying \(\|r_v-r_w\|_p=\|q_v-q_w\|_p\) for all \(vw\in E(G)\). It is easy to check that \(f_p(G)\) is always finite and that it is minor monotone. By the graph minor theorem of N. Robertson and P. D. Seymour [J. Comb. Theory, Ser. B 92, No. 2, 325–357 (2004; Zbl 1061.05088)], there are a finite number of excluded minors for the property \(f_p(G) \leq k\). In this paper, we determine the complete set of excluded minors for \(f_\infty(G) \leq 2\). The two excluded minors are the wheel on five vertices and the graph obtained by gluing two copies of \(K_4\) along an edge and then deleting that edge. We also show that the same two graphs are the complete set of excluded minors for \(f_1(G) \leqslant 2\). In addition, we give a family of examples that show that \(f_\infty\) is unbounded on the class of planar graphs and \(f_\infty\) is not bounded as a function of tree-width.

MSC:

05C10 Planar graphs; geometric and topological aspects of graph theory
05C83 Graph minors
05C12 Distance in graphs
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)

Citations:

Zbl 1061.05088
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] D. Avis, {\it Some Polyhedral Cones Related to Metric Spaces}, Ph.D. thesis, Stanford University, Stanford, CA, 1977.
[2] K. Ball, {\it Isometric embedding in \(l_p\)-spaces}, European J. Combin., 11 (1990), pp. 305-311. · Zbl 0712.46008
[3] A. I. Barvinok, {\it Problems of distance geometry and convex properties of quadratic maps}, Discrete Comput. Geom., 13 (1995), pp. 189-202, . · Zbl 0829.05025
[4] M. Belk, {\it Realizability of graphs in three dimensions}, Discrete Comput. Geom., 37 (2007), pp. 139-162. · Zbl 1114.05066
[5] M. Belk and R. Connelly, {\it Realizability of graphs}, Discrete Comput. Geom., 37 (2007), pp. 125-137. · Zbl 1114.05067
[6] J. Bourgain, {\it On Lipschitz embeddings of finite metric spaces in Hilbert space}, Israel J. Math., 52 (1985), pp. 46-52. · Zbl 0657.46013
[7] M. Deza and M. Laurent, {\it Geometry of Cuts and Metrics}, Springer, New York, 1997. · Zbl 0885.52001
[8] M. Fréchet, {\it Les dimensions d’un ensemble abstrait}, Math. Ann., 68 (1910), pp. 145-168. · JFM 41.0102.03
[9] W. Holsztynski, {\it \(\mathbb{R}^n\) as a universal metric space}, Notices Amer. Math. Soc., 25 (1978), pp. A-367.
[10] D. Kitson, {\it Finite and infinitesimal rigidity with polyhedral norms}, Discrete Comput. Geom., 54 (2015), pp. 390-411, . · Zbl 1329.52021
[11] C. St. J. A. Nash-Williams, {\it Decomposition of finite graphs into forests}, J. London Math. Soc., 39 (1964), 12. · Zbl 0119.38805
[12] N. Robertson and P. Seymour, {\it Graph minors. XX. Wagner’s conjecture}, J. Combin. Theory Ser. B, 92 (2004), pp. 325-357. · Zbl 1061.05088
[13] N. Robertson and P. D. Seymour, {\it Graph minors. XIII. The disjoint paths problem}, J. Combin. Theory Ser. B, 63 (1995), pp. 65-110, . · Zbl 0823.05038
[14] V. Rödl and A. Ruciński, {\it Bipartite coverings of graphs}, Combin. Probab. Comput., 6 (1997), pp. 349-352, . · Zbl 0894.05022
[15] P. D. Seymour, {\it Matroids and multicommodity flows}, European J. Combin., 2 (1981), pp. 257-290, . · Zbl 0479.05023
[16] M. Sitharam and H. Gao, {\it Characterizing graphs with convex and connected Cayley configuration spaces}, Discrete Comput. Geom., 43 (2010), pp. 594-625, . · Zbl 1215.05085
[17] M. Sitharam and J. Willoughby, {\it On Flattenability of Graphs}, preprint, , 2015. · Zbl 1439.05166
[18] W. T. Tutte, {\it A theory of 3-connected graphs}, Indag. Math., 23 (1961), pp. 441-455. · Zbl 0101.40903
[19] H. S. Witsenhausen, {\it Minimum dimension embedding of finite metric spaces}, J. Combin. Theory Ser. A, 42 (1986), pp. 184-199. · Zbl 0594.05024
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.