TY - JOUR
T1 - On simultaneous planar graph embeddings
AU - Brass, Peter
AU - Cenek, Eowyn
AU - Duncan, Cristian A.
AU - Efrat, Alon
AU - Erten, Cesim
AU - Ismailescu, Dan P.
AU - Kobourov, Stephen G.
AU - Lubiw, Anna
AU - Mitchell, Joseph S.B.
N1 - Funding Information:
✩ An extended abstract of this paper appeared in WADS 2003. * Corresponding author. E-mail addresses: [email protected] (P. Brass), [email protected] (E. Cenek), [email protected] (C.A. Duncan), [email protected] (A. Efrat), [email protected] (C. Erten), [email protected] (D.P. Ismailescu), [email protected] (S.G. Kobourov), [email protected] (A. Lubiw), [email protected] (J.S.B. Mitchell). 1 Partially supported by NSF Grant ACR-0222920. 2 Partially supported by Metron Aviation, Inc., NASA Ames Research (NAG2-1620), and the National Science Foundation (CCF-0431030, CCF-0528209).
PY - 2007/2/1
Y1 - 2007/2/1
N2 - 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. We present positive and negative results for the two versions of the problem. Among the positive results with given mapping, we show that we can embed two paths on an n×n grid, and two caterpillar graphs on a 3n×3n grid. Among the negative results with given mapping, we show that it is not always possible to simultaneously embed three paths or two general planar graphs. 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(n2)×O( n2) grid.
AB - 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. We present positive and negative results for the two versions of the problem. Among the positive results with given mapping, we show that we can embed two paths on an n×n grid, and two caterpillar graphs on a 3n×3n grid. Among the negative results with given mapping, we show that it is not always possible to simultaneously embed three paths or two general planar graphs. 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(n2)×O( n2) grid.
KW - Graph drawing
KW - Planar graphs
KW - Simultaneous visualizations
UR - http://www.scopus.com/inward/record.url?scp=84867933017&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84867933017&partnerID=8YFLogxK
U2 - 10.1016/j.comgeo.2006.05.006
DO - 10.1016/j.comgeo.2006.05.006
M3 - Article
AN - SCOPUS:84867933017
SN - 0925-7721
VL - 36
SP - 117
EP - 130
JO - Computational Geometry: Theory and Applications
JF - Computational Geometry: Theory and Applications
IS - 2
ER -