Matched Drawings of Planar Graphs

A natural way to draw two planar graphs whose vertex sets are matched is to assign each matched pair a unique y-coordinate. In this paper we introduce the concept of such matched drawings, which are a relaxation of simultaneous geometric embeddings with mapping. We study which classes of graphs allow matched drawings and show that (i) two 3-connected planar graphs or a 3-connected planar graph and a tree may not be matched drawable, while (ii) two trees or a planar graph and a su±ciently restricted planar graph|such as an unlabeled level planar (ULP) graph or a graph of the family of \carousel graphs"|are always matched drawable.