Information Technology Reference
In-Depth Information
f
c
e
d
e
c
3
f
b
e
2
e
d
d
f
a
a
d
1
b
b
c
c
a
b
1234 123
1234
(a)
(b)
(c)
Fig. 8. (a) Graph G 1 with R 1 = {a,d,e,f} and ˁ 1 = {d ₒ 1 ,a ₒ 2 ,e ₒ 3 ,f ₒ 4 } .
(b) Graph G 2 with R 2 = {a, b, f} and ˁ 2 = {a ₒ 1 ,bₒ 2 ,f ₒ 3 } .(c)A2-PSGEof
G 1 and G 2 where vertex set R = R 1 ∩ R 2 = {a,f} is shared.
3 Partial Simultaneous Geometric Embedding
The relation between column planarity and PSGE is expressed by the following
theorem, which relates the size of column planar sets to PSGE.
Theorem 3. Consider planar graphs G 1 =( V,E 1 ) and G 2 =( V,E 2 ) on n
vertices. If R 1 is column planar in G 1 , R 2 is column planar in G 2 and
|
R 1 |
+
|
R 2 |
>n,thenG 1 and G 2 admit a (
|
R 1 |
+
|
R 2 |−
n ) -PSGE.
Proof. Fig. 8 illustrates the construction. The set R = R 1
R 2 has size at least
|
n> 0 and is column planar in both G 1 and G 2 . More specifically,
there exist injections ˁ 1 : R
R 1 |
+
|
R 2 |−
such that R is ˁ 1 -column
planar in G 1 and ˁ 2 -column planar in G 2 . By exchanging the roles of the x -
and y -coordinates in the definition of column planar in G 2 ,weseethatforall
injections ʳ : R
R
and ˁ 2 : R
R
R
, there exists a plane straight-line embedding of G 2 that
embeds each v
R at ( ʳ ( v ) 2 ( v )). In particular, we may choose ʳ = ˁ 1 .
Two trees. Combining Theorem 3 and Theorem 1 immediately yields the fol-
lowing lower bound on the size of a PSGE of two trees.
Corollary 1. Every two trees on a set of n vertices admit an 11 n/ 17 -PSGE.
There are two trees T 1 and T 2 on 226 vertices that do not admit an SGE [14].
Thus, an upper bound on the size of the common set in a PSGE of T 1 and T 2
is 225. Root T 1 arbitrarily and let T 1 be the result of taking k copies of T 1 and
connecting their roots with a path. Define T 2 similarly. Then an upper bound on
the size of the common set in a PSGE of T 1 and T 2 is 225 k . It follows that there
exist two trees on a set of n vertices that admit no k -PSGE for k> 225 n/ 226.
Tree and ULP graph. If one of the two graphs in our PSGE is ULP, then the
size of the common set depends only on how large a column planar set we can
find in the other graph:
Lemma 3. Consider a planar graph G 1 =( V,E 1 ) and a ULP graph G 2 =
( V,E 2 ) on n vertices. If R is column planar in G 1 ,thenG 1 and G 2 admit a
|
R
|
-PSGE.
 
Search WWH ::




Custom Search