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



Titolo: Matched Drawings of Planar Graphs
Autori: 
DI GIACOMO, Emilio
DIDIMO, WALTER
LIOTTA, Giuseppe
mostra contributor esterni 
Data di pubblicazione: 2008
Abstract: 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.
Handle: http://hdl.handle.net/11391/31711
ISBN: 9783540775362
Appare nelle tipologie:4.1 Contributo in Atti di convegno

File in questo prodotto:
Non ci sono file associati a questo prodotto.
Utilizza questo identificativo per citare o creare un link a questo documento:
http://hdl.handle.net/11391/31711
  • Citazioni
  • ND

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
 
 
 
Powered by IRIS-about IRIS-Utilizzo dei cookie
Logo CINECA  Copyright © 2020