51
Morphing Planar Graph Drawings with a Polynomial Number of Steps Soroush Alamdari , Patrizio Angelini , Timothy M. Chan , Giuseppe Di Battista , Fabrizio Frati § , Anna Lubiw , Maurizio Patrignani , Vincenzo Roselli , Sahil Singla , Bryan T. Wilkinson UNIVERSITÀ DEGLI STUDI ROMA TRE §

Morphing Planar Graph Drawings with a Polynomial Number of ...compunet/www/docs/cionzo/morph-so… · Morphing Planar Graph Drawings with a Polynomial Number of Steps Soroush Alamdari

  • Upload
    others

  • View
    3

  • Download
    0

Embed Size (px)

Citation preview

Page 1: Morphing Planar Graph Drawings with a Polynomial Number of ...compunet/www/docs/cionzo/morph-so… · Morphing Planar Graph Drawings with a Polynomial Number of Steps Soroush Alamdari

Morphing Planar Graph Drawings with aPolynomial Number of Steps

Soroush Alamdari †, Patrizio Angelini ⋄, Timothy M. Chan †,Giuseppe Di Battista⋄, Fabrizio Frati§, Anna Lubiw †,

Maurizio Patrignani ⋄, Vincenzo Roselli ⋄, Sahil Singla †,Bryan T. Wilkinson †

† ⋄UNIVERSITÀ DEGLI STUDI

ROMA

TRE §

Page 2: Morphing Planar Graph Drawings with a Polynomial Number of ...compunet/www/docs/cionzo/morph-so… · Morphing Planar Graph Drawings with a Polynomial Number of Steps Soroush Alamdari

Vincenzo Roselli (Roma Tre University) Morphing Planar Graph Drawings with a Polynomial Number of Steps

Planar linear morphing steps of straight-line drawings

Planar straight-line drawing of a graph: vertices are distinct pointsof the plane and edges are non-intersecting straight-line segments

Planar linear morphing step: transformation of a planarstraight-line drawing of a graph into another planar straight-linedrawing of the same graph

moving vertices at constant speedalong straight-line trajectories

preserving planarity

. .Problem

.State of the Art

. .Our result

. . .Preliminaries

. . . . . . .Topology

. .Geometry

.Conclusions

Page 3: Morphing Planar Graph Drawings with a Polynomial Number of ...compunet/www/docs/cionzo/morph-so… · Morphing Planar Graph Drawings with a Polynomial Number of Steps Soroush Alamdari

Vincenzo Roselli (Roma Tre University) Morphing Planar Graph Drawings with a Polynomial Number of Steps

Planar linear morphing steps of straight-line drawings

Planar straight-line drawing of a graph: vertices are distinct pointsof the plane and edges are non-intersecting straight-line segments

Planar linear morphing step: transformation of a planarstraight-line drawing of a graph into another planar straight-linedrawing of the same graph

moving vertices at constant speedalong straight-line trajectories

preserving planarity

. .Problem

.State of the Art

. .Our result

. . .Preliminaries

. . . . . . .Topology

. .Geometry

.Conclusions

Page 4: Morphing Planar Graph Drawings with a Polynomial Number of ...compunet/www/docs/cionzo/morph-so… · Morphing Planar Graph Drawings with a Polynomial Number of Steps Soroush Alamdari

Vincenzo Roselli (Roma Tre University) Morphing Planar Graph Drawings with a Polynomial Number of Steps

Planar Morphings

Given two planar straight-line drawings of the same graph, a planarmorphing is a sequence of planar linear morphing stepstransforming the first drawing into the second one

. .Problem

.State of the Art

. .Our result

. . .Preliminaries

. . . . . . .Topology

. .Geometry

.Conclusions

Page 5: Morphing Planar Graph Drawings with a Polynomial Number of ...compunet/www/docs/cionzo/morph-so… · Morphing Planar Graph Drawings with a Polynomial Number of Steps Soroush Alamdari

Vincenzo Roselli (Roma Tre University) Morphing Planar Graph Drawings with a Polynomial Number of Steps

Planar Morphings

Given two planar straight-line drawings of the same graph, a planarmorphing is a sequence of planar linear morphing stepstransforming the first drawing into the second one

. .Problem

.State of the Art

. .Our result

. . .Preliminaries

. . . . . . .Topology

. .Geometry

.Conclusions

Page 6: Morphing Planar Graph Drawings with a Polynomial Number of ...compunet/www/docs/cionzo/morph-so… · Morphing Planar Graph Drawings with a Polynomial Number of Steps Soroush Alamdari

Vincenzo Roselli (Roma Tre University) Morphing Planar Graph Drawings with a Polynomial Number of Steps

Planar Morphings

Given two planar straight-line drawings of the same graph, a planarmorphing is a sequence of planar linear morphing stepstransforming the first drawing into the second one

. .Problem

.State of the Art

. .Our result

. . .Preliminaries

. . . . . . .Topology

. .Geometry

.Conclusions

Page 7: Morphing Planar Graph Drawings with a Polynomial Number of ...compunet/www/docs/cionzo/morph-so… · Morphing Planar Graph Drawings with a Polynomial Number of Steps Soroush Alamdari

