PhD Research under guide/advisor of a different department

Yes.

At least in the US, it is quite common for PhD students enrolled in department X to be advised by faculty in department Y, either alone or with a co-advisor in department X. Off the top of my head, I can think of PhD students in my (computer science) department who are advised or co-advised by faculty in electrical engineering, mathematics, and industrial engineering. Similarly, faculty in my department who advise PhD students in mathematics, electrical engineering, mechanical engineering, and biology.

That said, if you enroll in the PhD program in department X, you will have to satisfy the degree requirements (courses, comprehensive/qualifying exams, etc.) for department X, even if your advisor and your eventual research interests are in department Y.

I have seen co-advisors a number of times. At least three of my computer science colleagues were co-advised by biologists who were working on projects that needed complex and novel data manipulation and/or novel algorithm design (see, for instance, LUMPY: A probabilistic framework for structural variant discovery). There aren't any specific laws regarding this (at least in the U.S.), but specific university departments may have guidelines or rules regarding the practice--you would have to check with the schools you are applying to for individual policies.

If your interests bridge two departments, you should probably figure out which department you'd most likely fit into, and contact professors in that field to ask for their opinion on being co-advised. It may turn out that you need higher level mathematics to inform your physics research but that you won't be creating new math (for example), in which case you probably wouldn't need separate advisors.