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.
Scheda prodotto non validato
Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo
Titolo: | Matched Drawings of Planar Graphs |
Autori: | |
Data di pubblicazione: | 2008 |
Abstract: | A natural way to draw two planar graphs whose vertex sets are matched is to assign each matched p...air 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. |
Handle: | http://hdl.handle.net/11391/31711 |
ISBN: | 9783540775362 |
Appare nelle tipologie: | 4.1 Contributo in Atti di convegno |