On simultaneous planar graph embeddings

被引：0

作者：

Brass, P ^{[1
]}

Cenek, E

Duncan, CA

Efrat, A

Erten, C

Ismailescu, D

Kobourov, SG

Lubiw, A

Mitchell, JSB

机构：

[1] CUNY, Dept Comp Sci, New York, NY 10021 USA

[2] Univ Waterloo, Dept Comp Sci, Waterloo, ON N2L 3G1, Canada

[3] Univ Miami, Dept Comp Sci, Coral Gables, FL 33124 USA

[4] Univ Arizona, Dept Comp Sci, Tucson, AZ 85721 USA

[5] Hofstra Univ, Dept Math, Hempstead, NY 11550 USA

[6] SUNY Stony Brook, Dept Appl Math & Stat, Stony Brook, NY 11794 USA

来源：

ALGORITHMS AND DATA STRUCTURES, PROCEEDINGS | 2003年 / 2748卷

关键词：

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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 0(n) x 0(n) grid, and an outerplanar and general planar graph can be embedded simultaneously on an O(n(2)) x O(n(2)) grid.

引用

页码：243 / 255

页数：13

共 21 条

[1] DRAWING THE PLANAR DUAL
BERN, M
GILBERT, JR
[J]. INFORMATION PROCESSING LETTERS, 1992, 43 (01) : 7 - 13
[2] BOOK THICKNESS OF A GRAPH
BERNHART, F
KAINEN, PC
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 1979, 27 (03) : 320 - 331
[3] On embedding an outer-planar graph in a point set
Bose, P
[J]. COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2002, 23 (03): : 303 - 312
[4] REPRESENTATIONS OF PLANAR GRAPHS
BRIGHTWELL, GR
SCHEINERMAN, ER
[J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 1993, 6 (02) : 214 - 229
[5] CENEK E, THESIS U WATERLOO
[6] Chrobak M., 1996, Proceedings of the Twelfth Annual Symposium on Computational Geometry, FCRC '96, P319, DOI 10.1145/237218.237401
[7] Convex grid drawings of 3-connected planar graphs
Chrobak, M
Kant, G
[J]. INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS, 1997, 7 (03) : 211 - 223
[8] COLLBERG C, 2003, IN PRESS 1 ACM S SOF
[9] HOW TO DRAW A PLANAR GRAPH ON A GRID
DEFRAYSSEIX, H
PACH, J
POLLACK, R
[J]. COMBINATORICA, 1990, 10 (01) : 41 - 51
[10] Di Battista G., 1999, Graph Drawing: Algorithms for the Visualization of Graphs

← 1 2 3 →