Information Technology Reference
In-Depth Information
1
2
3
4
5
23
7
15
1
8
10
19
21
20
24
4
25
678910 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
(a)
12
16
2
22
56
11
3
17
13
18
9
14
26
(b)
13
13
1
2
19
3
26
1
2
19
3
26
4
4
14
14
12
12
0
0
25
25
11
11
13
13
9 10
18
9 10
18
10
10
9
9
3
3
4
4
8
8
17
17
8
8
7
7
16
24
16
24
23
23
6
6
12
12
5
5
2
2
5
5
4
4
22
22
7
7
21
21
3
3
11
11
6
6
2
2
15
15
1
1
20
20
0
0
1
1
(c)
(d)
Fig. 3. (a)-(b) A pair of graphs G 1 ,G 2 ; G 1 is a tree of depth two while G 2 is a fat caterpillar.
G 1 and G 2 have the same vertex set; each vertex has the same label in (a) and (b). (c)-(d) A
simultaneous embedding of G 1 ,G 2 .
An immediate consequence of Lemma 3 and Theorem 2 is that EAP is properly
contained in AEP (Corollary 1). Theorems 1 and 2 imply Corollary 2.
Corollary 1. EAP
AEP .
Corollary 2. Let
be a pair of graphssuch that G 1 is either a radius-2 star, an
extended degree-3 spider or ageneralized caterpillar, and G 2 is a fatcaterpillar. Then
G 1 ,G 2
G 1 ,G 2
admits aSGE.
The characterization of Theorem 2 implies that all planar graphs that are known to
be simultaneously embeddable with a strictly monotone path [4] are in fact simultane-
ously embeddable with a fat caterpillar (i.e., EAPgraphs). Moreover, EAPgraphs open
uptwofurther research directions. A first research direction is to extend to fat cater-
pillars other existing SGE results that involve paths that are not realized in a strictly
monotone fashion. A second research direction is to extend the result of Theorem 1 to
simultaneousdrawings that are not planar but where some crossing configurations are
forbidden. Regarding the first research direction, we prove below that fat caterpillars
can be used to generalize a result by Angelini et al. [3] in which it is proved that a
path and a tree of depth two always admit a SGE. As for “nearly planar” simultaneous
geometric embeddings,wedevoteSec.4toquasi planar drawings.
Theorem 3. Let
G 1 ,G 2
be a pair of graphssuch that G 1 is a tree of depth 2 and G 2
is a fatcaterpillar. Then
G 1 ,G 2
admits aSGE.
Sketch of Proof: The technique is inspired by the one described in [3]. Since G 1 is a
tree of depth 2,removing the root of G 1 we obtain a set of stars S 1 ,S 2 ,...,S h .Let
Search WWH ::




Custom Search