We study curves that are invariant under a birational map f:X->X of a complex projective surface X. We show that if X is a minimal rational surface and f is an algebraically stable (AS) map with first dynamical degree larger than one, then any invariant curve for f has arithmetic genus at most 1. In particular, invariant curves for AS birational maps of the projective plane must have degree 3 or less. Next we find formulas for all of the AS quadratic birational maps of the projective plan whose indeterminacy is constrained to lie on an invariant curve Q; however, we exclude the cases when Q is an irreducible curve of genus 1. Finally we study the dynamics of some of these quadratic maps. By studying the induced real maps of the real projective plane we find a class of maps exhibiting maximal entropy in its real dynamics. Also we present an example in which our strategy fails to find such a map.