Vincenzo Roselli (Roma Tre University) Morphing Planar Graph Drawings with a Polynomial Number of Steps

State of the Art

Existence of a planar morphing: O(2n) /Between any two planar drawings of a maximal planar graph(triangulation) Cairns ’44

Between any two planar drawings such that all faces areconvex polygons (preserving the convexity in each intermediatestep) Thomassen ’83

A polynomial number of planar linear morphing steps isguaranteed only for polygons

Aichholzer et al. ’11

Related settingsAllowing non-linear trajectories

Floater & Gotsman ’99, Gotsman & Surazhsky ’01,’03Allowing bent edges

orthogonal drawings Lubiw et al.’06orthogonal preserving edge directions Biedl et al. ’06general planar graphs Lubiw & Petrick ’11

. .Problem

.State of the Art

. .Our result

. . .Preliminaries

. . . . . . .Topology

. .Geometry

.Conclusions

Page 8: Morphing Planar Graph Drawings with a Polynomial Number of ...compunet/www/docs/cionzo/morph-so… · Morphing Planar Graph Drawings with a Polynomial Number of Steps Soroush Alamdari

Vincenzo Roselli (Roma Tre University) Morphing Planar Graph Drawings with a Polynomial Number of Steps

State of the Art

Existence of a planar morphing: O(2n) /Between any two planar drawings of a maximal planar graph(triangulation) Cairns ’44

Between any two planar drawings such that all faces areconvex polygons (preserving the convexity in each intermediatestep) Thomassen ’83

A polynomial number of planar linear morphing steps isguaranteed only for polygons

Aichholzer et al. ’11

Related settingsAllowing non-linear trajectories

Floater & Gotsman ’99, Gotsman & Surazhsky ’01,’03Allowing bent edges

orthogonal drawings Lubiw et al.’06orthogonal preserving edge directions Biedl et al. ’06general planar graphs Lubiw & Petrick ’11

. .Problem

.State of the Art

. .Our result

. . .Preliminaries

. . . . . . .Topology

. .Geometry

.Conclusions

Page 9: Morphing Planar Graph Drawings with a Polynomial Number of ...compunet/www/docs/cionzo/morph-so… · Morphing Planar Graph Drawings with a Polynomial Number of Steps Soroush Alamdari

Vincenzo Roselli (Roma Tre University) Morphing Planar Graph Drawings with a Polynomial Number of Steps

State of the Art

Existence of a planar morphing: O(2n) /Between any two planar drawings of a maximal planar graph(triangulation) Cairns ’44

Between any two planar drawings such that all faces areconvex polygons (preserving the convexity in each intermediatestep) Thomassen ’83

A polynomial number of planar linear morphing steps isguaranteed only for polygons

Aichholzer et al. ’11

Related settingsAllowing non-linear trajectories

Floater & Gotsman ’99, Gotsman & Surazhsky ’01,’03Allowing bent edges

orthogonal drawings Lubiw et al.’06orthogonal preserving edge directions Biedl et al. ’06general planar graphs Lubiw & Petrick ’11

. .Problem

.State of the Art

. .Our result

. . .Preliminaries

. . . . . . .Topology

. .Geometry

.Conclusions

Page 10: Morphing Planar Graph Drawings with a Polynomial Number of ...compunet/www/docs/cionzo/morph-so… · Morphing Planar Graph Drawings with a Polynomial Number of Steps Soroush Alamdari

Vincenzo Roselli (Roma Tre University) Morphing Planar Graph Drawings with a Polynomial Number of Steps

State of the Art

Existence of a planar morphing: O(2n) /Between any two planar drawings of a maximal planar graph(triangulation) Cairns ’44

Between any two planar drawings such that all faces areconvex polygons (preserving the convexity in each intermediatestep) Thomassen ’83

A polynomial number of planar linear morphing steps isguaranteed only for polygons

Aichholzer et al. ’11

Related settingsAllowing non-linear trajectories

Floater & Gotsman ’99, Gotsman & Surazhsky ’01,’03Allowing bent edges

orthogonal drawings Lubiw et al.’06orthogonal preserving edge directions Biedl et al. ’06general planar graphs Lubiw & Petrick ’11

. .Problem

.State of the Art

. .Our result

. . .Preliminaries

. . . . . . .Topology

. .Geometry

.Conclusions

Page 11: Morphing Planar Graph Drawings with a Polynomial Number of ...compunet/www/docs/cionzo/morph-so… · Morphing Planar Graph Drawings with a Polynomial Number of Steps Soroush Alamdari

Vincenzo Roselli (Roma Tre University) Morphing Planar Graph Drawings with a Polynomial Number of Steps

Our result: triangulations

.Theorem..

.

Given any two planar straight-line drawings of the sametriangulation, there exists a planar morphing between them withO(n2) planar linear morphing steps

⇝. .Problem

.State of the Art

. .Our result

. . .Preliminaries

. . . . . . .Topology

. .Geometry

.Conclusions

Page 12: Morphing Planar Graph Drawings with a Polynomial Number of ...compunet/www/docs/cionzo/morph-so… · Morphing Planar Graph Drawings with a Polynomial Number of Steps Soroush Alamdari

