Good question--I wondered about that as well. I found the graph in the Our World in Data website, which I first learned about from Steven Pinker. These specific historical data come from a 2003 paper from Cambridge by Manuel Eisner, Long-Term Historical Trends in Violent Crime, which is 60 pages long and highly detailed. Eisner is also the creator of the map in the OP. Here's a brief summary from OWID:
For earlier historical periods, researchers have reconstructed the
long-term changes in homicide rates from historical records that often
originated from some form of legal documentation of the crimes. Although
there are gaps in the reconstructed data, and there are uncertainties
in both the number of homicides and the size of the population, the
historical record is more complete than one might assume. One reason for
this is the great social importance of these crimes. Violent killings
were of concern for a long time, and they were therefore often reliably
registered. In some cases, or for prehistoric times, it is additionally
possible to use the insights from forensic archaeologists, who can
determine the causes of death from skeletal remains.
That doesn't answer all of your questions, but I think you'll find most of them addressed in the paper itself.