  The Severi variety parameterizes plane curves of degree d with delta nodes.
Its degree is called the Severi degree. For large enough d, the Severi degrees
coincide with the Gromov-Witten invariants of P^2. Fomin and Mikhalkin (2009)
proved the 1995 conjecture that, for fixed delta, Severi degrees are eventually
polynomial in d.
  In this paper, we study the Severi varieties corresponding to a large family
of toric surfaces. We prove the analogous result that the Severi degrees are
eventually polynomial as a function of the multidegree. More surprisingly, we
show that the Severi degrees are also eventually polynomial "as a function of
the surface". We illustrate our theorems by explicit computing, for a small
number of nodes, the Severi degree of any large enough Hirzebruch surface and
of a singular surface.
  Our strategy is to use tropical geometry to express Severi degrees in terms
of Brugalle and Mikhalkin's floor diagrams, and study those combinatorial
objects in detail. An important ingredient in the proof is the polynomiality of
the discrete volume of a variable facet-unimodular polytope.
