Abstract
A metric graph is a pair (G, d), where G is a graph and \(d:E(G) \rightarrow \mathbb {R}_{\ge 0}\) is a distance function. Let \(p \in [1,\infty ]\) be fixed. An isometric embedding of the metric graph (G, d) in \(\ell _p^k = (\mathbb {R}^k, d_p)\) is a map \(\phi :V(G) \rightarrow \mathbb {R}^k\) such that \(d_p(\phi (v), \phi (w)) = d(vw)\) for all edges \(vw\in E(G)\). The \(\ell _p\)-dimension of G is the least integer k such that there exists an isometric embedding of (G, d) in \(\ell _p^k\) for all distance functions d such that (G, d) has an isometric embedding in \(\ell _p^K\) for some K. It is easy to show that \(\ell _p\)-dimension is a minor-monotone property. In this paper, we characterize the minor-closed graph classes \(\mathscr {C}\) with bounded \(\ell _p\)-dimension, for \(p \in \{2,\infty \}\). For \(p=2\), we give a simple proof that \(\mathscr {C}\) has bounded \(\ell _2\)-dimension if and only if \(\mathscr {C}\) has bounded treewidth. In this sense, the \(\ell _2\)-dimension of a graph is ‘tied’ to its treewidth. For \(p=\infty \), the situation is completely different. Our main result states that a minor-closed class \(\mathscr {C}\) has bounded \(\ell _\infty \)-dimension if and only if \(\mathscr {C}\) excludes a graph obtained by joining copies of \(K_4\) using the 2-sum operation, or excludes a Möbius ladder with one ‘horizontal edge’ removed.
Similar content being viewed by others
Notes
The latter lemma works under the assumption that G does not have the graph consisting of two vertices linked by k parallel edges as a minor, which is more restrictive than just forbidding a k-fan minor. Nevertheless, the two proofs are based on a similar strategy.
References
Abraham, I., Bartal, Y., Neiman, O.: Advances in metric embedding theory. Adv. Math. 228(6), 3026–3126 (2011)
Ball, K.: Isometric embedding in \(l_p\)-spaces. Eur. J. Comb. 11(4), 305–311 (1990)
Belk, M.: Realizability of graphs in three dimensions. Discrete Comput. Geom. 37(2), 139–162 (2007)
Belk, M., Connelly, R.: Realizability of graphs. Discrete Comput. Geom. 37(2), 125–137 (2007)
Bourgain, J.: On Lipschitz embedding of finite metric spaces in Hilbert space. Isr. J. Math. 52(1–2), 46–52 (1985)
Chekuri, Ch., Chuzhoy, J.: Polynomial bounds for the grid-minor theorem. J. ACM 63(5), #40 (2016)
Chuzhoy, J., Tan, Z.: Towards tight(er) bounds for the excluded grid theorem. In: 30th Annual ACM-SIAM Symposium on Discrete Algorithms (San Diego 2019), pp. 1445–1464. SIAM, Philadelphia (2019)
Deza, M.M., Laurent, M.: Geometry of Cuts and Metrics. Algorithms and Combinatorics, vol. 15. Springer, Berlin (1997)
Di Battista, G., Tamassia, R.: On-line maintenance of triconnected components with SPQR-trees. Algorithmica 15(4), 302–318 (1996)
Diestel, R.: Graph Theory. Graduate Texts in Mathematics, vol. 173. Springer, Berlin (2017)
E.-Nagy, M., Laurent, M., Varvitsiotis, A.: Forbidden minor characterizations for low-rank optimal solutions to semidefinite programs over the elliptope. J. Comb. Theory Ser. B 108, 40–80 (2014)
Erdös, P., Szekeres, G.: A combinatorial problem in geometry. Compos. Math. 2, 463–470 (1935)
Fiorini, S., Huynh, T., Joret, G., Varvitsiotis, A.: The excluded minors for isometric realizability in the plane. SIAM J. Discrete Math. 31(1), 438–453 (2017)
Joret, G., Paul, Ch., Sau, I., Saurabh, S., Thomassé, S.: Hitting and harvesting pumpkins. SIAM J. Discrete Math. 28(3), 1363–1390 (2014)
Kitson, D., Nixon, A., Schulze, B.: Rigidity of symmetric frameworks in normed spaces. Linear Algebra Appl. 607, 231–285 (2020)
Laurent, M., Varvitsiotis, A.: A new graph parameter related to bounded rank positive semidefinite matrix completions. Math. Program. 145(1–2), 291–325 (2014)
Muller, C.: Excluded Minors for Isometric Embeddings of Graphs in \(\ell _\infty ^k\)-Spaces. MSc thesis, Université Libre de Bruxelles (2017)
Robertson, N., Seymour, P.D.: Graph minors. V. Excluding a planar graph. J. Comb. Theory Ser. B 41(1), 92–114 (1986)
Robertson, N., Seymour, P.D.: Graph minors. XX. Wagner’s conjecture. J. Comb. Theory Ser. B 92(2), 325–357 (2004)
Saxe, J.B.: Embeddability of weighted graphs in \(k\)-space is strongly NP-hard. In: 17th Allerton Conference in Communications, Control and Computing (Monticello 1979), pp. 480–489 (1979)
Schulze, B.: Combinatorial rigidity of symmetric and periodic frameworks. In: Handbook of Geometric Constraint Systems Principles. Discrete Math. Appl. (Boca Raton), pp. 543–565. CRC Press, Boca Raton (2019)
Sitharam, M., Willoughby, J.: On flattenability of graphs. Automated Deduction in Geometry (Coimbra 2014). Lecture Notes in Comput. Sci., vol. 9201. Lecture Notes in Artificial Intelligence, pp. 129–148. Springer, Cham (2015)
Witsenhausen, H.S.: Minimum dimension embedding of finite metric spaces. J. Comb. Theory Ser. A 42(2), 184–199 (1986)
Acknowledgements
We thank Monique Laurent and Antonios Varvitsiotis for helpful discussions regarding the material in Sect. 2. We also thank anonymous referees for their helpful comments on an earlier version of the paper.
Author information
Authors and Affiliations
Corresponding author
Additional information
Editor in Charge: János Pach
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
S. Fiorini and T. Huynh are supported by ERC Consolidator Grant 615640-ForEFront. G. Joret is supported by an ARC Grant from the Wallonia-Brussels Federation of Belgium. C. Muller is supported by the Luxembourg National Research Fund (FNR) Grant No. 11628910.
Rights and permissions
About this article
Cite this article
Fiorini, S., Huynh, T., Joret, G. et al. Unavoidable Minors for Graphs with Large \(\ell _p\)-Dimension. Discrete Comput Geom 66, 301–343 (2021). https://doi.org/10.1007/s00454-021-00285-5
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-021-00285-5