  The problem of realizing finite metric spaces in terms of weighted graphs has
many applications. For example, the mathematical and computational properties
of metrics that can be realized by trees have been well-studied and such
research has laid the foundation of the reconstruction of phylogenetic trees
from evolutionary distances. However, as trees may be too restrictive to
accurately represent real-world data or phenomena, it is important to
understand the relationship between more general graphs and distances. In this
paper, we introduce a new type of metric called a cactus metric, that is, a
metric that can be realized by a cactus graph. We show that, just as with tree
metrics, a cactus metric has a unique optimal realization. In addition, we
describe an algorithm that can recognize whether or not a metric is a cactus
metric and, if so, compute its optimal realization in $O(n^3)$ time, where $n$
is the number of points in the space.