Vincenzo Roselli (Roma Tre University) Morphing Planar Graph Drawings with a Polynomial Number of Steps

Our result: general planar graphs

.Theorem..

.

Given any two planar straight-line drawings of the same graph,there exists a planar morphing between them with O(n4) planarlinear morphing steps

Extend the two drawings to a pair of drawings of the sametriangulation

it can be done by adding O(n2) vertices Aronov et al. ’93

Apply the algorithm for triangulations

. .Problem

.State of the Art

. .Our result

. . .Preliminaries

. . . . . . .Topology

. .Geometry

.Conclusions

Page 13: Morphing Planar Graph Drawings with a Polynomial Number of ...compunet/www/docs/cionzo/morph-so… · Morphing Planar Graph Drawings with a Polynomial Number of Steps Soroush Alamdari

Vincenzo Roselli (Roma Tre University) Morphing Planar Graph Drawings with a Polynomial Number of Steps

Our result: general planar graphs

.Theorem..

.

Given any two planar straight-line drawings of the same graph,there exists a planar morphing between them with O(n4) planarlinear morphing steps

Extend the two drawings to a pair of drawings of the sametriangulation

it can be done by adding O(n2) vertices Aronov et al. ’93

Apply the algorithm for triangulations

. .Problem

.State of the Art

. .Our result

. . .Preliminaries

. . . . . . .Topology

. .Geometry

.Conclusions

Page 14: Morphing Planar Graph Drawings with a Polynomial Number of ...compunet/www/docs/cionzo/morph-so… · Morphing Planar Graph Drawings with a Polynomial Number of Steps Soroush Alamdari

Vincenzo Roselli (Roma Tre University) Morphing Planar Graph Drawings with a Polynomial Number of Steps

Preliminaries

Kernel of a polygon P: convex set K of internal points of P having“direct visibility” to all the vertices of P

If |P| ≤ 5, then K ̸= ∅ and K ∩ V (P) ̸= ∅

kernel vertex

K ̸= ∅ K = ∅ K = P

. .Problem

.State of the Art

. .Our result

. . .Preliminaries

. . . . . . .Topology

. .Geometry

.Conclusions

Page 15: Morphing Planar Graph Drawings with a Polynomial Number of ...compunet/www/docs/cionzo/morph-so… · Morphing Planar Graph Drawings with a Polynomial Number of Steps Soroush Alamdari

Vincenzo Roselli (Roma Tre University) Morphing Planar Graph Drawings with a Polynomial Number of Steps

Preliminaries

Kernel of a polygon P: convex set K of internal points of P having“direct visibility” to all the vertices of P

If |P| ≤ 5, then K ̸= ∅ and K ∩ V (P) ̸= ∅

kernel vertex

K ̸= ∅ K = ∅ K = P

. .Problem

.State of the Art

. .Our result

. . .Preliminaries

. . . . . . .Topology

. .Geometry

.Conclusions

Page 16: Morphing Planar Graph Drawings with a Polynomial Number of ...compunet/www/docs/cionzo/morph-so… · Morphing Planar Graph Drawings with a Polynomial Number of Steps Soroush Alamdari

Vincenzo Roselli (Roma Tre University) Morphing Planar Graph Drawings with a Polynomial Number of Steps

Elementary operations

.Property (by Euler’s formula)..

.

There exists an internal vertex v whose neighbors induce a simple(without chords) polygon P, with |P| ≤ 5

Contraction:v can becontracted to akernel-neighbor v ′

Actually, v remains “suitably close” to v ′ during the morphing.Extraction:..

.

If v has been contracted to v ′, v can be extracted from v ′ andplaced on any point of the kernel of P

. .Problem

.State of the Art

. .Our result

. . .Preliminaries

. . . . . . .Topology

. .Geometry

.Conclusions

Page 17: Morphing Planar Graph Drawings with a Polynomial Number of ...compunet/www/docs/cionzo/morph-so… · Morphing Planar Graph Drawings with a Polynomial Number of Steps Soroush Alamdari

Vincenzo Roselli (Roma Tre University) Morphing Planar Graph Drawings with a Polynomial Number of Steps

Elementary operations

.Property (by Euler’s formula)..

.

There exists an internal vertex v whose neighbors induce a simple(without chords) polygon P, with |P| ≤ 5

Contraction:v can becontracted to akernel-neighbor v ′

Actually, v remains “suitably close” to v ′ during the morphing.Extraction:..

.

If v has been contracted to v ′, v can be extracted from v ′ andplaced on any point of the kernel of P

. .Problem

.State of the Art

. .Our result

. . .Preliminaries

. . . . . . .Topology

. .Geometry

.Conclusions

Page 18: Morphing Planar Graph Drawings with a Polynomial Number of ...compunet/www/docs/cionzo/morph-so… · Morphing Planar Graph Drawings with a Polynomial Number of Steps Soroush Alamdari

Vincenzo Roselli (Roma Tre University) Morphing Planar Graph Drawings with a Polynomial Number of Steps

Elementary operations

.Property (by Euler’s formula)..

