On Balloon Drawings of Rooted Trees

Chun-Cheng Lin and Hsu-Chun Yen

​

Dept. of Electrical Engineering,

National Taiwan University

Balloon Drawing of Rooted Trees

• Definition.

The balloon drawing of a rooted tree is a drawing having the following constraints:

• all the children of the same parent are placed on the circumference of the cycle centered at their parent,

​

• there exist no edge crossings in the drawing, and

​

• with respect to the root, the deeper an edge is, the shorter its drawing length becomes.

2

Two models of balloon drawing (I)

• The fractal model – top-down method

( Koike & Yoshihara, 1993 )

• Displaying self-similarly

​

• Evenly angle degree

​

• Edge length formula
• r_m = γ × r_m-1

​

​

3

120^o

120^o

120^o

r₁

r₂

r₃

Two models of balloon drawing (II)

• The subtree with nonuniform sizes (SNS) model

– Bottom-up method ( Carriere & Kazman, 1995 )

• Allow the subtrees with the same parent to reside in circles of different sizes

​

4

inner circle

outer circle

Comparison

• The balloon drawings of the same ordered tree under different models are given:

​

​

​

​

​

​

​

​

• The drawing based on the SNS model results in a clearer display on large subtrees than that under the fractal model.

​

5

Q. For an unordered rooted tree (i.e., changing the order of subtrees is allowed),

what is a good balloon drawing under the SNS model depend on?

the SNS model

the fractal model

A. Angular resolution and aspect ratio of angle.

Goal: optimize them.

Preliminaries

• Unordered tree
• The order of subtrees is not significant.

​

• Angular resolution ( denoted by AngResl )
• the minimum degree of two neighboring edges incident to the common vertex.
• Range: ( 0^o, 360^o )

⇒ Larger AngResl is better.

​

• Aspect ratio ( denoted by AspRatio )
• the ratio of the maximum degree to the minimum degree of the angles incident to a vertex
• Range: ( 1, ∞ )
• Smaller AspRatio approaching to one gives a more balanced display

6

Reduction to star graphs

• Definition. The balloon drawing of a star graph with children of nonuniform size is a drawing in which
• circles associated with different children of the root do not overlap, and
• all the children of the root are placed on the circumference of a circle centered at the root.

​

7

The balloon drawing

under the SNS model

(for the level zero)

(for the nozero level)

Balloon Drawing of Unordered Trees

• Changing the order of subtrees affects the angular resolution as well as the aspect ratio of the drawing.
• Example.

8

Larger AngResl and smaller AspRatio.

swap M₂ and m₂

Independence

​

​

9

Optimizing AngResl and AspRatio on each level is Independent.

Swapping any two subtrees inside the outer circle doesn’t

affect the optimization on other levels.

​

​

​

10

• Procedure 1 OptBalloonDrawing
• Order {θ₁,…,θ_n} in ascending order as

either m₁, m₂, …, m_k-1, m_k, M_k, M_k-1, …, M₂, M₁ if n is even,

or m₁, m₂, …, m_k-1, m_k, mid, M_k, M_k-1, …, M₂, M₁ if n is odd,

where m_i (resp. M_i) is the i-th minimum (resp. maximum) among all, and mid is the median if n is odd.

• Output a drawing witnessed by the following circular permutation: σ = (M₁, m₂, M₃, m₄, … (, mid) …, M₄, m₃, M₂, m₁)

​

e.g. (n = 10) (the drawing has 10 slices)

{θ₁,…,θ₁₀} ⇒ m₁ < m₂ < m₃ < m₄ < m₅ < M₅ < M₄ < M₃ < M₂ < M₁

11

M₁

M₃

m₂

M₂

m₃

m₁

M₅

m₄

m₅

M₄

• Theorem. Procedure 1 achieves optimality in angular resolution as well as in aspect ratio for star graphs.

​

• Basic idea to prove the correctness of the algorithm:
• Claim. optAngResl must be (M_i + m_i-1)/2 for some i ∈ {2,…,k}, which can be generated by Procedure 1.

​

• Similarly, the minimum of the largest angle must be

(M_j-1 + m_j)/2 for j ∈ {2,…,k}, which can be generated by Procedure 1.

​

• Since the permutation σ , generated by Procedure 1, simultaneously has both the maximum degree of the smallest angle and the minimum degree of the largest angle of any drawing, σ also witnesses the optAspRatio. Q.E.D

12

An experimental result

13

Balloon drawing with uneven angles

• Area of balloon drawing
• The size of the cycle enclosing the drawing

​

• The drawing under the SNS model may not be minimal

14

(of even angle type)

The Aspect Ratio (resp. Angular resolution) problem

• Given the initial drawing of a star graph (with uneven angles) and a real number r, determine how to flip the drawing of subtrees so that AspRatio ≤ r (resp. AngResl ≥ r).

​

15

slice 2

slice 5

slice 4

slice 3

slice 1

Matching

• Matching
• A set of edges such that any two edges shares no common node.

​

• Maximum matching
• A matching of the maximum cardinality

​

• Perfect matching
• For a graph with n nodes, the largest possible matching consists of n/2 edges

​

• The maximum matching problem for bipartite graphs with n vertices and m edges can be found in time.

16

Perfect!!

• Theorem. Both the Aspect Ratio Problem and the Angular Resolution Problem can be solved in O(n^2.5) time.

pf. Consider the Aspect Ratio Problem ; the other problem can be proved by a slight modification.

17

A₁

A₂

A₃

A₄

• Algorithm.
• Iteratively selects an pair (x,y) where x ∈ {b_i, b’_i} and y ∈ {b_{i ⊕1}, b’_{i ⊕1}} such that x+y is assumed to be the ‘smallest’ angle.
• A bipartite graph G_(x,y) is constructed in such a way that a drawing respecting the aspect ratio r exists iff G_(x,y) has a perfect matching.

Take the following example for illustration:

18

A bipartite graph G_(x,y)

Perfect matching ⇔ a balloon drawing

Delete the edges (s,t) where s + t > r ϕ

b₄

b’₄

b₁

b’₁

Local magnetic spring model

• Magnetic spring model (Sugiyama and Misue, 1995)
• The graph is placed on a global magnetic field
• Edge ⇒ magnetized spring

​

​

​

• Our local magnetic spring model

​

19

Experimental results and applications

• Experimental results

​

​

​

​

​

​

• Applications

​

20

Thank you for your attention.