Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/81454
Title: The Excluded Minors for Isometric Realizability in the Plane
Authors: Fiorini, Samuel
Huynh, Tony
Joret, Gwenaël
Varvitsiotis, Antonios
Keywords: Finite metric spaces
Isometric embeddings
Issue Date: 2017
Source: Fiorini, S., Huynh, T., Joret, G., & Varvitsiotis, A. (2017). The Excluded Minors for Isometric Realizability in the Plane. SIAM Journal on Discrete Mathematics, 31(1), 438-453.
Series/Report no.: SIAM Journal on Discrete Mathematics
Abstract: 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 Robertson and Seymour [J. Combin. Theory Ser. B, 92 (2004), pp. 325--357], 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) \leq 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.
URI: https://hdl.handle.net/10356/81454
http://hdl.handle.net/10220/43485
ISSN: 0895-4801
DOI: 10.1137/16M1064775
Rights: © 2017 Society for Industrial and Applied Mathematics (SIAM). This paper was published in SIAM Journal on Discrete Mathematics and is made available as an electronic reprint (preprint) with permission of Society for Industrial and Applied Mathematics (SIAM). The published version is available at: [http://dx.doi.org/10.1137/16M1064775]. One print or electronic copy may be made for personal use only. Systematic or multiple reproduction, distribution to multiple locations via electronic or other means, duplication of any material in this paper for a fee or for commercial purposes, or modification of the content of the paper is prohibited and is subject to penalties under law.
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:SPMS Journal Articles

Files in This Item:
File Description SizeFormat 
The Excluded Minors for Isometric Realizability in the Plane.pdf445.51 kBAdobe PDFThumbnail
View/Open

SCOPUSTM   
Citations 20

1
checked on Sep 5, 2020

WEB OF SCIENCETM
Citations 20

1
checked on Oct 24, 2020

Page view(s) 20

96
checked on Oct 25, 2020

Download(s) 20

51
checked on Oct 25, 2020

Google ScholarTM

Check

Altmetric


Plumx

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.