18 problems

For a finite point configuration $P\subset\mathbb{R}^2$, let its Steiner ratio be the ratio of the cost of an optimal Steiner tree for $P$ to the cost of a minimum spanning tree fo…

Let $S$ be an even set of points in the plane, and let $\mathcal M$ be a max-sum matching of $S$. Define $t(S)$ as the minimum, over points $y$ in the plane, of…

Let $S$ be an even set of points in the plane, and let $\{a_ib_i:i=1,\dots,n\}$ be a max-sum matching of $S$, where $|S|=2n$. A point $o$ is required to satisfy, for every matched…

Let $\mathbb{M}^n$ be a piece-wise differentiable, elliptic Minkowski space, and let $s(\mathbb{M}^n)$ denote the maximum degree of a Steiner point in a Steiner minimal tree in…

Morgan's conjecture. For all $d\geq 2$,

Let $r\in(0,1)$ and $\alpha\in(0,1/r-1)$. A regular, unit simplicial complex on $m$ vertices has constituent simplices that are regular and unit. Euclidean Steiner tree conjecture…

Let $d$ be the number of terminals in a regular simplex, and let $k\geq 1$. The construction described immediately before the claim recursively splits Steiner points and coordinate…

Let $k\geq 1$ and let $d$ satisfy … A good binary tree of height $k$ is defined recursively: a height-zero tree is a single node, and for positive height at most one child-subtree…

Let $G$ be a graph with $m$ edges, and embed each edge by its characteristic vector, as in the Vertex Cover reduction discussed in the source. Consider the Euclidean Steiner tree o…

Let $d\geq 1$, and consider finite point configurations of $d+1$ points in Euclidean space. Their Steiner ratio is the ratio of the cost of the optimal Steiner tree to the cost of…

West–Wu's conjecture. For every positive integer $k$, if $T$ is $3k$-edge-connected in $G$, then $G$ admits $k$ pairwise edge-disjoint $T$-connectors.

Let $G$ be a connected graph with at least $k$ vertices and at least $k$ edges, and let $L(G)$ be its line graph. For a set $S\subseteq V(G)$ with $|S|\geq 2$, let $\lambda_G(S)$ b…

Let an $\varepsilon$-approximate Steiner tree be a tree whose angles at Steiner points lie in $[2\pi/3-\varepsilon,2\pi/3+\varepsilon]$. For $d\geqslant 2$, let…

Let the cities be the points $\{(i,j): i,j\in\mathbb{Z}\}$ in the plane, and consider a Steiner network on this square-grid configuration. Its normalized length is its total networ…

Let $N$ be a set of terminals embedded in the Euclidean plane, and let $G$ be any tree topology on $N$ whose Steiner points have degree at least three. Fixed-topology bead-minimiza…

Let $N$ be a set of terminals embedded in the Euclidean plane, and let $T_S$ be a full Steiner minimum tree on $N$. Full-tree degeneracy conjecture. There exists a minimum Steiner…

Let $N$ be a set of $n$ terminals in a Minkowski plane $M$ with unit ball $B$, and let $T_S$ and $T_{\mathrm{opt}}$ be a $d_M$-SMT and a $d_M$-MSPT on $N$, respectively. Minkowski-…

Let $\operatorname{ssr}(\mathbb R^2)$ denote the Steiner subratio of the Euclidean plane, defined as the infimum of the ratios of minimal-filling weight to Steiner minimal-tree len…