I know that Jewish law allows bowing to a ruler out of respect, but what if that ruler is deified by his people? For instance, would it be permissible for a Jew to bow to the Emperor of Japan, who is considered divine and a god by his people? What should one do if confronted w/ a situation where he must bow to a ruler of this "status"?

If the bowing is part of the ritual of deification, it is forbidden. If it is a bow which would be used for non deified people as well, it is permitted.