Portal de Periódicos da CAPES

On Simultaneous Planar Graph Embeddings

2003; Springer Science+Business Media; Linguagem: Inglês

10.1007/978-3-540-45078-8_22

1611-3349

Peter Braß, Eowyn Čenek, Christian A. Duncan, Alon Efrat, Cesim Erten, Dan Ismailescu, Stephen Kobourov, Anna Lubiw, Joseph S. B. Mitchell,

Computational Geometry and Mesh Generation

We consider the problem of simultaneous embedding of planar graphs. There are two variants of this problem, one in which the mapping between the vertices of the two graphs is given and another in which the mapping is not given. In particular, given a mapping, we show how to embed two paths on an n ×n grid, and two caterpillar graphs on a 3n ×3n grid. We show that it is not always possible to simultaneously embed three paths. If the mapping is not given, we show that any number of outerplanar graphs can be embedded simultaneously on an O(n) ×O(n) grid, and an outerplanar and general planar graph can be embedded simultaneously on an O(n 2) ×O(n 2) grid.