The graph: Bitcoin mining cost per transaction leaves an ambiguity. Who pays the transaction costs?
According to the list of available charts, that chart is showing "miners revenue divided by the number of transactions". That is, it's the average amount a miner earns for each transaction they process. "Bitcoin mining cost per transaction" isn't a very good title for the chart.
So far, the vast majority of miners' earnings comes from the 50 BTC per block rewards, with a tiny fraction coming from the transaction fees paid by the people creating transactions.
So to answer your question, nobody pays the vast majority of the cost; it is created out of thin air as the reward for mining a block. You could see it that each new block generated inflates the money supply and so devalues all existing Bitcoins, in which case you could argue that everyone holding Bitcoin is paying via inflation. But the inflation is predictable, and so already priced in.
In a transaction, you pull in funds from one or more sources and send out funds to one or more places. A transaction may not send out more funds than were paid into it. The transaction fee is simply the difference between the funds sent out and the funds pulled in.
For example, look at transaction 31b39c2bed53253561f5c4957aea68644877efe7c2a9fb2f642837029de30e2a. It has five inputs, each .5 bitcoins, for 3.5 bitcoins. It has two outputs, one .01 bitcoins and one 2.48 bitcoins for 2.49 bitcoins total. So the transaction pays a fee of .01 bitcoins.
The transaction fee is paid from the transaction inputs. Each entity in the Bitcoin system can make its own decisions about transaction fees. When a transaction is formed, the program creating the transaction typically decides what the fee will be and constructs the transaction accordingly. When a server receives a transaction, it can decide if the fee is high enough to justify relaying it or it can refuse to relay it. And a miner can decide which valid transactions to include in blocks it mines based on transaction fees however it wants. The Bitcoins system does not require any agreements on transaction fees.
I know this is an old question, but in case it is useful for anyone else...
From the graph is not instantly clear to me whether how this "reward" is being calculated. But simply put, the reward a miner gets every time it successfully places a block into the blockchain is composed of 2 parts: 1) the fee that transaction originator wishes to pay to the miner and 2) the reward "the network" awards to the miner.
Focusing on the first part of the reward, a miner will include your transaction on the block he is building based on whether a) your transaction has an attractive payment offering (or fee) attached to it or b) he believes on the decentralized economy and thus is simply trying to contribute to its functioning rather than doing money, in which case he could take transactions with 0 fees attached to them. It could also be that he is just randomly selecting transactions. At the end, it is really up to the miner to decide what transactions he wants to add to the forming block. Most of the miners will select the transactions on how high the fee is; so the more you are willing to pay the miner to post your transaction, the higher the possibilities that your transaction will be posted soon into the blockchain.
Moving on to the other part of the reward for the miner, every time a miner solves the required algorithm he can claim bitcoins for his work. To do so, he attaches a new transaction to the same finished block, where he awards himself some bitcoins (currently set at 12.5 bc, but this parameter is halved every 210,000 blocks created -about every 4 years-, so it will be 6.25 after 2020 and so on).
This transaction is unique in itself because no one is sending the miner these bcs, nor they come from an ethereal pool of available bitcoins waiting for miners to claim. In that sense, yes, they are newly minted bitcoins produced out of thin air. It is worth noting at this point, though, that there is a limit to the total amount of bcs that can ever exist, which is set at 21,000,000, thus making bitcoins a "limited resource". This limit has still not been reached, what is planned to happen around the year 2140.
The validity of this final transaction rests on the fact that the other miners can validate whether he really solved the block or not. When everyone has validated this, they add this block to their own blockchain and propagate the info, effectively recognizing among the whole network composing the blockchain that this miner has now 12.5 more bitcoins to spend.
Can these newly created bitcoins help devaluate the existing coins? I guess so, just as with any normal currency when more bills and coins are created by its respective central bank. On the other hand, I also guess that people loosing their private keys and thus the funds assigned to it also counter this devaluation.
Bottom line: Who is paying for the fees of the transaction? the person requesting the transaction to be put on the blockchain. This fee can even be 0. Who is paying for the mining of the block? No one. These bcs are new and assigned to the miner at the moment.