Matched Drawings of Planar Graphs

Authors

  • Emilio Di Giacomo
  • Walter Didimo
  • Marc van Kreveld
  • Giuseppe Liotta
  • Bettina Speckmann

DOI:

https://doi.org/10.7155/jgaa.00193

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.

Downloads

Download data is not yet available.

Downloads

Published

2009-11-01

How to Cite

Di Giacomo, E., Didimo, W., van Kreveld, M., Liotta, G., & Speckmann, B. (2009). Matched Drawings of Planar Graphs. Journal of Graph Algorithms and Applications, 13(3), 423–445. https://doi.org/10.7155/jgaa.00193