[math-fun] Folding flat figures with holes

How many folds are needed to turn a square piece of paper into a flat figure with k holes? As an example, you can fold a square up into a long skinny rectangle like the wrapper a drinking straw comes in, and then bend that long skinny rectangle in lots of places to create lots of crossings (and lots of holes between the crossings). I can show that asymptotically you can get k holes with something like constant times sqrt(k) folds, but I don't know if this is best possible. Jim Propp