Is it allowed to include graphs in a thesis without explicit permission?

Depends on your university policies, but probably yes. There is probably a "thesis FAQ" at your graduate division that will clarify this!

I had to request permission for many separate aspects of my thesis, including sections of my own papers that were re-used, and (I think) figures from other peoples' papers.

Usually you can do this through the journal's "Request permissions" link, which takes you through Rightslink or something similar, and the cost was always zero for me. Other journals (PLOS) have explicit copyright policies which you can reference.

The risk here is that when you file your thesis, someone in the graduate division will say, "wait, this isn't from your work, do you have rights to do this?" and slow your graduation down! The only people who can tell you whether this will happen are at your university. For instance, this is a policy page for copyright at Michigan Tech: http://www.mtu.edu/gradschool/administration/academics/thesis-dissertation/copyright/use/

In USA and EU, the legal answer is yes, the Fair Use exemption for educational use should apply. (read: it clearly applies, but I am no lawyer.)

It's still pretty rude, though, so I asked for permission. I found peer-reviewed authors are pretty accommodating. Getting permission and citing appropriately removes any possible wrongdoing from inclusion.

My advice is: just ask for permission and you might also build some useful bridges in the process.