D.I.E.I. - Università degli Studi di Perugia
h-quasi planar drawings of bounded
treewidth graphs in linear area
Emilio Di Giacomo, Walter Didimo,
Giuseppe Liotta, Fabrizio Montecchiani
University of Perugia
13th Italian Conference on Theoretical Computer Science
19-21 September 2012, Varese, Italy
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
Graph Drawing and Area Requirement
Graph G
19/09/2012
Straight-line grid drawing  of G
ICTCS ’12 - Varese, Italy
2
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
Graph Drawing and Area Requirement
w
h
Graph G
Straight-line grid drawing  of G
Area requirement of straight-line drawings is a
widely studied topic in Graph Drawing
19/09/2012
ICTCS ’12 - Varese, Italy
3
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
Area Requirement for planar drawings
• Area requirement problem mainly studied for planar straightline grid drawings:
– planar graphs have planar straight-line grid drawings in
O(n2) area (worst case optimal) [de Fraysseix et al.;
Schnyder; 1990]
– sub-quadratic upper bounds:
• trees – O(n log n) [Crescenzi et al., 1992]
• outerplanar graphs – O(n1.48) [Di Battista, Frati, 2009]
– super-linear lower bound:
• series-parallel graphs – Ω(n2√(log n)) [Frati, 2010]
19/09/2012
ICTCS ’12 - Varese, Italy
4
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
Area Requirement for planar drawings
• Planarity imposes severe limitations on the optimization
of the area
19/09/2012
ICTCS ’12 - Varese, Italy
5
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
Area Requirement for planar drawings
• Planarity imposes severe limitations on the optimization
of the area
– Non-planar straight-line drawings in O(n) area exist
for k-colorable graphs [Wood, 2005] – no guarantee
on the type and on the number of crossings
A drawing by
Wood’s technique
19/09/2012
ICTCS ’12 - Varese, Italy
6
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
Beyond planarity: crossing complexity
• Non-planar drawings should be considered:
– How can we “control” the crossing complexity of a
drawing?
19/09/2012
ICTCS ’12 - Varese, Italy
7
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
Crossing complexity measures
• Large Angle Crossing drawings (LAC) or Right Angle
Crossing drawings (RAC), [Didimo et al., 2011]
RAC drawing
19/09/2012
ICTCS ’12 - Varese, Italy
8
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
Crossing complexity measures
• h-Planar drawings: at most h crossings per edge
1-planar drawing
19/09/2012
ICTCS ’12 - Varese, Italy
9
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
Crossing complexity measures
• h-Quasi Planar drawings: at most h-1 mutually crossing
edges
3-quasi planar drawing
19/09/2012
ICTCS ’12 - Varese, Italy
10
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
The problem
• We investigate trade-offs between area requirement
and crossing complexity
• We focus on h-quasi planarity as a measure of crossing
complexity
19/09/2012
ICTCS ’12 - Varese, Italy
11
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
Our contribution 1/2
(h-quasi planar drawings)
• General technique: Every n-vertex graph with
treewidth ≤ k, has an h-quasi planar drawing in O(n) area
with h depending only on k
19/09/2012
ICTCS ’12 - Varese, Italy
12
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
Our contribution 1/2
(h-quasi planar drawings)
• General technique: Every n-vertex graph with
treewidth ≤ k, has an h-quasi planar drawing in O(n) area
with h depending only on k
• Ad-hoc techniques: Smaller values of h for specific
subfamilies of planar partial k-trees (outerplanar, flat
series-parallel, proper simply nested)
19/09/2012
ICTCS ’12 - Varese, Italy
13
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
Our contribution 2/2
(h-quasi planarity vs h-planarity)
• Comparison: There exist n-vertex series-parallel graphs
(partial 2-trees) such that every h-planar drawing
requires super-linear area for any constant h
– 11-quasi planar drawings in linear area always exist
19/09/2012
ICTCS ’12 - Varese, Italy
14
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
Our contribution 2/2
(h-quasi planarity vs h-planarity)
• Comparison: There exist n-vertex series-parallel graphs
(partial 2-trees) such that every h-planar drawing
requires super-linear area for any constant h
– 11-quasi planar drawings in linear area always exist
• Additional result: There exist n-vertex planar graphs such
that every h-planar drawing requires quadratic area for
any constant h
19/09/2012
ICTCS ’12 - Varese, Italy
15
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
What’s coming next
• Basic definitions
• Results on h-quasi planarity
• Comparison with h-planarity
• Conclusions and open problems
19/09/2012
ICTCS ’12 - Varese, Italy
16
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
BASIC DEFINITIONS
19/09/2012
ICTCS ’12 - Varese, Italy
17
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
Bounded treewidth graphs
• What’s a k-tree?
19/09/2012
ICTCS ’12 - Varese, Italy
18
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
Bounded treewidth graphs
• What’s a k-tree?
• a clique of size k is a k-tree
3-tree construction
19/09/2012
ICTCS ’12 - Varese, Italy
19
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
Bounded treewidth graphs
• What’s a k-tree?
• a clique of size k is a k-tree
• the graph obtained from a k-tree by adding a new vertex
adjacent to each vertex of a clique of size k is a k-tree
3-tree construction
19/09/2012
ICTCS ’12 - Varese, Italy
20
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
Bounded treewidth graphs
• What’s a k-tree?
• a clique of size k is a k-tree
• the graph obtained from a k-tree by adding a new vertex
adjacent to each vertex of a clique of size k is a k-tree
3-tree construction
19/09/2012
ICTCS ’12 - Varese, Italy
21
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
Bounded treewidth graphs
• What’s a k-tree?
• a clique of size k is a k-tree
• the graph obtained from a k-tree by adding a new vertex
adjacent to each vertex of a clique of size k is a k-tree
3-tree construction
19/09/2012
ICTCS ’12 - Varese, Italy
22
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
Bounded treewidth graphs
• What’s a k-tree?
• a clique of size k is a k-tree
• the graph obtained from a k-tree by adding a new vertex
adjacent to each vertex of a clique of size k is a k-tree
3-tree construction
19/09/2012
ICTCS ’12 - Varese, Italy
23
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
Bounded treewidth graphs
• What’s a k-tree?
• a clique of size k is a k-tree
• the graph obtained from a k-tree by adding a new vertex
adjacent to each vertex of a clique of size k is a k-tree
• A subgraph of a k-tree is a partial k-tree
• A graph has treewidth ≤ k  it is a partial k-tree
3-tree construction
19/09/2012
ICTCS ’12 - Varese, Italy
24
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
Track assignment
• t-track assignment of a graph G [Dujmović et al., 2004] =
t vertex coloring + total ordering <i in each color class Vi
3-track assignment
19/09/2012
ICTCS ’12 - Varese, Italy
25
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
Track assignment
• t-track assignment of a graph G [Dujmović et al., 2004] =
t vertex coloring + total ordering <i in each color class Vi
– (Vi ,<i ) = track τi , 1 ≤ i ≤ t
track
3-track assignment
19/09/2012
ICTCS ’12 - Varese, Italy
26
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
Track assignment
• t-track assignment of a graph G [Dujmović et al., 2004] =
t vertex coloring + total ordering <i in each color class Vi
– (Vi ,<i ) = track τi , 1 ≤ i ≤ t
– X-crossing = (u, v), (w, z): u,w ∈ Vi, v, z ∈ Vj , u <i w and z <j
v, for i ≠ j
X-crossing
19/09/2012
ICTCS ’12 - Varese, Italy
27
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
Track assignment
• t-track assignment of a graph G [Dujmović et al., 2004] =
t vertex coloring + total ordering <i in each color class Vi
– (Vi ,<i ) = track τi , 1 ≤ i ≤ t
– X-crossing = (u, v), (w, z): u,w ∈ Vi, v, z ∈ Vj , u <i w and z <j
v, for i ≠ j
NOT an X-crossing
19/09/2012
ICTCS ’12 - Varese, Italy
28
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
Track layout
• (c, t)-track layout of G = t-track assignment + edge c-coloring:
no two edges of the same color form an X-crossing
(2,3)-track layout
19/09/2012
ICTCS ’12 - Varese, Italy
29
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
Track layout
• (c, t)-track layout of G = t-track assignment + edge c-coloring:
no two edges of the same color form an X-crossing
(2,3)-track layout
19/09/2012
ICTCS ’12 - Varese, Italy
30
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
Track layout
• (c, t)-track layout of G = t-track assignment + edge c-coloring:
no two edges of the same color form an X-crossing
(2,3)-track layout
19/09/2012
ICTCS ’12 - Varese, Italy
31
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
THE GENERAL TECHNIQUE:
COMPUTING COMPACT H-QUASI PLANAR
DRAWINGS OF K-TREES
19/09/2012
ICTCS ’12 - Varese, Italy
32
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
Ingredients of the result
• assume to have a (c,t)-track layout: we show how to
compute a [c(t-1)+1]-quasi planar drawing in O(t3 n) area
19/09/2012
ICTCS ’12 - Varese, Italy
33
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
Ingredients of the result
• assume to have a (c,t)-track layout: we show how to
compute a [c(t-1)+1]-quasi planar drawing in O(t3 n) area
• we prove that every partial k-tree has a (2,t)-track layout
where t depends on k but it does not depend on n
19/09/2012
ICTCS ’12 - Varese, Italy
34
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
Ingredients of the result
• assume to have a (c,t)-track layout: we show how to
compute a [c(t-1)+1]-quasi planar drawing in O(t3 n) area
• we prove that every partial k-tree has a (2,t)-track layout
where t depends on k but it does not depend on n
 every partial k-tree has a O(1)-quasi planar drawing in
