Same here! My novel is at the intersection of two dimensions--ours and what has come to be called "faerie." Despite the fantastic name and the plethora of pointy-eared folk, though, there's no magic in that other realm and I have this whole backstory about divergent evolution and biochemical processes and alternate histories and such.
Fantasy or science fiction? I go with fantasy, because that's the tradition this story seems to derive from, but it definitely has elements of both.
Just curious, but how are you qualifying "magic?" Do you mean "no people throwing fireballs" or "no unicorns/dragons/multi-headed-sea-serpents" or what?
Game of Thrones (not YA, I know) keeps mentioning magic, but other than some creepy mojo from that red priestess, the ice zombie things, and, of course, the dragons, there isn't a whole lot of overtly fantastical elements. At least, not of the spells-and-incantation variety. (I haven't read them all yet, so perhaps something happens of which I'm not aware.)