Planar Map Graphs.

Zhi-Zhong Chen, Michelangelo Grigni, Christos H. Papadimitriou

Browse the full STOC paper archive.