Time Machine backup painfully slow

I'm backing up two iMac's (with Time Machine) into one single 500GB USB external HD. The one machine that has the external HD plug into via USB performs the backup at a reasonable amount of time (no problem here). But the second machine, which connects to the extrenal HD via Airport (through a D-link router) performs the backup at a painfully slow rate.

I know this is not an ideal setup, but I was wondering what can be done to improve here (short of buying a second drive). Maybe if I connect the second machine to the network (router) with a ethernet cable, instead of it being wireless now? Maybe some tweaking of the network/filesharing system preferences? Or am I doomed with this setup and most definitely must look into purchasing a second drive?

TIA

BTW - On one machine I only have in use about 100GB of a 320 GB disk and it performed an initial backup in only a few minutes. On the second machine I use about 120 GB of a 160GB disk and so far about 4 hours have gone by and only 51.5GB have been backed up.

This is a different twist...and sort of defeats the whole purpose of Time Machine.

What if a plug in the external HD to machine one and perform a backup, the when it's finished I unplug from machine one and plug it on machine two and perform a back of that machine. Being that this is the first backup, which is the one hat takes the longest, then I can go back to machine one, plug the drive there and perform the incremental backups for both machines.

Will Time Machine recognize both backups being different, or will it overwrite over each other?

Just a thought...