The Importance of Being Proper - Graph Drawing - page 254

two affine transformations have been applied (i) ʓ has no crossing, (ii) every edgeis
a y -monotone curve, (iii) for i =1 ,...,k , the vertices in V i = V 3( i− 1)+1 are placed

1) + 1, that we denote by L 3( i− 1)+1 , and (iv) the order in which the
vertices in V i = V 3( i− 1)+1 appear along L 3( i− 1)+1 is the same as the order in which
they appear along L i . For each i =1 ,...,k

on line y =3( i −

E such that
ʳ ( u )= i and ʳ ( v )= i +1. Place vertices d u and d v in ʓ on the two points of the curve
representing ( u,v ) having y -coordinate equal to 3( i

− 1, consider each edge ( u,v ) ∈

1)+2 and 3 i , respectively. Then,
the curves representing in ʓ any two edges in E are part of the curves representing in
ʓ any two edges in E . Hence ʓ is a cl-planar drawing of ( V ,E ,ʳ ,T ).
Suppose that ( V ,E ,ʳ ,T ) admits a cl-planar drawing ʓ ; a cl-planar drawing ʓ of
( V,E,ʳ,T ) is constructed as follows. Initialize ʓ = ʓ .For i =1 ,...,k

−

− 1, consider

each path ( u,d u ,d v ,v ) such that ʳ ( u )=3( i 1) + 1 and ʳ ( v )=3 i +1;remove

vertices d u and d v , and their incident edges in E from ʓ ;drawedge ( u,v )

−

E in ʓ
as the composition of the curves representing edges ( u,d u ), ( d u ,d v ),and( d v ,v ) in ʓ .
Scale ʓ down by a factor of 3 and vertically translate it so that the vertices of V 1 lie on
line y =1. After the two affine transformations have been applied (i) ʓ has no crossing,
(ii) every edgeisa y -monotone curve, (iii) for i =1 ,...,k , the vertices of level V i are
placed on line y = i , and (iv) the order in which the vertices in V i = V 3( i− 1)+1 appear
along L i is the same as the order in which they appear along L 3( i− 1)+1 .Since ʓ is
cl-planar, this implies that ʓ is cl-planar, as well.
The goal of this transformation was to obtain an instance ( V ,E ,ʳ ,T ) such that,
if there exists a vertex u

∈

V j , with 1 ∈ ≤ j ≤ 3( k − 1) + 1, that is adjacent to two

V h , with h = j T ;

vertices v,w ∈ ± 1,then u , v ,and w have the same parent node μ ∈

hence, ( V ,E ,ʳ ,T ) is μ -connected between levels V j and V h .
In the second step we transform ( V ,E ,ʳ ,T ) into an equivalent level-connected
instance ( V ∗ ,E ∗ ,ʳ ∗ ,T ∗ ). Initialize ( V ∗ ,E ∗ ,ʳ ∗ ,T ∗ )=( V ,E ,ʳ ,T ). Consider each
cluster μ ∈ T according to a bottom-up visit of T . If there exists a level V i , with
ʳ min ( μ ) ≤ i<ʳ max ( μ ),such that no edgein E connects a vertex u ∈ V i ∩ V μ with
avertex v V μ , then add two vertices u ∗ and v ∗ to V ∗ , add an edge ( u ∗ ,v ∗ ) to

E ∗ ,set ʳ ∗ ( u ∗ )= i and ʳ ∗ ( v ∗ )= i +1,andadd u ∗ and v ∗ to T ∗ as children of μ .
Observe that, for each cluster μ

V i +1 ∩ ∈

T and for each level 1

∈ ≤ i ≤ 3 k − 2,atmosttwo

dummy vertices are added to ( V ∗ ,E ∗ ,ʳ ∗ ,T ∗ ).Thisimpliesthat V ∗ |∈ V |

2 )

| O ( | ∈

2 ) time.
It remains to prove that ( V ∗ ,E ∗ ,ʳ ∗ ,T ∗ ) is equivalent to ( V ,E ,ʳ ,T ).
Suppose that ( V ∗ ,E ∗ ,ʳ ∗ ,T ∗ ) admits a cl-planar drawing ʓ ∗ ; a cl-planar drawing
ʓ of ( V ,E ,ʳ ,T ) can be constructed as follows. Initialize ʓ = ʓ ∗ and remove
from V , E ,and ʓ all the vertices and edges added when constructing ʓ ∗ . Since all
the other vertices of V and edges of E have the same representation in ʓ and in ʓ ∗ ,
and since ʓ ∗ is cl-planar, it follows that ʓ is cl-planar, as well.
Suppose that ( V ,E ,ʳ ,T ) admits a cl-planar drawing ʓ ; a cl-planar drawing ʓ ∗
of ( V ∗ ,E ∗ ,ʳ ∗ ,T ∗ ) can be constructed as follows. Initialize ʓ ∗ = ʓ . Consider a level
V i , with 1

2 ). Also, the whole construction can be performed in O (

O ( | V | | V |

1),such that vertices u ∗ ,v ∗ ∈ μ with ʳ ( u ∗ )= i and ʳ ( v ∗ )=

≤ i ≤ 3( k −

T , have been added to ( V ∗ ,E ∗ ,ʳ ∗ ,T ∗ ). By construction,
( V ,E ,ʳ ,T ) is not μ -connected between levels V i and V i +1 . As observed before, this
implies that no vertex u

i +1,forsomecluster μ ∈

∈ V i ∩ V μ exists that is connected to two vertices v,w ∈ V i +1 ,