Matched Drawings of Planar Graphs

Di Giacomo, Emilio and Didimo, Walter and van Kreveld, Marc and Liotta, Giuseppe and Speckmann, Bettina (2008) Matched Drawings of Planar Graphs. In: Graph Drawing 15th International Symposium, GD 2007, September 24-26, 2007 , pp. 183-194(Official URL:

Full text not available from this repository.


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 planar graph of some special families-such as unlabeled level planar (ULP) graphs or the family of "carousel graphs"-are always matched drawable.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-540-77537-9_19
Classifications: P Styles > P.720 Straight-line
G Algorithms and Complexity > G.490 Embeddings

Actions (login required)

View Item View Item