.

There exists an internal vertex v whose neighbors induce a simple(without chords) polygon P, with |P| ≤ 5

Contraction:v can becontracted to akernel-neighbor v ′

Actually, v remains “suitably close” to v ′ during the morphing.Extraction:..

.

If v has been contracted to v ′, v can be extracted from v ′ andplaced on any point of the kernel of P

. .Problem

.State of the Art

. .Our result

. . .Preliminaries

. . . . . . .Topology

. .Geometry

.Conclusions

Page 19: Morphing Planar Graph Drawings with a Polynomial Number of ...compunet/www/docs/cionzo/morph-so… · Morphing Planar Graph Drawings with a Polynomial Number of Steps Soroush Alamdari

Vincenzo Roselli (Roma Tre University) Morphing Planar Graph Drawings with a Polynomial Number of Steps

Elementary operations

.Property (by Euler’s formula)..

.

There exists an internal vertex v whose neighbors induce a simple(without chords) polygon P, with |P| ≤ 5

Contraction:v can becontracted to akernel-neighbor v ′

Actually, v remains “suitably close” to v ′ during the morphing.Extraction:..

.

If v has been contracted to v ′, v can be extracted from v ′ andplaced on any point of the kernel of P

. .Problem

.State of the Art

. .Our result

. . .Preliminaries

. . . . . . .Topology

. .Geometry

.Conclusions

Page 20: Morphing Planar Graph Drawings with a Polynomial Number of ...compunet/www/docs/cionzo/morph-so… · Morphing Planar Graph Drawings with a Polynomial Number of Steps Soroush Alamdari

Vincenzo Roselli (Roma Tre University) Morphing Planar Graph Drawings with a Polynomial Number of Steps

Cairns’ algorithm: intuition

.Computational complexity... T (n) = 2T (n − 1) + O(1) =⇒ T (n) ∈ O(2n)

. .Problem

.State of the Art

. .Our result

. . .Preliminaries

. . . . . . .Topology

. .Geometry

.Conclusions

Page 21: Morphing Planar Graph Drawings with a Polynomial Number of ...compunet/www/docs/cionzo/morph-so… · Morphing Planar Graph Drawings with a Polynomial Number of Steps Soroush Alamdari

Vincenzo Roselli (Roma Tre University) Morphing Planar Graph Drawings with a Polynomial Number of Steps

Cairns’ algorithm: intuition

O(1)

contract v on v′

.Computational complexity... T (n) = 2T (n − 1) + O(1) =⇒ T (n) ∈ O(2n)

. .Problem

.State of the Art

. .Our result

. . .Preliminaries

. . . . . . .Topology

. .Geometry

.Conclusions

Page 22: Morphing Planar Graph Drawings with a Polynomial Number of ...compunet/www/docs/cionzo/morph-so… · Morphing Planar Graph Drawings with a Polynomial Number of Steps Soroush Alamdari

Vincenzo Roselli (Roma Tre University) Morphing Planar Graph Drawings with a Polynomial Number of Steps

Cairns’ algorithm: intuition

O(1) O(1)

contract v on v′ contract v on v′′

.Computational complexity... T (n) = 2T (n − 1) + O(1) =⇒ T (n) ∈ O(2n)

. .Problem

.State of the Art

. .Our result

. . .Preliminaries

. . . . . . .Topology

. .Geometry

.Conclusions

Page 23: Morphing Planar Graph Drawings with a Polynomial Number of ...compunet/www/docs/cionzo/morph-so… · Morphing Planar Graph Drawings with a Polynomial Number of Steps Soroush Alamdari

Vincenzo Roselli (Roma Tre University) Morphing Planar Graph Drawings with a Polynomial Number of Steps

Cairns’ algorithm: intuition

O(1)

O(1)

O(1)

? ?

in general v′ 6= v′′⇒ ⇒

contract v on v′ contract v on v′′

.Computational complexity... T (n) = 2T (n − 1) + O(1) =⇒ T (n) ∈ O(2n)

. .Problem

.State of the Art

. .Our result

. . .Preliminaries

. . . . . . .Topology

. .Geometry

.Conclusions

Page 24: Morphing Planar Graph Drawings with a Polynomial Number of ...compunet/www/docs/cionzo/morph-so… · Morphing Planar Graph Drawings with a Polynomial Number of Steps Soroush Alamdari

Vincenzo Roselli (Roma Tre University) Morphing Planar Graph Drawings with a Polynomial Number of Steps

Cairns’ algorithm: intuition

O(1)

O(1)

recursionT (n− 1)

O(1)

recursionT (n− 1)

in general v′ 6= v′′⇒ ⇒

contract v on v′ contract v on v′′

.Computational complexity... T (n) = 2T (n − 1) + O(1) =⇒ T (n) ∈ O(2n)

. .Problem

.State of the Art

. .Our result

. . .Preliminaries

. . . . . . .Topology

. .Geometry

.Conclusions

Page 25: Morphing Planar Graph Drawings with a Polynomial Number of ...compunet/www/docs/cionzo/morph-so… · Morphing Planar Graph Drawings with a Polynomial Number of Steps Soroush Alamdari

