Given a compact surface $F$ with non-empty boundary and a homotopy class of self-maps on $F$, we consider the problem of finding a representative which carries the minimal number of fixed points possible for the class. When $F$ is either the pants surface or the once punctured Möbius band this problem is solved by a graph map, where the graph is homotopy equivalent to $F$. A partial result is presented for the remaining two surfaces whose fundamental group is the free group on two generators.