Abstract. A tripod with feet [Formula: see text] is obtained by six internally disjoint paths, three of them starting at a single vertex [Formula: see text] and ending at [Formula: see text], and another three of them starting at another vertex [Formula: see text] and ending at [Formula: see text]. Tripods play an important role in the proof of the two paths theorem, as well as some other structure theorems concerning rooted minors. The complete characterization of a tripod is well-known; if we cannot get such a tripod, then assuming some mild connectivity, a given graph must be embedded in a plane with [Formula: see text] in the outer face boundary. In this paper, by using the tripod result as a base, we give a structure theorem that, given four vertices [Formula: see text] in a graph [Formula: see text], guarantees a subgraph of [Formula: see text] that is homeomorphic to a subgraph of [Formula: see text] and contains at least three of [Formula: see text] as branches. This result is also motivated by the following problem: Every minimum counterexample to Hajós’ conjecture for [Formula: see text] is internally 5-connected.

This paper presents the first polynomial time algorithm to compute geodesics in a CAT(0) cubical complex in general dimension. The algorithm is a simple iterative method to update breakpoints of a path joining two points using Miller, Owen and Provan's algorithm (2015) as a subroutine. Our algorithm is applicable to any CAT(0) space in which geodesics between two close points can be computed, not limited to CAT(0) cubical complexes.