Vincenzo Roselli (Roma Tre University) Morphing Planar Graph Drawings with a Polynomial Number of Steps

Our idea

.Computational complexity..

.

T (n) = Tconv (n) + T (n − 1) + O(1)=⇒ T (n) polynomial if Tconv (n) polynomial

. .Problem

.State of the Art

. .Our result

. . .Preliminaries

. . . . . . .Topology

. .Geometry

.Conclusions

Page 26: Morphing Planar Graph Drawings with a Polynomial Number of ...compunet/www/docs/cionzo/morph-so… · Morphing Planar Graph Drawings with a Polynomial Number of Steps Soroush Alamdari

Vincenzo Roselli (Roma Tre University) Morphing Planar Graph Drawings with a Polynomial Number of Steps

Our idea

O(1) O(1)

.Computational complexity..

.

T (n) = Tconv (n) + T (n − 1) + O(1)=⇒ T (n) polynomial if Tconv (n) polynomial

. .Problem

.State of the Art

. .Our result

. . .Preliminaries

. . . . . . .Topology

. .Geometry

.Conclusions

Page 27: Morphing Planar Graph Drawings with a Polynomial Number of ...compunet/www/docs/cionzo/morph-so… · Morphing Planar Graph Drawings with a Polynomial Number of Steps Soroush Alamdari

Vincenzo Roselli (Roma Tre University) Morphing Planar Graph Drawings with a Polynomial Number of Steps

Our idea

O(1) O(1)

convexification

Tconv(n)

.Computational complexity..

.

T (n) = Tconv (n) + T (n − 1) + O(1)=⇒ T (n) polynomial if Tconv (n) polynomial

. .Problem

.State of the Art

. .Our result

. . .Preliminaries

. . . . . . .Topology

. .Geometry

.Conclusions

Page 28: Morphing Planar Graph Drawings with a Polynomial Number of ...compunet/www/docs/cionzo/morph-so… · Morphing Planar Graph Drawings with a Polynomial Number of Steps Soroush Alamdari

Vincenzo Roselli (Roma Tre University) Morphing Planar Graph Drawings with a Polynomial Number of Steps

Our idea

O(1)

O(1)

O(1)

recursionT (n− 1)

convexification

Tconv(n)

.Computational complexity..

.

T (n) = Tconv (n) + T (n − 1) + O(1)=⇒ T (n) polynomial if Tconv (n) polynomial

. .Problem

.State of the Art

. .Our result

. . .Preliminaries

. . . . . . .Topology

. .Geometry

.Conclusions

Page 29: Morphing Planar Graph Drawings with a Polynomial Number of ...compunet/www/docs/cionzo/morph-so… · Morphing Planar Graph Drawings with a Polynomial Number of Steps Soroush Alamdari

Vincenzo Roselli (Roma Tre University) Morphing Planar Graph Drawings with a Polynomial Number of Steps

Our idea

O(1)

O(1)

O(1)

recursionT (n− 1)

convexification

Tconv(n)

.Computational complexity..

.

T (n) = Tconv (n) + T (n − 1) + O(1)=⇒ T (n) polynomial if Tconv (n) polynomial

. .Problem

.State of the Art

. .Our result

. . .Preliminaries

. . . . . . .Topology

. .Geometry

.Conclusions

Page 30: Morphing Planar Graph Drawings with a Polynomial Number of ...compunet/www/docs/cionzo/morph-so… · Morphing Planar Graph Drawings with a Polynomial Number of Steps Soroush Alamdari

Vincenzo Roselli (Roma Tre University) Morphing Planar Graph Drawings with a Polynomial Number of Steps

Computing Tconv(n)

.Problem (Convexification)..

.

Transform the drawing of the triangulation in such a way thatvertices v ′ and v ′′ (the kernel-neighbors of v in the twocontractions) become kernel-vertices of P with a polynomialnumber of linear morphing steps

It can be done by:

contracting vertices of the graph

not belonging to the external facewithout inducing external chords on P

extracting vertices in reverse order

applying linear morphing steps to handle some special cases

. .Problem

.State of the Art

. .Our result

. . .Preliminaries

. . . . . . .Topology

. .Geometry

.Conclusions

Page 31: Morphing Planar Graph Drawings with a Polynomial Number of ...compunet/www/docs/cionzo/morph-so… · Morphing Planar Graph Drawings with a Polynomial Number of Steps Soroush Alamdari

Vincenzo Roselli (Roma Tre University) Morphing Planar Graph Drawings with a Polynomial Number of Steps

Convexification of P

.

.If |P| = 3, it is already convex!

.

.

The cases where 3 < |P| ≤ 5 have tobe handled

. .Problem

.State of the Art

. .Our result

. . .Preliminaries

. . . . . . .Topology

. .Geometry

.Conclusions

Page 32: Morphing Planar Graph Drawings with a Polynomial Number of ...compunet/www/docs/cionzo/morph-so… · Morphing Planar Graph Drawings with a Polynomial Number of Steps Soroush Alamdari

Vincenzo Roselli (Roma Tre University) Morphing Planar Graph Drawings with a Polynomial Number of Steps

