This is a good question. Unfortunately there are several criteria by which chemists indentify whether a process is melting or not. One of them is called the Lindemann Criteria which says:
"Crystals are considered to melt, when the vibrational amplitude becomes half of the interatomic spacing in the crystal lattice."
What does it mean? Normally, at temperatures greater than 0K, atoms possess kinetic energy. Infact, temperature itself is a measure of the kinetic energy of the constituent atoms. The kinetic energy of an atom is related to the temperature as:
$$\text{Kinetic Energy}=\frac{3}{2}k\text{T}$$
where $k$ is a constant called Boltzmann Constant, with a value of $1.38×10^{-23}\text{J/mol}$. Atoms in a solid are characterized by their fixed mean positions. They only vibrate within a certain boundary around them. Since they have kinetic energy (and velocity as well), they tend to leave their current location, but repulsive forces from the other atoms push it back to its original position. In this way, you could consider atomic bonds like "little springs".
The extent to which the atom displaces itself from the mean location is called it's vibrational amplitude. As we increase temperature, the atoms will have more velocity, and can consequently displace itself further from the mean position. Lindemann defines the melting temperature as the temperature at which the amplitude becomes half of the space between two adjacent atoms of the crystal.
Yet another criteria for defining the melting point is the Born criteria that says:
"Crystals are considered to melt, when the shear modulus approaches zero"
You might wonder, what is this shear modulus? It's infact, a measure of how much tangential stress a solid object can handle, and the tangential strain caused by it. Tangential forces on an object are forces that act parallel to the surface of the object, hence the name. See the picture below that shows a tangential force applied on an originally cuboidal object:
Tangential (or shearing) stress is defined as:
$$\sigma _{shear}=\frac{F_{shear}}{A}$$
where $F_{shear}$ is the tangential (shearing) force, and $A$ denotes area of surface in question.
Considering the picture above, shearing strain would be defined as:
$$\epsilon _{shear}=\frac{\Delta x}{h}$$
There exists a unique proportionality between the stress applied and strain produced, and is given by:
$$\frac{\sigma _{shear}}{\epsilon _{shear}}=S$$
where $S$ is called the shear modulus. Its a constant for a given material and a given temperature.
In a physical sense, liquids are considered as substances that cannot withstand a tangential stress. When a tangential stress is applied, liquids simply keep on increasing the strain, even under small stress. This itself is a useful way to consider when a solid melts, when its shear modulus becomes zero!
Now, let's consider how we consider melting for the different examples that you have asked for:
Diamond: Diamond has a structure of covalent bonds arranged tetrahedrally to each carbon. Each bond has it's characteristic bond length. Applying Lindemann condition over here would be considered advisable , so that melting point is where vibrations of carbon atoms is half of the $\ce{C-C}$ bond distance. Ultimately some of the $\ce{C-C}$ would break and the molten mixture would largely consist of radicals of varying sizes, that permit free movement between themselves.
Graphite: While each layer of graphite is only weakly bonded to the other layer by van der Waals' forces, each layer (called graphene) itself is a quite a large molecule. You can consider a liquid as a large number of small molecules, so clearly graphene doesn't look like this. To melt it, you would have to break some of the $\ce{C-C}$ bonds so that we can produce small molecules that can move freely. We apply Lindemann condition in this case. The molten mixture would be similar to that of diamond.
Branched polymers: Remember how I told to consider liquids as small molecules that can move freely sliding among themselves? We consider the same thing over here. The branch bonds are comparatively weaker than the rest of the bonds in the polymer, and these are the ones that will break when heated. As far as bond-breakings are concerned, we use the Lindemann condition. While the unbranched polymers are big molecules, they are still small enough to exhibit liquid character at the high temperature required to break the branched bonds. The molten mixture would consist of the straight-chain polymers in radical forms.