area O(n)
19/09/2012
ICTCS ’12 - Varese, Italy
35
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
An example
INPUT: A partial k-tree G
19/09/2012
ICTCS ’12 - Varese, Italy
36
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
An example
INPUT: A partial k-tree G
G = 2-tree
19/09/2012
ICTCS ’12 - Varese, Italy
37
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
An example
INPUT: A partial k-tree G
1. Compute a (2,tk)-track layout  of G
19/09/2012
ICTCS ’12 - Varese, Italy
38
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
An example
1)  = (2,t)-track layout of G
t=4
19/09/2012
ICTCS ’12 - Varese, Italy
39
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
An example
INPUT: A partial k-tree G
1. Compute a (2,tk)-track layout  of G
2. Construct an hk-quasi planar drawing  from 
OUTPUT: The drawing 
19/09/2012
ICTCS ’12 - Varese, Italy
40
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
An example
2)  = h-quasi planar drawing of G
h ≤ c(t-1)+1 = 2(4-1)+1 = 7
19/09/2012
ICTCS ’12 - Varese, Italy
41
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
An example
INPUT: A partial k-tree G
1. Compute a (2,tk)-track layout  of G
2. Construct an hk-quasi planar drawing  from 
OUTPUT: The drawing 
19/09/2012
ICTCS ’12 - Varese, Italy
42
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
(c,t)-track layout  h-quasi planar drawing
• Lemma 1: every n-vertex graph G admitting a (c,t)-track
layout, also admits an h-quasi planar drawing in O(t3n)
area, where h = c(t − 1) + 1
19/09/2012
ICTCS ’12 - Varese, Italy
43
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
An example
19/09/2012
ICTCS ’12 - Varese, Italy
44
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
(c,t)-track layout  h-quasi planar drawing
place the vertices
along segments
19/09/2012
ICTCS ’12 - Varese, Italy
45
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
(c,t)-track layout  h-quasi planar drawing
any edge connecting a vertex on a
segment i to a vertex on a segment j
(i < j) do not overlap with any vertex on
a segment k s.t. i < k <j
19/09/2012
ICTCS ’12 - Varese, Italy
46
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
(c,t)-track layout  h-quasi planar drawing
any edge connecting a vertex on a
segment i to a vertex on a segment j
(i < j) do not overlap with any vertex on
a segment k s.t. i < k <j
19/09/2012
ICTCS ’12 - Varese, Italy
47
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
(c,t)-track layout  h-quasi planar drawing
19/09/2012
ICTCS ’12 - Varese, Italy
48
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
(c,t)-track layout  h-quasi planar drawing
A = O(t3n)
t
O(t2n)
19/09/2012
ICTCS ’12 - Varese, Italy
49
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
(c,t)-track layout  h-quasi planar drawing:
upper bound on h
• We prove that at most c(t − 1) edges mutually cross
19/09/2012
ICTCS ’12 - Varese, Italy
50
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
(c,t)-track layout  h-quasi planar drawing:
upper bound on h
• We prove that at most c(t − 1) edges mutually cross
– every edge (u,v) with u ϵ si and v ϵ sj is completely
contained in a parallelogram Πi,j
si
parallelogram Πi,j
sj
19/09/2012
ICTCS ’12 - Varese, Italy
51
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
(c,t)-track layout  h-quasi planar drawing:
upper bound on h
at most c mutually crossing edges in
each parallelogram
19/09/2012
ICTCS ’12 - Varese, Italy
52
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
(c,t)-track layout  h-quasi planar drawing:
upper bound on h
at most c mutually crossing edges in
each parallelogram
+
at most t − 1 parallelograms
mutually overlap (to prove)
19/09/2012
ICTCS ’12 - Varese, Italy
53
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
(c,t)-track layout  h-quasi planar drawing:
upper bound on h
at most c mutually crossing edges in
each parallelogram
+
at most t − 1 parallelograms
mutually overlap (to prove)
=
at most c(t − 1) mutually
crossing edges in our drawing
19/09/2012
ICTCS ’12 - Varese, Italy
54
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
(c,t)-track layout  h-quasi planar drawing:
upper bound on h
• Simplified (but consistent) model
– segments = points
19/09/2012
ICTCS ’12 - Varese, Italy
55
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
(c,t)-track layout  h-quasi planar drawing:
upper bound on h
• Simplified (but consistent) model
– segments = points
– parallelograms = curves
19/09/2012
ICTCS ’12 - Varese, Italy
56
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
(c,t)-track layout  h-quasi planar drawing:
upper bound on h
• An overlap occurs iff
1 - two curves form a crossing
19/09/2012
ICTCS ’12 - Varese, Italy
57
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
(c,t)-track layout  h-quasi planar drawing:
upper bound on h
• An overlap occurs iff
2 - two curves share an endpoint and the other two
endpoints are either before or after the one in common
19/09/2012
ICTCS ’12 - Varese, Italy
58
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
(c,t)-track layout  h-quasi planar drawing:
upper bound on h
• Simplified (but consistent) model
– an overlap occurs iff
1 - two curves form a crossing
2 - two curves share an endpoint and the other two
endpoints are either before or after the one in common
4 mutually overlapping
parallelograms
19/09/2012
ICTCS ’12 - Varese, Italy
59
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
(c,t)-track layout  h-quasi planar drawing:
upper bound on h
• To prove: at most t − 1 parallelograms mutually overlap
• Proof by induction on t
19/09/2012
ICTCS ’12 - Varese, Italy
60
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
(c,t)-track layout  h-quasi planar drawing:
upper bound on h
• To prove: at most t − 1 parallelograms mutually overlap
• Proof by induction on t
– t = 2: one parallelogram, OK
19/09/2012
ICTCS ’12 - Varese, Italy
61
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
(c,t)-track layout  h-quasi planar drawing:
upper bound on h
• To prove: at most t − 1 parallelograms mutually overlap
• Proof by induction on t
– t = 2: one parallelogram, OK
– t > 2:
• Ot = biggest set of mutually overlapping
parallelograms in Γt
– suppose by contradiction that |Ot| > t – 1
• By induction |Ot-1| ≤ t - 2
19/09/2012
ICTCS ’12 - Varese, Italy
62
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
(c,t)-track layout  h-quasi planar drawing:
upper bound on h
1 2
i1 i2
ip ip + 1
t-1 t
• Ot = P U R
19/09/2012
ICTCS ’12 - Varese, Italy
63
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
(c,t)-track layout  h-quasi planar drawing:
upper bound on h
1 2
i1 i2
ip ip + 1
t-1 t
• P = subset of parallelograms of Ot having st as a side
– t − 2+ |P| ≥ t  |P| ≥ 2
19/09/2012
ICTCS ’12 - Varese, Italy
64
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
(c,t)-track layout  h-quasi planar drawing:
upper bound on h
1 2
i1 i2
ip ip + 1
t-1 t
• P = subset of parallelograms of Ot having st as a side
– t − 2+ |P| ≥ t  |P| ≥ 2
• R = Ot \ P
– they must have a side sj , 1 ≤ j ≤ i1 and a side sl , ip + 1
≤ l ≤ t − 1  they are present in Γt-1
– |Ot| = |R| + |P| and |Ot| ≥ t  |R| ≥ t − |P|
19/09/2012
ICTCS ’12 - Varese, Italy
65
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
(c,t)-track layout  h-quasi planar drawing:
upper bound on h
1 2
i1 i2
ip ip + 1
t-1 t
• Let ih + 1 ≤ l ≤ t − 1 be the greatest index among the segments
in R
– parallelograms Πi2,l ,…, Πip,l and all the parallelograms in R
mutually overlap
• they form a bundle of mutually overlapping
parallelograms in Γt−1 whose size is at least t − |P| + |P|
− 1 > t - 2, a contradiction, OK
19/09/2012
ICTCS ’12 - Varese, Italy
66
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
(2, tk)-track layout of k-trees
• Theorem 1: Every partial k-tree admits a (2, tk)-track
layout, where tk is given by the following set of
equations:
19/09/2012
ICTCS ’12 - Varese, Italy
67
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
Putting results together
• Theorem 2: Every partial k-tree with n vertices admits a
hk -quasi planar grid drawing in O(tk3n) area, where hk =
2(tk − 1) + 1 and tk is given by the following set of
equations:
19/09/2012
ICTCS ’12 - Varese, Italy
68
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
Some values
(1,t)-track layouts
K
1
2
3
19/09/2012
h_k (our result) h_k [Di Giacomo et al., 2005]
3
3
11
15
299
5415
ICTCS ’12 - Varese, Italy
69
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
COMPARING H-QUASI PLANARITY
WITH H-PLANARITY
19/09/2012
ICTCS ’12 - Varese, Italy
70
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
Area lower bound for h-planar drawings of partial
2-trees
• Theorem 6: Let h be a positive integer, there exist nvertex series-parallel graphs such that any h-planar
straight-line drawing requires Ω(n2√(log n)) area
• Hence, h-planarity is more restrictive than h-quasi
planarity in terms of area requirement for partial 2-trees
19/09/2012
ICTCS ’12 - Varese, Italy
71
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
Area lower bound for h-planar drawings of partial
2-trees: sketch of proof
a graph G
19/09/2012
ICTCS ’12 - Varese, Italy
72
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
Area lower bound for h-planar drawings of partial
2-trees: sketch of proof
G* = l-extension of G
l
19/09/2012
ICTCS ’12 - Varese, Italy
73
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
Area lower bound for h-planar drawings of partial
2-trees: sketch of proof
• Lemma 5: Let h be a positive integer, and let G be a
planar graph. In any h-planar drawing of the 3hextension G* of G, there are no two edges of G crossing
each other.
19/09/2012
ICTCS ’12 - Varese, Italy
74
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
Area lower bound for h-planar drawings of partial
2-trees: sketch of proof
• Lemma 5: Let h be a positive integer, and let G be a
planar graph. In any h-planar drawing of the 3hextension G* of G, there are no two edges of G crossing
each other.
u
z
if 2 edges of G cross…
w
19/09/2012
ICTCS ’12 - Varese, Italy
v
75
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
Area lower bound for h-planar drawings of partial
2-trees: sketch of proof
• Lemma 5: Let h be a positive integer, and let G be a
planar graph. In any h-planar drawing of the 3hextension G* of G, there are no two edges of G crossing
each other
u
…one vertex will be inside
a triangle
19/09/2012
z
w
ICTCS ’12 - Varese, Italy
v
76
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
Area lower bound for h-planar drawings of partial
2-trees: sketch of proof
• Lemma 5: Let h be a positive integer, and let G be a
planar graph. In any h-planar drawing of the 3hextension G* of G, there are no two edges of G crossing
each other
u
…at least one edge of the
triangle will receive h+1
crossings…!!!
19/09/2012
z
w
h
ICTCS ’12 - Varese, Italy
v
77
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
Area lower bound for h-planar drawings of partial
2-trees: sketch of proof
• Consider the n-vertex graph G of the family of seriesparallel graphs described in [Frati, 2010]
– Ω(n2√(log n)) area may be required in planar s.l.
drawings
G
19/09/2012
ICTCS ’12 - Varese, Italy
78
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
Area lower bound for h-planar drawings of partial
2-trees: sketch of proof
• Construct the 3h-extension G* of G
– n* = 3m + n = Θ(n)
– G* is a series-parallel graph
–  G must be drawn planarly in any h-planar drawing
of G*
3h
19/09/2012
G
ICTCS ’12 - Varese, Italy
79
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
Extending the lower bound to planar graphs
• Theorem 7: Let ε > 0 be given and let h(n) : N → N be a
function such that h(n) ≤ n0.5− ε ∀n ϵ N. For every n > 0 there
exists a graph G with Θ(n) vertices such that any h(n)-planar
straight-line grid drawing of G requires Ω(n1+ 2ε) area
– Ω(n2) area necessary if
h is a constant
19/09/2012
ICTCS ’12 - Varese, Italy
3h
80
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
CONCLUSIONS AND OPEN
PROBLEMS
19/09/2012
ICTCS ’12 - Varese, Italy
81
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
Conclusions and remarks
• We studied h-quasi planar drawings of partial k-trees in linear
area
– drawings with optimal area and controlled crossing
complexity
19/09/2012
ICTCS ’12 - Varese, Italy
82
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
Conclusions and remarks
• We studied h-quasi planar drawings of partial k-trees in linear
area
– drawings with optimal area and controlled crossing
complexity
• Interesting also in the case of planar graphs
– Are there h-quasi planar drawings of planar graphs in o(n2)
area where h ϵ o(n)?
19/09/2012
ICTCS ’12 - Varese, Italy
83
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
Conclusions and remarks
• We studied h-quasi planar drawings of partial k-trees in linear
area
– drawings with optimal area and controlled crossing
complexity
• Interesting also in the case of planar graphs
– Are there h-quasi planar drawings of planar graphs in o(n2)
area where h ϵ o(n)?
• O(n) area and h ϵ O(1) can be simultaneously achieved
for some families of planar graphs
19/09/2012
ICTCS ’12 - Varese, Italy
84
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
Conclusions and remarks
• We studied h-quasi planar drawings of partial k-trees in linear
area
– drawings with optimal area and controlled crossing
complexity
• Interesting also in the case of planar graphs
– Are there h-quasi planar drawings of planar graphs in o(n2)
area where h ϵ o(n)?
• O(n) area and h ϵ O(1) can be simultaneously achieved
for some families of planar graphs
• Theorem 8: Every planar graph with n vertices admits a
O(log16 n)-quasi planar grid drawing in O(n log48 n) area
19/09/2012
ICTCS ’12 - Varese, Italy
85
D.I.E.I. - Università degli Studi di Perugia
E. Di Giacomo, W. Didimo, G. Liotta, F. Montecchiani
Some open problems
• h-quasi planar drawings of planar graphs:
– is it possible to achieve both O(n) area and h ϵ O(1)?
• h-quasi planar drawings of partial k-trees:
– studying area - aspect ratio trade offs: O(n) area and
o(n) aspect ratio?
19/09/2012
ICTCS ’12 - Varese, Italy
86