Convexification of 5-gons

The problem can be reduced to the convexification of 4-gons.Non-adjacent kernel-neighbors..

.

c d

a

e

b

c

d

e

ab

c

d

e

ab

.Adjacent kernel-neighbors..

.

c d e

ab

c d e

ab

c d e

ab

. .Problem

.State of the Art

. .Our result

. . .Preliminaries

. . . . . . .Topology

. .Geometry

.Conclusions

Page 33: Morphing Planar Graph Drawings with a Polynomial Number of ...compunet/www/docs/cionzo/morph-so… · Morphing Planar Graph Drawings with a Polynomial Number of Steps Soroush Alamdari

Vincenzo Roselli (Roma Tre University) Morphing Planar Graph Drawings with a Polynomial Number of Steps

Convexification of 5-gons

The problem can be reduced to the convexification of 4-gons.Non-adjacent kernel-neighbors..

.

c d

a

e

b

c

d

e

ab

c

d

e

ab

.Adjacent kernel-neighbors..

.

c d e

ab

c d e

ab

c d e

ab

. .Problem

.State of the Art

. .Our result

. . .Preliminaries

. . . . . . .Topology

. .Geometry

.Conclusions

Page 34: Morphing Planar Graph Drawings with a Polynomial Number of ...compunet/www/docs/cionzo/morph-so… · Morphing Planar Graph Drawings with a Polynomial Number of Steps Soroush Alamdari

Vincenzo Roselli (Roma Tre University) Morphing Planar Graph Drawings with a Polynomial Number of Steps

Convexification of 5-gons

The problem can be reduced to the convexification of 4-gons.Non-adjacent kernel-neighbors..

.

c d

a

e

b

c

d

e

ab

c

d

e

ab

.Adjacent kernel-neighbors..

.

c d e

ab

c d e

ab

c d e

ab

. .Problem

.State of the Art

. .Our result

. . .Preliminaries

. . . . . . .Topology

. .Geometry

.Conclusions

Page 35: Morphing Planar Graph Drawings with a Polynomial Number of ...compunet/www/docs/cionzo/morph-so… · Morphing Planar Graph Drawings with a Polynomial Number of Steps Soroush Alamdari

Vincenzo Roselli (Roma Tre University) Morphing Planar Graph Drawings with a Polynomial Number of Steps

Convexification of 5-gons

The problem can be reduced to the convexification of 4-gons.Non-adjacent kernel-neighbors..

.

c d

a

e

b

c

d

e

ab

c

d

e

ab

.Adjacent kernel-neighbors..

.

c d e

ab

c d e

ab

c d e

ab

. .Problem

.State of the Art

. .Our result

. . .Preliminaries

. . . . . . .Topology

. .Geometry

.Conclusions

Page 36: Morphing Planar Graph Drawings with a Polynomial Number of ...compunet/www/docs/cionzo/morph-so… · Morphing Planar Graph Drawings with a Polynomial Number of Steps Soroush Alamdari

Vincenzo Roselli (Roma Tre University) Morphing Planar Graph Drawings with a Polynomial Number of Steps

Convexification of 5-gons

The problem can be reduced to the convexification of 4-gons.Non-adjacent kernel-neighbors..

.

c d

a

e

b

c

d

e

ab

c

d

e

ab

.Adjacent kernel-neighbors..

.

c d e

ab

c d e

ab

c d e

ab

. .Problem

.State of the Art

. .Our result

. . .Preliminaries

. . . . . . .Topology

. .Geometry

.Conclusions

Page 37: Morphing Planar Graph Drawings with a Polynomial Number of ...compunet/www/docs/cionzo/morph-so… · Morphing Planar Graph Drawings with a Polynomial Number of Steps Soroush Alamdari

Vincenzo Roselli (Roma Tre University) Morphing Planar Graph Drawings with a Polynomial Number of Steps

Convexification of 5-gons

The problem can be reduced to the convexification of 4-gons.Non-adjacent kernel-neighbors..

.

c d

a

e

b

c

d

e

ab

c

d

e

ab

.Adjacent kernel-neighbors..

.

c d e

ab

c d e

ab

c d e

ab

. .Problem

.State of the Art

. .Our result

. . .Preliminaries

. . . . . . .Topology

. .Geometry

.Conclusions

Page 38: Morphing Planar Graph Drawings with a Polynomial Number of ...compunet/www/docs/cionzo/morph-so… · Morphing Planar Graph Drawings with a Polynomial Number of Steps Soroush Alamdari

Vincenzo Roselli (Roma Tre University) Morphing Planar Graph Drawings with a Polynomial Number of Steps

Convexification of 4-gons

Value of a vertex: val(v) = 6− deg(v) =⇒∑

v val(v) = 12

.A contractible vertex is problematic if:..

.

it belongs to P and is not on the outerface

it is on the outer face

its contraction would induce anexternal chord on P

Sometimes we can deal with problematic vertices. . . but sometimes we cannot.

In this case the values of the problematic vertices sum up to atmost 11 =⇒ there exists a non-problematic contractible vertex.,

. .Problem

.State of the Art

. .Our result

