  Any system of bisectors (in the sense of abstract Voronoi diagrams) defines
an arrangement of simple curves in the plane. We define Voronoi-like graphs on
such an arrangement, which are graphs whose vertices are locally Voronoi. A
vertex $v$ is called locally Voronoi, if $v$ and its incident edges appear in
the Voronoi diagram of three sites. In a so-called admissible bisector system,
where Voronoi regions are connected and cover the plane, we prove that any
Voronoi-like graph is indeed an abstract Voronoi diagram. The result can be
seen as an abstract dual version of Delaunay's theorem on (locally) empty
circles.
  Further, we define Voronoi-like cycles in an admissible bisector system, and
show that the Voronoi-like graph induced by such a cycle $C$ is a unique tree
(or a forest, if $C$ is unbounded). In the special case where $C$ is the
boundary of an abstract Voronoi region, the induced Voronoi-like graph can be
computed in expected linear time following the technique of [Junginger and
Papadopoulou SOCG'18]. Otherwise, within the same time, the algorithm
constructs the Voronoi-like graph of a cycle $C'$ on the same set (or subset)
of sites, which may equal $C$ or be enclosed by $C$. Overall, the technique
computes abstract Voronoi (or Voronoi-like) trees and forests in linear
expected time, given the order of their leaves along a Voronoi-like cycle. We
show a direct application in updating a constraint Delaunay triangulation in
linear expected time, after the insertion of a new segment constraint,
simplifying upon the result of [Shewchuk and Brown CGTA 2015].
