To solve the general case requires that you allow for more than just polygons because you can end up with a topologically interesting shape, that is, a shape with one or more holes in it.

I have usually seen this handled by having a clock-wise polygon around the outside and zero or more counter-clock-wise polygons describing the holes. And often those are simplified by having them joined by lines contained within the shape.

So your best bet is probably to only remove a "shared" edge that appears twice in one polygon if both instances of the edge are adjacent in the list. This will remove useless internal lines (and each such removal can make a new removal possible) while preventing you from splitting your shape into two shapes (the outer edge and the hole).

The next trick is to flag shared edges that you end up being unable to remove so that you don't draw lines for those. You fill the polygon like normal but you need to just skip over self-shared edges when you go to draw a line around the border of the polygon. Even better is to draw the "internal" (self-shared) edges using the "fill" color so you don't end up with unshaded pixels when they fall too precisely onto such a line. If you draw the internal / self-shared edges before the other edges, then that is best of all (to make sure you don't have single-pixel gaps in your border line).