. . .Preliminaries

. . . . . . .Topology

. .Geometry

.Conclusions

Page 39: Morphing Planar Graph Drawings with a Polynomial Number of ...compunet/www/docs/cionzo/morph-so… · Morphing Planar Graph Drawings with a Polynomial Number of Steps Soroush Alamdari

Vincenzo Roselli (Roma Tre University) Morphing Planar Graph Drawings with a Polynomial Number of Steps

Convexification of 4-gons

Value of a vertex: val(v) = 6− deg(v) =⇒∑

v val(v) = 12

.A contractible vertex is problematic if:..

.

it belongs to P and is not on the outerface

it is on the outer face

its contraction would induce anexternal chord on P

Sometimes we can deal with problematic vertices. . . but sometimes we cannot.

In this case the values of the problematic vertices sum up to atmost 11 =⇒ there exists a non-problematic contractible vertex.,

. .Problem

.State of the Art

. .Our result

. . .Preliminaries

. . . . . . .Topology

. .Geometry

.Conclusions

Page 40: Morphing Planar Graph Drawings with a Polynomial Number of ...compunet/www/docs/cionzo/morph-so… · Morphing Planar Graph Drawings with a Polynomial Number of Steps Soroush Alamdari

Vincenzo Roselli (Roma Tre University) Morphing Planar Graph Drawings with a Polynomial Number of Steps

Dealing with problematic vertices: an example

There exist at most two chord-inducing vertices:

.Inside △abc..

.

a

b

c

dx

a

b

c

x = d

.Outside △abc..

.

a

b

c

dx

a

b

c

d

x

. .Problem

.State of the Art

. .Our result

. . .Preliminaries

. . . . . . .Topology

. .Geometry

.Conclusions

Page 41: Morphing Planar Graph Drawings with a Polynomial Number of ...compunet/www/docs/cionzo/morph-so… · Morphing Planar Graph Drawings with a Polynomial Number of Steps Soroush Alamdari

Vincenzo Roselli (Roma Tre University) Morphing Planar Graph Drawings with a Polynomial Number of Steps

Dealing with problematic vertices: an example

There exist at most two chord-inducing vertices:

.Inside △abc..

.

a

b

c

dx

a

b

c

x = d

.Outside △abc..

.

a

b

c

dx

a

b

c

d

x

. .Problem

.State of the Art

. .Our result

. . .Preliminaries

. . . . . . .Topology

. .Geometry

.Conclusions

Page 42: Morphing Planar Graph Drawings with a Polynomial Number of ...compunet/www/docs/cionzo/morph-so… · Morphing Planar Graph Drawings with a Polynomial Number of Steps Soroush Alamdari

Vincenzo Roselli (Roma Tre University) Morphing Planar Graph Drawings with a Polynomial Number of Steps

Dealing with problematic vertices: an example

There exist at most two chord-inducing vertices:

.Inside △abc..

.

a

b

c

dx

a

b

c

x = d

.Outside △abc..

.

a

b

c

dx

a

b

c

d

x

. .Problem

.State of the Art

. .Our result

. . .Preliminaries

. . . . . . .Topology

. .Geometry

.Conclusions

Page 43: Morphing Planar Graph Drawings with a Polynomial Number of ...compunet/www/docs/cionzo/morph-so… · Morphing Planar Graph Drawings with a Polynomial Number of Steps Soroush Alamdari

Vincenzo Roselli (Roma Tre University) Morphing Planar Graph Drawings with a Polynomial Number of Steps

Computational Complexity

.Total number of steps...T (n) = Tconv (n) + T (n − 1) + O(1)

.

.

P(v) can be convexified in O(n): Tconv (n) ∈ O(n)

T (n) = O(n) +T (n − 1) + O(1) =⇒ T (n) ∈ O(n2)

.Contracted vertices..

.

“Suitably placed inside P”:

where?

how do they move?

. .Problem

.State of the Art

. .Our result

. . .Preliminaries

. . . . . . .Topology

. .Geometry

.Conclusions

Page 44: Morphing Planar Graph Drawings with a Polynomial Number of ...compunet/www/docs/cionzo/morph-so… · Morphing Planar Graph Drawings with a Polynomial Number of Steps Soroush Alamdari

Vincenzo Roselli (Roma Tre University) Morphing Planar Graph Drawings with a Polynomial Number of Steps

Computational Complexity

.Total number of steps...T (n) = Tconv (n) + T (n − 1) + O(1)

.

.

P(v) can be convexified in O(n): Tconv (n) ∈ O(n)

T (n) = O(n) +T (n − 1) + O(1) =⇒ T (n) ∈ O(n2)

.Contracted vertices..

.

“Suitably placed inside P”:

where?

how do they move?

. .Problem

.State of the Art

. .Our result

. . .Preliminaries

. . . . . . .Topology

. .Geometry

.Conclusions

Page 45: Morphing Planar Graph Drawings with a Polynomial Number of ...compunet/www/docs/cionzo/morph-so… · Morphing Planar Graph Drawings with a Polynomial Number of Steps Soroush Alamdari

Vincenzo Roselli (Roma Tre University) Morphing Planar Graph Drawings with a Polynomial Number of Steps

