On simultaneous planar graph embeddings

P. Brass; E. Cenek; Christian A. Duncan; A. Efrat; C. Erten; D. Ismailescu; S. G. Kobourov; A. Lubiw; J. S.B. Mitchell

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

On simultaneous planar graph embeddings

P. Brass, E. Cenek, Christian A. Duncan, A. Efrat, C. Erten, D. Ismailescu, S. G. Kobourov, A. Lubiw, J. S.B. Mitchell

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Chapter

20 Scopus citations

Abstract

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 x n grid, and two caterpillar graphs on a 3n x 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) x O(n) grid, and an outerplanar and general planar graph can be embedded simultaneously on an O(n²) x O(n²) grid.

Original language	English (US)
Title of host publication	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Editors	Frank Dehne, Jorg-Rudiger Sack, Michiel Smid
Publisher	Springer-Verlag
Pages	243-255
Number of pages	13
ISBN (Print)	3540405453
DOIs	https://doi.org/10.1007/978-3-540-45078-8_22
State	Published - 2003

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2748
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

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

Cite this

Brass, P., Cenek, E., Duncan, C. A., Efrat, A., Erten, C., Ismailescu, D., Kobourov, S. G., Lubiw, A., & Mitchell, J. S. B. (2003). On simultaneous planar graph embeddings. In F. Dehne, J.-R. Sack, & M. Smid (Eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 243-255). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2748). Springer-Verlag. https://doi.org/10.1007/978-3-540-45078-8_22

On simultaneous planar graph embeddings. / Brass, P.; Cenek, E.; Duncan, Christian A. et al.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). ed. / Frank Dehne; Jorg-Rudiger Sack; Michiel Smid. Springer-Verlag, 2003. p. 243-255 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2748).

Research output: Chapter in Book/Report/Conference proceeding › Chapter

Brass, P, Cenek, E, Duncan, CA, Efrat, A, Erten, C, Ismailescu, D, Kobourov, SG, Lubiw, A & Mitchell, JSB 2003, On simultaneous planar graph embeddings. in F Dehne, J-R Sack & M Smid (eds), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2748, Springer-Verlag, pp. 243-255. https://doi.org/10.1007/978-3-540-45078-8_22

Brass P, Cenek E, Duncan CA, Efrat A, Erten C, Ismailescu D et al. On simultaneous planar graph embeddings. In Dehne F, Sack JR, Smid M, editors, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer-Verlag. 2003. p. 243-255. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-45078-8_22

Brass, P. ; Cenek, E. ; Duncan, Christian A. et al. / On simultaneous planar graph embeddings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). editor / Frank Dehne ; Jorg-Rudiger Sack ; Michiel Smid. Springer-Verlag, 2003. pp. 243-255 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inbook{4fbb4391f2444cfc84d39da8491a6e05,

title = "On simultaneous planar graph embeddings",

abstract = "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 x n grid, and two caterpillar graphs on a 3n x 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) x O(n) grid, and an outerplanar and general planar graph can be embedded simultaneously on an O(n2) x O(n2) grid.",

author = "P. Brass and E. Cenek and Duncan, {Christian A.} and A. Efrat and C. Erten and D. Ismailescu and Kobourov, {S. G.} and A. Lubiw and Mitchell, {J. S.B.}",

note = "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).",

year = "2003",

doi = "10.1007/978-3-540-45078-8_22",

language = "English (US)",

isbn = "3540405453",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer-Verlag",

pages = "243--255",

editor = "Frank Dehne and Jorg-Rudiger Sack and Michiel Smid",

booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

}

TY - CHAP

T1 - On simultaneous planar graph embeddings

AU - Brass, P.

AU - Cenek, E.

AU - Duncan, Christian A.

AU - Efrat, A.

AU - Erten, C.

AU - Ismailescu, D.

AU - Kobourov, S. G.

AU - Lubiw, A.

AU - Mitchell, J. 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 - 2003

Y1 - 2003

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. In particular, given a mapping, we show how to embed two paths on an n x n grid, and two caterpillar graphs on a 3n x 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) x O(n) grid, and an outerplanar and general planar graph can be embedded simultaneously on an O(n2) x 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. In particular, given a mapping, we show how to embed two paths on an n x n grid, and two caterpillar graphs on a 3n x 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) x O(n) grid, and an outerplanar and general planar graph can be embedded simultaneously on an O(n2) x O(n2) grid.

UR - http://www.scopus.com/inward/record.url?scp=35248879254&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=35248879254&partnerID=8YFLogxK

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

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

M3 - Chapter

AN - SCOPUS:35248879254

SN - 3540405453

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 243

EP - 255

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

A2 - Dehne, Frank

A2 - Sack, Jorg-Rudiger

A2 - Smid, Michiel

PB - Springer-Verlag

ER -

On simultaneous planar graph embeddings

Abstract

Publication series

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this