Home | Issues | About JGAA | Instructions for Authors |
Special Issue on Selected Papers from the Fifteenth International Symposium on Graph Drawing, GD 2007
DOI: 10.7155/jgaa.00193
Matched Drawings of Planar Graphs
Vol. 13, no. 3, pp. 423-445, 2009. Regular paper.
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 is 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 sufficiently restricted planar graph-such as an unlabeled level planar (ULP) graph or a graph of the
family of "carousel graphs"-are always matched drawable.
|
Submitted: December 2007.
Reviewed: May 2008.
Revised: August 2008.
Accepted: November 2008.
Final: November 2008.
Published: November 2009.
|
Journal Supporters
|