Computational Complexity

.Total number of steps...T (n) = Tconv (n) + T (n − 1) + O(1)

.

.

P(v) can be convexified in O(n): Tconv (n) ∈ O(n)

T (n) = O(n) +T (n − 1) + O(1) =⇒ T (n) ∈ O(n2)

.Contracted vertices..

.

“Suitably placed inside P”:

where?

how do they move?

. .Problem

.State of the Art

. .Our result

. . .Preliminaries

. . . . . . .Topology

. .Geometry

.Conclusions

Page 46: Morphing Planar Graph Drawings with a Polynomial Number of ...compunet/www/docs/cionzo/morph-so… · Morphing Planar Graph Drawings with a Polynomial Number of Steps Soroush Alamdari

Vincenzo Roselli (Roma Tre University) Morphing Planar Graph Drawings with a Polynomial Number of Steps

Moving contracted vertices

Contracted degree-3 and degree-4 vertices are expressed as convexcombination of their kernel-neighbors

. .Problem

.State of the Art

. .Our result

. . .Preliminaries

. . . . . . .Topology

. .Geometry

.Conclusions

Page 47: Morphing Planar Graph Drawings with a Polynomial Number of ...compunet/www/docs/cionzo/morph-so… · Morphing Planar Graph Drawings with a Polynomial Number of Steps Soroush Alamdari

Vincenzo Roselli (Roma Tre University) Morphing Planar Graph Drawings with a Polynomial Number of Steps

Moving degree-5 contracted vertices

As long as the convexity of the polygon does not change...

b

ce

a

db′

e′

e

b

e′

b′

a

b

c

e

a

d

b′

e′

When it changes...

ae′

b′b′

e′

ae′

b′

e′

ae′

b′b′

e′

. .Problem

.State of the Art

. .Our result

. . .Preliminaries

. . . . . . .Topology

. .Geometry

.Conclusions

Page 48: Morphing Planar Graph Drawings with a Polynomial Number of ...compunet/www/docs/cionzo/morph-so… · Morphing Planar Graph Drawings with a Polynomial Number of Steps Soroush Alamdari

Vincenzo Roselli (Roma Tre University) Morphing Planar Graph Drawings with a Polynomial Number of Steps

Moving degree-5 contracted vertices

As long as the convexity of the polygon does not change...

b

ce

a

db′

e′

e

b

e′

b′

a

b

c

e

a

d

b′

e′

When it changes...

ae′

b′b′

e′

ae′

b′

e′

ae′

b′b′

e′

. .Problem

.State of the Art

. .Our result

. . .Preliminaries

. . . . . . .Topology

. .Geometry

.Conclusions

Page 49: Morphing Planar Graph Drawings with a Polynomial Number of ...compunet/www/docs/cionzo/morph-so… · Morphing Planar Graph Drawings with a Polynomial Number of Steps Soroush Alamdari

Vincenzo Roselli (Roma Tre University) Morphing Planar Graph Drawings with a Polynomial Number of Steps

Moving degree-5 contracted vertices

As long as the convexity of the polygon does not change...

b

ce

a

db′

e′

e

b

e′

b′

a

b

c

e

a

d

b′

e′

When it changes...

ae′

b′b′

e′

ae′

b′

e′

ae′

b′b′

e′

. .Problem

.State of the Art

. .Our result

. . .Preliminaries

. . . . . . .Topology

. .Geometry

.Conclusions

Page 50: Morphing Planar Graph Drawings with a Polynomial Number of ...compunet/www/docs/cionzo/morph-so… · Morphing Planar Graph Drawings with a Polynomial Number of Steps Soroush Alamdari

Vincenzo Roselli (Roma Tre University) Morphing Planar Graph Drawings with a Polynomial Number of Steps

Future work

.Open problems..

.

more efficient algorithms for general planar graphs?

how to compute a morphing without augmenting thedrawings to represent a triangulation?

lower bound?planar 3-trees admit morphing in O(n), cycles in O(n2):

any other meaningful subclasses admitting “short”morphings?

.What we did in the meanwhile...Unidirectional morphings to move contracted vertices

Thank you!

. .Problem

.State of the Art

. .Our result

. . .Preliminaries

. . . . . . .Topology

. .Geometry

.Conclusions

Page 51: Morphing Planar Graph Drawings with a Polynomial Number of ...compunet/www/docs/cionzo/morph-so… · Morphing Planar Graph Drawings with a Polynomial Number of Steps Soroush Alamdari

Vincenzo Roselli (Roma Tre University) Morphing Planar Graph Drawings with a Polynomial Number of Steps

Future work

.Open problems..

.

more efficient algorithms for general planar graphs?

how to compute a morphing without augmenting thedrawings to represent a triangulation?

lower bound?planar 3-trees admit morphing in O(n), cycles in O(n2):

any other meaningful subclasses admitting “short”morphings?

.What we did in the meanwhile...Unidirectional morphings to move contracted vertices

Thank you!

. .Problem

.State of the Art

. .Our result

. . .Preliminaries

. . . . . . .Topology

. .Geometry

.Conclusions