A Topological Embedding of the Binary Tree into the Square Lattice
A Topological Embedding of the Binary Tree into the Square Lattice
复制标题
二叉树在方格中的拓扑嵌入
DOI：
--
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Samuel Kelly
中科院分区：
文献类型：
--
作者：
Samuel Kelly
我们证明，对于任何具有 $n$ 个顶点和最大度 $3$ 的有限树 $T$，存在 $T$ 到整数网格 $Z^2$ 的拓扑嵌入，该网格将顶点映射到顶点，并且其图像最多满足 $\frac{7}{3}n$ 个顶点。由于 Valiant 10.5555/1963635.1963641 具有更强的常数，这会恢复较弱的结果形式。我们解决了 arXiv:2112.05305 的问题 $7.7$，给出了一对图 $X,Y$ 的第一个例子，这样没有规则的映射 $X\to Y$，但 $X$ 到 $Y$ 的粗略接线轮廓线性增长。
We prove that for any finite tree $T$ with $n$ vertices and maximal degree $3$, there is a topological embedding of $T$ into the integer grid $Z^2$ which maps vertices to vertices and whose image meets at most $\frac{7}{3}n$ vertices. This recovers a weaker form of a result due to Valiant 10.5555/1963635.1963641 with stronger constants. We address question $7.7$ of arXiv:2112.05305, giving the first example of a pair of graphs $X,Y$ such that there is no regular map $X\to Y$ but the coarse wiring profile of $X$ into $Y$ grows linearly.
通过图对 (±1)-偏斜射影空间进行分类
DOI：
--
发表时间：
2021
期刊：
影响因子：
--
作者：
東谷章弘;上山健太;Kenta Ueyama;上山健太;上山健太
通讯作者：
上山健太