On the existence and optimality of some planar graph embeddings

UNIVERSITÀ DEGLI STUDI

ROMA

TRE

RomaTreUniversity

Ph.D.in Computer S ien e and Engineering

On the Existen e and Optimality

of Some Planar Graph

Embeddings

On the Existen e and Optimality of Some Planar Graph Embeddings

Athesispresentedby

PatrizioAngelini

in partialfulllmentoftherequirementsforthedegreeof

Do torofPhilosophy

inComputerS ien eandEngineering

RomaTreUniversity

Dept. ofInformati sandAutomation

Committee:

Prof. Giuseppe DiBattista

Reviewers:

Prof. AnnaLubiw

Ai mieifratelli...e arros io!

Whenthe solution issimple,Godis answering. Wherethe world easestobe

the s ene ofour personalhopesandwishes,wherewe fa eitasfree beings

admiring, askingandobserving, thereweenter the realmof ArtandS ien e.

A knowledgments

My best a knowledgments goto myadvisor GiuseppeDi Battista. Knowing

himandworkingwithhimduringmyundergraduatestudieswasaneventthat

hangedmy life,as it was the rststep towardsthe dire tion I am following

now. I thankhimfor havingtaughtme howto makeresear handfor having

transmitted tomehispassionindoingit.

Spe ialthanksgotoFabrizioBrilloFrati,hewas notjust aresear hmate

forme,buthewas myse ond advisor,heisnotjustaguyIspentmostofmy

timewithin thelastthreeyears,butheisatruefriend.

IwouldliketoalsothankMaurizioTitto Patrignani, akeyelementofthe

great atmospherewehaveinourgroup.

I would like to thank Mi hael Kaufmann for allowing me to spend four

wonderfulmonthsasaguestattheUniversityofTübingen,andJanKrato hvíl,

Mi hael Goodri h, and David Eppstein for theverypleasantand interesting

visitsI ouldmakeattheCharlesUniversityofPragueandat theUniversity

ofCalifornia,Irvine.

I would like to thank Anna Lubiw and Seok-Hee Hongfor reviewing this

thesis.

Iwouldliketo thankmy oauthorsforthegreat timeIhadwhenworking

with all of them: Lu aCittadini, Pier Fran es o Cortese, Giuseppe Di

Bat-tista, Walter Didimo, Fabrizio Frati, Markus Geyer,Lu a Grilli, Vít Jelínek,

Mi hael Kaufmann, Jan Krato hvíl, Daniel Neuwirth, Maurizio Patrignani,

Ignaz Rutter,andAntoniosSymvonis.

I thank allthe other people that madepartof our resear hgroup during

myPh.D.years,asea hofthem ontributedtomakeitagreatperiod: Guido

Drovandi, Fabrizio Martorelli,Alessandro Marzioni,BernardoPalazzi,

Maur-izio Pizzonia,TizianaRe e,MassimoRimondini,and StefanoVissi hio.

Thenalheartfelta knowledgeisformyfriendsandformyfamily. Without

Contents

Contents viii

Introdu tion 1

I Preliminaries 7

1 Graph Preliminariesand Denitions 9

1.1 Basi Denitions . . . 9

1.2 PlanarGraphs . . . 10

1.3 DrawingConventions. . . 13

1.4 FamiliesofPlanarGraphs . . . 15

2 De ompositionof PlanarGraphs 17 2.1 Conne tivity . . . 17

2.2 Data Stru turesforPlanarGraphs . . . 18

II Planar Embeddings 27 3 Topologi al Morphing ofPlanar Graphs 29 3.1 Introdu tion. . . 30

3.2 Flip andSkipOperations . . . 32

3.3 NP-Completeness oftheGeneralCase . . . 35

3.4 LinearityoftheCasewithFixedCombinatorialEmbedding . . 38

3.5 LinearityoftheCasewithoutP-nodes . . . 43

3.6 Fixed-ParameterTra tabilityoftheGeneralCase. . . 51

CONTENTS ix

4 Testing Planarity ofPartiallyEmbedded Graphs 57

4.1 Introdu tion. . . 58

4.2 NotationandPreliminaries . . . 60

4.3 CombinatorialChara terization . . . 65

4.4 Linear-TimeAlgorithm . . . 74

4.5 Generalizationsof Pep. . . 93

4.6 SimultaneousEmbeddingwithFixedEdges . . . 94

4.7 Con lusions . . . 96

5 Minimum-DepthEmbeddings 97 5.1 Introdu tion. . . 98

5.2 High-LevelDes riptionoftheAlgorithm . . . 100

5.3 PropertiesofSetsofIntegerPairs. . . 101

5.4 The Combinatorial Stru ture of PlanarEmbeddings and their Depths . . . 102

5.5 ComputingaMinimum-DepthEmbeddingofaBi onne ted Pla-narGraph . . . 112

5.6 ExtensiontoGeneralPlanarGraphs . . . 142

5.7 Con lusions . . . 144

IIIGreedy Drawings of Planar Graphs 145 6 GreedyDrawings of PlanarGraphs 147 6.1 Introdu tion. . . 148

6.2 TriangulatedBinaryCa tuses . . . 151

6.3 GreedyDrawingsofBinaryCa tuses . . . 152

6.4 SpanningaTriangulationwithaBinaryCa tus . . . 161

6.5 ExtensiontoTri onne tedPlanarGraphs . . . 174

6.6 Con lusionsandOpenProblems . . . 181

7 Su in tRepresentation ofGreedy Drawings 183 7.1 Introdu tion. . . 183

7.2 Denitions andPreliminaries . . . 185

7.3 TheLowerBound . . . 187

7.4 Drawabilityof

T

n

. . . 193

IVSimultaneous Embedding of Planar Graphs 197

8 Geometri SimultaneousEmbeddingof a Treeand a Path 199

8.1 Introdu tion. . . 200

8.2 Preliminaries . . . 201

8.3 TheCounterexample . . . 203

8.4 Overview . . . 208

8.5 DetailedProofs . . . 220

8.6 An AlgorithmfortheGeometri Simultaneous Embeddingof a TreeofDepth

2

andaPath . . . 246

8.7 Con lusions . . . 248

V Clustered Graphs 249 9

c

-Planar ClusteredGraphs 251 9.1 Clustered Graphs . . . 252

9.2 DrawingClustered Graphs. . . 253

9.3 Testing

c

-PlanarityofClustered Graphs . . . 254

10Straight-Line Re tangular Drawings ofClustered Graphs 259 10.1 Introdu tion. . . 260

10.2 Preliminaries . . . 262

10.3 Howto DrawLinearly-OrderedOuter lusteredGraphs . . . 272

10.4 Howto DrawOuter lusteredGraphs . . . 286

10.5 Howto DrawClusteredGraphs . . . 307

10.6 Con lusions . . . 316

VIPubli ations and Bibliography 317

11Other Resear hA tivities 319

Publi ations 320

Introdu tion

A graph isanabstra t mathemati alrepresentationofaset ofobje ts, alled

verti es, together with a pairwise relationship between su h obje ts, that is

representedbya olle tionofedges onne tingpairsofverti es. Examplesof

relationships among obje ts that are representable by a graph an be found

in everyeld, ranging from interpersonal relationshipsto omputernetworks

andfrom knowledgerepresentationtobioinformati s. Of ourse,thebest way

tomakesu harelationship learlyunderstandableistovisualizethegraphso

that verti esandedgesareeasilyre ognizableat humaneye. Su hanissueis

addressedin theresear held ofGraph Drawing,whi h anberegardedasa

ross between theareas of Graph Theory, Graph Algorithmi , and

Computa-tional Geometry.

InGraphDrawing,themost ommonwayto visualize agraphisto draw

ea h vertex as apoint in theplane and ea h edge as a urve onne ting the

orresponding points. The pla ement of the verti es in the plane and the

drawingof the urves should be performed in su h away that the resulting

drawingbe ni eandreadable, in thesense that theinformation des ribedby

the graphshould be possibly understandableat a glan e. Inorder to obtain

the desired ni e and readable visualization, it is important to formalize the

aestheti riteria that distinguish agood drawingfrom abad one. Then,

thegoalofGraphDrawingisto reatealgorithmsthatautomati allyprodu e

drawingsrespe tingsu h riteria.

Themostnaturalaestheti riterionthat one an think ofisprobablythe

absen e of partial or omplete overlappingamong verti esand edges, that is

alled planarity. Anotherimportant riterion that one hasto onsider when

drawingagraphistheareaofthedrawing,asadrawingwithasmallarea an

be better visualizedinside asmall s reen. Observethat, while planarity isa

property that adrawingmaysatisfy or not,thedrawingareaisameasure of

quality measures an be dened on erning the visualization of graphs,even

withthepossibilityof ombiningsomeofthem. However,the best drawing

ofagraphmightnotexist,sin edrawingsthataregoodintermsofa ertain

riteriummaybebad in termsof another.

Itis interestingtoobservethatsomeoftheaestheti riteriaof adrawing

of a graph only depend on its topologi al features, while other riteria also

depend onthegeometri alrealization. Forexample,animportanttheoremin

GraphDrawing,knownasFary'sTheorem,statesthateverygraphadmitting

aplanardrawingalsoadmitsaplanardrawinginwhi hedgesarerepresented

bystraight-linesegments. Thisimpliesthat,inordertode idewhetheragiven

graphadmits aplanar drawing, it ispossibleto study whether su h agraph

admitsaplanarembedding,thatis,a ir ularorderingoftheedgesaroundea h

vertexthat determinesnotopologi al rossingin theindu eddrawing,rather

than omputingthea tual oordinatesofthepointsrepresentingtheverti es.

Ontheotherhand,givenagraphwithaxedembedding,dierentgeometri al

realizationsmayleadto drawingswithdierentarea.

Severalnaturaland interestingtostudy questions an beformulated

on- erningtheaestheti riteriadenedforthegraphi alrepresentationofgraphs.

When onsidering agraphproperty, therst, andprobably mostnatural,

arising question is the one about the existen e of graphs satisfying su h a

propertyandofgraphsnotsatisfyingit. Ifbothpositiveandnegativeinstan es

exist,theproblem anthenbestudiedeither froma ombinatorialorfroman

algorithmi pointof view. In theformer ase, one an ask fora relationship

between the satisability of su h a property and the stru ture of the graph.

Namely,itisinterestingtounderstandwhetherthereexistsafamilyofgraphs

su h thatalland onlythegraphsbelongingto itsatisfythedesiredproperty.

Inthelatter ase,one anaskforthe omputational omplexityoftheproblem

ofde idingwhetheragivengraphsatisestheproperty.

Question1 Givenaproperty

P

, hara terizethefamilyofgraphs

F

su hthat

agraph

G

admitsadrawing (anembedding)satisfying

P

ifandonlyif

G

∈ F

.

Question2 Givenagraph

G

andaproperty

P

, whatisthetime omplexityof

de idingwhether

G

satises

P

? Also,whatisthetime omplexityof omputing

thedrawing(theembedding)of

G

satisfying

P

?

Explanatoryexamplesforthetwoproblems omefrom thestudy ofgraph

planarity. RegardingQuestion 1, afundamental theorem ongraphplanarity,

CONTENTS 3

doesnot ontainanysubgraphthat isasubdivisionofthe ompletegraph

K

5

orofthe ompletebipartitegraph

K

3,3

. Con erningQuestion2,several

linear-timeplanaritytestingalgorithmsareknownintheliterature(seeSe t.1.2for

a brief overview about planarity), so as some NP-hardness proofs related to

graph planarity, like the one on erning the problem of nding the maximal

planarsubgraphofanon-planargraph. Of ourse,thetwoproblemsareoften

stri tly related, sin e a ombinatorial hara terization for a ertain property

maydire tlyleadtoapolynomial-timealgorithmfortesting it.

Onthe otherhand, when onsidering aparti ular measureof quality ofa

drawingor ofanembedding,thetwomostnaturalquestionsare ertainlythe

one asking fortheoptimalvalueofsu hameasure amongallthegraphsofa

ertainfamilyandtheoneaskingforane ientalgorithmthatoptimizessu h

ameasureforagivengraph.

Question 3 Givenameasure

M

andafamilyofgraphs

F

,whatistheoptimal

value of

M

amongallthe graphs

G

∈ F

?

Question 4 Given agraph

G

andameasure

M

, whatis the time omplexity

of omputingadrawing(anembedding)of

G

thatisoptimalwithrespe tto

M

?

For these two questions, lear examples an be found in the ontext of

the area-minimization problem. In fa t, many results are known in Graph

Drawingaboutlower-bounds and upper-bounds for the area needed to draw

severalfamiliesofgraphsunder ertain onstraints,andsu hupper-boundsare

generallyobtainedas aresultofe ientdrawingalgorithms.

In this thesis we address and partially answer Questions 14 on several

lassesandtypesofgraphs. Wemainlydealwithplanargraphsandwithgraph

propertiesandmeasuresthatdependonthetopologyofthegraphratherthan

on itsgeometry. Wepropose algorithmsfor omputingplanarembeddings or

drawingsthatsatisfy ertainpropertiesorthatareoptimalwithrespe tto

er-tainmeasuresofquality. Also,we onsiderthesamequestionsonsimultaneous

graphdrawing problems,thatis,problemsinvolvingmorethanonegraph,and

on lusteredgraphs,thatis,graphswheretheverti esaregroupedinto lusters

bymeansofahierar hi alstru ture.

PartI of this thesisdealswith planargraphsand withthe most ommon

methods todes ribeandhandletheirplanarembeddings.

InChapter1weintrodu esomepreliminariesanddenitionsaboutplanar

InChapter2weintrodu ebasi on eptsaboutthe onne tivityofgraphs

andweillustratethemain te hniquesfordes ribingandhandlingthe

embed-dingsofplanargraphs,dependingontheirdegreeof onne tivity. Inparti ular,

we onsiderSPQR-trees,adata-stru turedes ribingthede ompositionofa

bi- onne tedgraphintoitstri onne ted omponents.

Part II dealswithproblems related to properties and qualitymeasures of

planargraphsthat onlydependontheirembedding.

InChapter 3we onsider theproblem of omparing twodierent

embed-dings ofthe samegraph in termsof theminimum numberof elementary

op-erationsthat haveto be performed in order to turn one embedding into the

other. Forthisproblem,thatwe allTopologi al Morphing,wedenethebasi

operationsthat anbeperformedtotransformanembedding,weshowthatthe

problemisNP-hardforbi onne tedplanargraphs,andwepresent

polynomial-timealgorithmsforsomemore onstrained asesthatindu eaxed-parameter

tra tablealgorithmforthegeneral ase.

In Chapter 4 we introdu e and solve a problem related to the lassi al

planarity testing and again related to the omparison between embeddings.

In fa t, given a planarembedding of a subgraph of a planar graph, we

on-sider theproblem of extendingit to aplanar embedding of thewhole graph

whilemaintainingtheembeddingofthesubgraphun hanged. Althoughmany

polynomial-time solvableproblems be ome harderwhen a partial solution is

xedinadvan e,weshowthatthisisnotthe aseforplanarity,aswedes ribe

a ombinatorial hara terizationoftheplanargraphsthatadmitanembedding

extensionandwepresentalinear-timetestingalgorithm.

In Chapter 5we dealwith the minimization of ertain distan e measures

that des ribethe quality ofa planarembedding. In parti ular, we studythe

problemof ndingaminimum-depth embedding of aplanargraph,wherethe

depth ofanembeddingisthemaximumdistan eofitsinternal fa esfromthe

externalone. Wepresentan

O(n

4

₎

-timealgorithm,improvingthebestprevious

bound,thatwas

O(n

5

_{log n)}

, obtainedbyBiensto kandMonma[BM90℄.

InPartIIIofthisthesiswedealwithgreedydrawings ofgraphs,i.e.,

draw-ingsofgraphssatisfyingaparti ularpropertythat isdened in termsof

geo-metri aldistan esbetweenverti esandisrelatedtotheee tivenessofgreedy

routing algorithmsforsensornetworks.

In Chapter 6we give preliminary denitions on greedy drawings and we

show that every tri onne ted planar graph admits a greedy drawing, hen e

provinga onje turebyPapadimitriouandRataj za .

InChapter7we onsiderarearequirementsofgreedydrawingsandweprove

CONTENTS 5

greedy-drawabletreesrequiringexponentialareainanygreedydrawing.

PartIVdealswiththesimultaneousembeddingoftwographsonthesame

set ofpointsontheplane.

InChapter8wedealwiththegeometri simultaneousembedding problem,

in whi h both graphsare required to bedrawn with straight-lineedges. We

show that there exist a tree and a path that do not admit any of su h

em-beddings. Thisproblem wasthemain openproblemin thearea,as itllsthe

gapin the ombinatorial hara terizationofthepairsofgraphsalways

admit-tingageometri simultaneousembedding. Infa t,itwas alreadyknown that

two aterpillarsalwaysadmitsu hembedding,whilethere existtwotreesnot

admittingany.

PartVdealswith lustered graphs,atypeof graphsin whi h theverti es

aregroupedintosets, alled lusters,a ordingto a ertaingivenhierar hy.

In Chapter 9, we give some preliminaries and denitions about lustered

graphs and the problem of de iding whether a lustered graph admits a

c

-planar drawing, that is,aplanardrawingin whi h someplanarity onstraints

are required also for the graphi al representation of the lusters. The

om-plexity of su h a problem is unknown in the general ase, while there exist

hara terizationsande ientalgorithmsforsomeparti ular lassesofgraphs.

Also,wedeneageneralizationoftheproblem,in whi h lusters an besplit

in ordertomakethe lusteredgraph

c

-planar.

InChapter10wedealwiththeproblemofdrawing lusteredgraphsni ely.

Inthis ontext,weshowthatevery

c

-planar lusteredgraphadmitsa

straight-line

c

-planardrawinginwhi h lustersarerepresentedbyaxis-parallel

re tan-gles. Asthesameresultholds forany onvexshapexedin advan e, we an

statethatthe

c

-planarityof lusteredgraphsisindependentonthegeometri al

representation ofthe lusters, so as Fary's Theorem statesthat theplanarity

Part I

Chapter 1

Graph Preliminaries and

Denitions

Inthis hapter,weintrodu esomepreliminariesanddenitionsaboutgraphs,

theirembeddings, andtheirdrawings.

A reader who wants to assume more familiarity with the basi on epts

about graphs, algorithms, and geometry, may referto books onGraph

The-ory(e.g.,[Har72,BM76,NC88,Die05℄),tobooksonAlgorithms(e.g.,[Eve79,

AHU83,CLRS01,GT02℄),andtobooksonComputationalGeometry(e.g.,[PS85,

Ede87,dvKOS00℄). Referen ebooks ontainingdetaileddenitions,basi

on- epts,andmostimportantresultsaboutGraphDrawing analsobeusefuland

interestingtoread[DETT99, KW01,NR04℄.

The hapteris organizedas follows. InSe t. 1.1 wegivebasi denitions

aboutgraphs. InSe t.1.2wedealwithplanargraphsandplanarembeddings;

inSe t.1.3wedes ribethemaindrawing onventionsusedinGraphDrawing;

nally, inSe t.1.4wedene someinterestingsub lassesofplanargraphs.

1.1 Basi Denitions

Agraph

G = (V, E)

is omposedofaset

V

ofverti es ornodes,andamultiset

E

of unordered pairs of verti es, alled edges or ar s. If thepairs of verti es

in

E

areordered,

G

isadire tedgraph,alsoreferredtoasdigraph. Thegraph

obtainedfromadigraph

G

by onsideringitsedgeswithoutorientationis alled

theunderlyinggraph of

G

. Givenanedge

e = (u, v)

∈ E

,wesaythat

u

and

v

u

and

v

. Also,wesaythattwoverti esareadja ent iftheyarein identtothe

sameedge,andtwoedgesareadja ent iftheyarein identtothesamevertex.

A self-loop in agraph

G = (V, E)

is anedge

(u, u)

∈ E

. Aset ofmultiple

edges in a graph

(V, E)

is a set of edges onne ting the same two verti es

u, v

_{∈ V}

. Agraphissimple ifit ontainsneitherself-loopsnormultipleedges.

Inthefollowing,unlessotherwisespe ied,wealwaysrefertosimplegraphs.

A graph

G = (V, E)

is omplete if forea hpair ofverti es

u, v

∈ V

, edge

(u, v)

_{∈ E}

. A graphis bipartite if

V

an be partitionedinto twosets

V

1

and

V

2

su hthat forea hedge

(u, v)

∈ E

, either

u

∈ V

1

and

v

∈ V

2

orvi e versa.

Agraph

G = (V, E)

isbipartite ifitsvertexset

V

an bepartitioned intotwo

subsets

V

1

and

V

2

sothat everyedge of

E

isin identtoavertexof

V

1

andto

avertexof

V

2

.

Thedegreeof avertex isthenumberofedgesin identtoit. Thedegreeof

agraph isthemaximumamongthedegreesofitsverti es.

A graph

G

′

_{= (V}

′

_{, E}

′

₎

isasubgraph ofagraph

G = (V, E)

if

V

′

_{⊆ V}

and

E

′

_{⊆ E}

. Wesaythat

G

′

_{= (V}

′

_{, E}

′

₎

isindu ed by

V

′

if,forea hedge

(u, v)

∈ E

su h that

u, v

∈ V

′

, wehave

(u, v)

∈ E

′

. Also,

G

′

_{= (V}

′

_{, E}

′

₎

is a spanning

subgraph of

G = (V, E)

ifitisasubgraphof

G

and

V

′

_{= V}

.

Asubdivision ofagraph

G

isagraph

G

′

that anbeobtainedbyrepla ing

ea h edge of

G

with apath of arbitrarylength. The ontra tion of an edge

(u, v)

onsists of the repla ement of

u

,

v

, and

(u, v)

with asingle vertex

w

,

ofea h edge

(u, z)

with an edge

(w, z)

, and ofea h edge

(v, z

′

₎

with anedge

(w, z

′

₎

. Aminor ofagraph

G

isanygraphthat anbeobtainedfrom

G

bya

sequen eofremovalsofverti es,removalsofedges,and ontra tionsofedges.

1.2 Planar Graphs

Inthisse tionwegivepreliminariesanddenitionsaboutplanargraphs.

A drawing of agraph is a mappingof ea h vertex to a distin t point of

theplaneandofea hedgeto asimpleopenJordan urvebetweenthepoints

towhi htheend-verti esoftheedgehavebeenmapped. A drawingisplanar

if no two edges interse t ex ept, possibly, at ommon end-points. A planar

graph is a graph admitting a planar drawing. A planar drawingof a graph

determinesa ir ularorderingof theedgesin ident toea hvertex

v

,that we

alltherotations heme of

v

. Twodrawingsofthesamegraphareequivalent

iftheydeterminethesamerotations hemeforea hvertex. Fig.1.1showstwo

equivalentdrawingsofaplanargraph. A ombinatorial embedding (orsimply

1.2. PLANARGRAPHS 11

equivalentlya ombinatorialembedding,partitionstheplaneintotopologi ally

onne ted regions alled fa es. A vertex (an edge) is in ident to a fa e if it

belongstothe y ledelimitingthefa e. Allthefa esareboundedbythe y le

delimitingthem, ex eptforonefa e,thatwe allouterfa e (orexternalfa e).

Theotherfa esare alledinternalfa es. Aplanarembedding

hΓ, fi

ofagraph

G

is omposed of anembedding

Γ

of

G

andof anouter fa e

f

of

Γ

. Aplane

graph isagraphwithaxedplanarembedding.

8

4

1

2

5

3

9

7

6

8

2

5

3

9

7

6

4

1

(a) (b)

Figure1.1: Twoequivalentplanardrawingsofaplanargraph.

Aplanegraphismaximal (orequivalentlyisatriangulation)ifallitsfa es

are delimited by y les of three verti es. A planar graph is maximal if it

admits aplanar embedding that determines atriangulation. A triangulation

is maximal in the sense that adding anedge to it yields anon-planargraph.

Maximal planar graphsare an importantand deeply studied lass of planar

graphssin eanyplanargraph anbeaugmentedtomaximalbyaddingdummy

edges to itand sin etriangulations,as thetri onne tedplanargraphs,admit

exa tly one ombinatorial embedding (a more detailed dis ussion about the

propertiesof highly- onne ted planargraphsis givenin Se t. 2.1)and hen e

areofteneasiertodealwith. Aplanegraphisinternally-triangulated whenall

itsinternalfa es haveexa tlythree in identverti es.

Thedualgraphofanembeddedplanargraph

G

hasavertexforea hfa eof

G

andanedge

(f, g)

forea htwofa es

f

and

g

of

G

sharinganedge. Fig.1.2

showsanembeddedplanargraphanditsdualgraph. Thedualgraphof

G

only

dependsontheembeddingof

G

andnotonthe hoi eoftheexternalfa e.

Planarity

Planarity is ommonly a epted as the most important aestheti riteria a

drawingshouldsatisfytobeni eandreadable. Infa t,theabsen eofpartialor

ompleteoverlappingamongtheobje tsmakesthedrawingaestheti ally

read-Figure1.2: Aplanargraph,whoseverti esarerepresentedbybla k ir lesand

whoseedgesarerepresentedbythi klines, anditsdualgraph,whoseverti es

are represented by white ir les and whose edges are represented by dotted

lines.

abilityofthe ombinatorialstru ture ofthegraph,as onrmedbysome

og-nitiveexperiments ingraphvisualization[PCJ97, Pur00,PCA02, WPCM02℄.

See Fig. 1.3 for a omparison between a non-planar and a planar drawing.

However,the great importan e of planar graphs, so in GraphDrawingas in

GraphTheoryand Computational Geometryin general,also omes fromthe

manymathemati al, ombinatorial,andgeometri alpropertiestheyexhibit.

6

4

1

2

5

3

8

9

7

₃

2

8

7

9

4

1

5

6

(a) (b)

Figure 1.3: (a) A non-planar drawing of a planar graph

G

. (b) A planar

drawingof

G

.

Fromthe ombinatorialand topologi alpointof view,therst important

resultaboutplanargraphsisthe hara terizationgivenbyKuratowski[Kur30℄

in

1930

,statingthatagraphisplanarifandonlyifit ontainsnosubdivision

ofthe ompletegraph

K

5

withveverti esandnosubdivisionofthe omplete

bipartitegraph

K

3,3

withthree verti esin ea hof thesets ofthebipartition.

Su ha hara terizationhasbeenextendedbyWagner,whostatedthatagraph

isplanarifandonlyifit ontainsno

K

5

-minorandno

K

3,3

-minor[Wag37℄. The

planarityofagraph anbetestedinlineartime,asrstshownbyHop roftand

1.3. DRAWINGCONVENTIONS 13

grapharealsopresented,e.g.,in[BL76,ET76,dR82,BM04,dFdMR06,HT08℄.

Also, su h testing algorithms an be suitably modied in order to ompute

planarembeddingsinthe asethetestispositive. Ifanembeddingofagraph

isxed,thenlineartimestillsu estotestiftheembeddingisplanar[Kir88℄.

Thefa tthattheplanaritytesting,soasmanyotherproblemsonplanargraphs,

anbesolvedinlineartimeisduetoanotherimportantmathemati alproperty

ofplanargraphs,statingthatthenumberofedgesofaplanargraphislinearin

thenumberofitsverti es. Namely,bytheEuler'sformula,wehave

m

≤ 3n−6

,

where

m

isthenumberofedges,inany

n

-vertexplanargraph.

1.3 Drawing Conventions

Whenaimingathighreadabilityofadrawing,anotherimportantissuethathas

tobe onsidered on ernsthegeometri alrepresentationoftheedgesandofthe

fa es. Namely,planardrawingsinwhi hedgesarerepresentedbystraight-line

segments(knownasstraight-linedrawings,seeFigs.1.4(a)and( ))happento

bemorereadable thandrawingsin whi h edges arerepresentedby poly-lines

(known aspoly-linedrawings,seeFig.1.4(b))orgeneral urves,anddrawings

in whi h fa es aredrawn as onvexpolygons(known as onvex drawings, see

Fig.1.4( ))aremorereadablethandrawingsinwhi h thisisnotthe ase(see

Fig.1.4(a)). Amongthe moreused andstudied drawing onventions,wealso

mentionorthogonal drawings,in whi hea hedgeisrepresentedbyasequen e

ofhorizontal andverti alsegments.

3

2

8

7

9

4

1

5

6

6

8

5

3

1

2

4

9

7

6

4

1

2

5

3

8

9

7

(a) (b) ( )

Figure 1.4: (a) A straight-line planar drawing of a planar graph

G

. (b) A

poly-lineplanardrawingof

G

. ( )A onvexdrawingof

G

.

Otherdrawing onventionsthatareworthtomentionarethegriddrawings,

in whi h verti esand bends haveinteger oordinates, upwarddrawings of

di-graphs,inwhi hea h edgeisrepresentedbya urvemonotoni ally-in reasing

ofproximity, theproximity graph ofaset ofpointsisthegraphwithavertex

forea hpointof theset, and withan edgebetween twoverti esifthe

orre-spondingpointssatisfytheproximityproperty. Then,aproximitydrawingof

agraph

G

is a drawing

D

of

G

su h that the proximity graphof the set of

pointsonwhi htheverti esof

G

are drawnin

D

oin ides with

G

itself. An

exampleofproximitygraphsistheDelaunaytriangulation foraset

P

ofpoints

in the plane, that is, a triangulation

T

su h that nopointin

P

is inside the

ir ums ribed ir leofanytrianglein

T

.

The moststudied and used drawing onventionis the one of straight-line

drawings. Of oursesu ha onventionismu h morerestri tivethan theone

inwhi hedges anhavebends,andhen emanyresultsthatholdforpoly-line

drawingsdonotholdforstraight-linedrawings. However,regardingplanarity,

this is not the ase. Indeed, averyimportant result, known as Fary's

theo-rem and independently proved by Wagner [Wag36℄, by Fary [Far48℄, and by

Stein[Ste51℄,statesthat agraphadmitsastraight-lineplanardrawingifand

onlyifit admitsaplanardrawing. This resultshowsthat planarity doesnot

depend on the geometry used for representingthe edges but it onlydepends

onthetopologi alpropertiesofthegraph.

Someaestheti riteria anbedenedtomeasurethequalityofadrawing.

Among them, one of the most important is ertainly the area o upied by

the drawing, that is, the area of the smallest re tangle with sides parallel

to the oordinate axes that ontains all the drawing. Of ourse, small area

drawings an notbeobtainedbysimplys alingdownthedrawing,sin esome

resolutionruleshavetoberespe tedinthedrawingformaintainingreadability.

Inparti ular,aminimumdistan e,sayoneunit,betweentwoelements(verti es

andedges) ofthe drawinghasto bemaintained. In order torespe tsomeof

su hrules,whendealingwithareaminimizationproblems,verti esareusually

pla edonanintegergrid, in su hawaythat theminimum distan e between

anytwoof themisat leastonegridunit. Inthisdire tion,ithasbeenshown

inseveralpapersthatevery

n

-vertexplanegraphadmitsaplanarstraight-line

drawingon a

O(n

2

₎

areagrid[dPP88, dPP90,S h90, CN98, ZH03, BFM07℄.

Further,agridofquadrati sizeisasymptoti allythebestpossiblefor

straight-lineplanardrawings,sin ethereexist planargraphsrequiringsu h anareain

1.4. FAMILIES OFPLANARGRAPHS 15

1.4 Families of Planar Graphs

Inthis se tionwepresentpreliminariesanddenitions aboutsomeimportant

sub- lassesofplanargraphsthat willbeusedin therest ofthethesis.

A y le is a onne ted graph su h that ea h vertex has degree exa tly

two. A tree is a onne ted a y li (i.e., not ontainingany y le) graph(see

Fig.1.5(a)). Apath isatreesu hthatea hvertexhasdegreeatmosttwo. A

hord ofa y le(ofapath)isanedge onne tingtwonon- onse utiveverti es

of the y le (of the path). A leaf of a tree is a node of degree one. A leaf

edge isanedgein identto aleaf. A aterpillar (seeFig.1.5(b))isatreesu h

thatremovingalltheleavesandalltheleafedgesyieldsapath, alledspine of

the aterpillar,whose nodesandedgesare alledspine nodesandspine edges,

respe tively. Astargraph (seeFig.1.5( ))isatreesu hthatremovingallthe

leavesandalltheleafedgesyieldsanisolatednode, alled entralnode.

r

(a) (b) ( )

Figure1.5: (a)Atreerootedatanode

r

. (b)A aterpillar. ( )A stargraph.

Arootedtree isatreewithonedistinguishednode, alledroot. Inarooted

tree, thedepth ofanode

v

is thelengthof theuniquepath (i.e.,the number

of edges omposing thepath)between

v

andtheroot. Thedepth ofarooted

treeisthemaximumdepthamongalltheverti es.

A binarytree (aternary tree)isarooted treesu h that ea h nodehas at

most two hildren(resp. three hildren). Atree is ordered ifan order ofthe

hildren of ea h node (i.e., a planar embedding) is spe ied. In an ordered

binarytree wedistinguishtheleft andtheright hild ofanode. Thesubtrees

of anode

u

of atree

T

arethe subtrees of

T

rootedat

u

and not ontaining

therootof

T

.

Anouterplanargraph isagraphadmittinganouterplanarembedding, that

is, an embedding in whi h all the verti es are on the outer fa e. From a

ombinatorialpointofview,anouterplanargraphisagraphthat ontainsno

K

4

-minorandno

K

2,3

-minor(seeFig.1.6(a)).

2

1

v=v

k

v=u

₁

u=u

_k

1

2

k

1

u=u=u =...=u

2

v=v=v =...=v

(a) (b) ( )

Figure1.6: (a) An outerplanargraph. (b)Aseries ompositionof asequen e

G

1

, G

2

, . . . , G

k

of series-parallel graphs. ( ) A parallel omposition of a set

G

1

, G

2

, . . . , G

k

ofseries-parallelgraphs.

aseries-parallelgraph with poles

u

and

v

. Denote by

u

i

and

v

i

thepoles of

aseries-parallelgraph

G

i

. A series omposition of asequen e

G

1

, . . . , G

k

of

series-parallelgraphs,with

k

≥ 2

,isaseries-parallelgraphwithpoles

u = u

1

and

v = v

k

su hthat

v

i

and

u

i+1

havebeenidentied,forea h

i = 1, . . . , k

− 1

(seeFig.1.6(b)). A parallel omposition of aset

G

1

, . . . , G

k

ofseries-parallel

graphs,with

k

≥ 2

,isaseries-parallelgraphwithpoles

u = u

1

=

· · · = u

k

and

v = v

1

=

· · · = v

k

(see Fig. 1.6 ( )). From a ombinatorial point of view, a

series-parallelgraphisagraphthat ontainsno

K

4

-minor.

AHamiltonian y le (path)inagraph

G

isasimple y le(resp. path)

pass-ingthroughalltheverti esof

G

. A Hamiltonian graph is agraph ontaining

Chapter 2

De omposition of Planar Graphs

Inthis hapterwestudytheproblemofde omposingplanargraphsinto

om-ponentswithhigherdegreeof onne tivityandwepresentthemaindata

stru -tures that an be used to deal with su h de omposition and to des ribe and

handle the embeddings of planar graphs. In parti ular, we des ribe

SPQR-trees, adata stru turethat an beusedto representandto e ientlyhandle

alltheembeddingsofabi onne tedplanargraph.

Thestru tureof the hapter isas follows. InSe t. 2.1wegivesomebasi

denitionsabout onne tivityandaboutsomepropertiesthataredependingon

thedegreeof onne tivity,whileinSe t.2.2wedenethemaindatastru tures

to des ribethede ompositionintobi onne ted andtri onne ted omponents,

withparti ularfo usontheSPQR-trees.

2.1 Conne tivity

Let

G = (V, E)

beaplanargraph. Wesaythat

G

is onne ted if,forea hpair

of verti es

u, v

∈ V

, there exists apath onne ting

u

and

v

. Moregenerally,

wesaythat

G

is

k

- onne ted if,forea hpairofverti es

u, v

∈ V

,thereexist

k

disjointpaths onne ting

u

and

v

. Alternatively,wesaythat

G

is

k

- onne ted

if removingany

k

− 1

verti esleaves

G

onne ted;

3

- onne ted,

2

- onne ted,

and

1

- onne ted graphs are also alled tri onne ted, bi onne ted, and simply

onne ted graphs,respe tively. Aseparating

k

-set is aset of

k

verti eswhose

removal dis onne ts the graph. Separating

1

-sets and separating

2

-sets are

also alled utverti es and separation pairs, respe tively. Hen e, a onne ted

no separationpairs. The maximal bi onne ted subgraphs of agraph are its

blo ks, while the maximal tri onne ted subgraphs of a graph are its

tri on-ne ted omponents. Ea h edge of

G

falls into asingle blo k of

G

and into a

singletri onne ted omponent, while utverti es (resp., verti esbelonging to

aseparationpair)aresharedbydierentblo ks(resp.,bydierentseparation

pairs). A utofagraph

G = (V, E)

isapartitionifitsverti esintotwosubsets

V

1

and

V

2

. A utset of

G

isthe set

E

′

⊆ E

su h that

(u, v)

∈ E

′

ifandonly

if

u

∈ V

1

and

v

∈ V

2

. Observethat the removal of the edges of

E

′

from

E

in reasesthenumberof onne ted omponentsof

G

.

Conne tivity and Embeddings

Inthissubse tionwegivesomepropertiesofplanargraphsandplanar

embed-dingsthatdependonthedegreeof onne tivityofthegraph.

First,observethat every

3

- onne tedplanargraphadmitstwoplanar

em-beddings, whi h onlydier for aipping around theirpoles, that is, thelist

of in ident edges around ea h vertex in the two embeddings are one the

re-versal of the other. Hen e, problems on erning the resear h of aparti ular

embedding of aplanargraphthat aredi ult forgeneralplanar graphs, an

be e iently solved when the graph is tri onne ted. This property strongly

motivatesthe study of problems on low- onne ted planargraphsin termsof

theirde ompositionintohighly- onne ted omponents,astheproblem anbe

solvedmoreeasily onsu h omponentsand thentheproblems turns intothe

one of putting them together e iently. Examples of su h problems are the

subje tofthe haptersofthenextpartofthisthesis.

Anotherimportantpropertyregardinghighly onne tedgraphsisthatevery

4

- onne tedplanargraphisHamiltonian[Tut56℄andtheHamiltonian y le an

befounde iently. ObservethattheproblemofndingaHamiltonian y lein

ageneralplanargraph,eveniftri onne ted,isNP-hard[GJ79℄. Further,every

bi onne ted outerplanargraph

G

has exa tlyone Hamiltonian y le, namely

the one delimiting the fa e to whi h all the verti es of

G

are in ident in an

outerplanarembeddingof

G

.

2.2 Data Stru tures for Planar Graphs

In order to des ribeand e iently handle the de omposition of a onne ted

graph into bi onne ted omponents and of a bi onne ted graph into

2.2. DATASTRUCTURESFORPLANARGRAPHS 19

The data stru ture that an be used to des ribe the de omposition of a

onne ted graph into its bi onne ted omponents, alled blo k- utvertex tree

(usuallyreferredtoasBC-tree),wasintrodu edbyHararyandPrinsin[HP66℄.

TheBC-tree

T

ofa onne tedgraph

G

is atree ontainingaB-nodeforea h

blo k of

G

and a C-node for ea h utvertex of

G

. Edges in

T

onne t ea h

B-node

µ

totheC-nodesasso iatedwiththe utverti esbelongingtotheblo k

of

µ

. The BC-treeof

G

maybethought as rooted at aspe i blo k

ν

. The

number of nodes of

T

is equal to the number of blo ks plus the number of

utverti es, that is

O(n)

, where

n

is the number of verti es of

G

. Fig. 2.1

showsa onne tedplanargraphanditsblo k- utvertextree,rootedatablo k

B

1

.

B

₁

B

₄

B

₃

B

₂

c

₁

c

₂

B

₁

B

2

B

3

B

4

c

₂

c

₁

(a) (b)

Figure 2.1: (a) A onne ted planar graph and (b) its blo k- utvertex tree,

rootedat

B

1

.

The data stru ture that an be used to des ribe the de omposition of a

bi onne ted graph into its tri onne ted omponents, alled SPQR-tree, was

introdu ed by Di Battista and Tamassia in [DT90, DT96b, DT96a℄. In the

following we dene SPQR-trees, we give their main properties, and we

de-s ribehow su h trees an be used to representand e iently handle all the

embeddingsofaplanarbi onne tedgraph.

SPQR-Trees

SPQR-trees were introdu ed in [DT96b℄ to des ribe all the possible

embed-dingsofbi onne tedplanargraphsin asu in twayandwereused invarious

situations whenaskingforplanarembeddingswith spe ialproperties.

A graphis st-bi onne tible if adding edge

(s, t)

to it yields a bi onne ted

graph. Let

G

bean st-bi onne tiblegraph. A split pair

{u, v}

of

G

iseither

G

with respe t to asplit pair

{u, v}

(or, simply, a maximal split omponent

of

{u, v}

)iseitheranedge

(u, v)

oramaximalsubgraph

G

′

of

G

su hthat

G

′

ontains

u

and

v

,and

{u, v}

isnotasplitpairof

G

′

. Avertex

w

6= u, v

belongs

toexa tlyonemaximal split omponentof

{u, v}

. We all split omponent of

{u, v}

theunionofanynumberofmaximalsplit omponentsof

{u, v}

.

In[DT96b℄,SPQR-treeswereintrodu edasrootedatoneedgeof

G

, alled

referen e edge. However,they analsobeviewedas unrooted,sin ea

de om-position starting from a dierent referen e edge would yield a tree with the

samestru ture. Here,in orderto simplify thedes riptionofthe onstru tion

ofSPQR-trees,werstdes ribethemasrootedtreesandthenwe ommenton

theimpli ationsof onsideringthem asunrooted.

RootedSPQR-Trees

TherootedSPQR-tree

T

e

ofabi onne tedgraph

G

,withrespe ttoareferen e

edge

e

,des ribesare ursivede ompositionof

G

indu edbyitssplitpairs. The

nodesof

T

e

areoffourtypes: S,P,Q,andR.Their onne tionsare alledar s,

inordertodistinguishthemfrom theedgesof

G

.

Ea hnode

µ

of

T

e

hasanasso iatedst-bi onne tiblemultigraph, alledthe

skeleton of

µ

anddenotedbyskel

(µ)

. Skeletonskel

(µ)

showshowthe hildren

of

µ

, representedbyvirtualedges, are arrangedinto

µ

. Thevirtualedge in

skel

(µ)

asso iatedwitha hildnode

ν

,is alledthevirtualedgeof

ν

inskel

(µ)

.

Forea hvirtualedge

e

i

ofskel

(µ)

,re ursivelyrepla e

e

i

withtheskeleton

skel

(µ

i

)

ofits orresponding hild

µ

i

. Thesubgraph of

G

that is obtainedin

thiswayisthepertinentgraph of

µ

andisdenotedbypertinent

(µ)

.

Given abi onne ted graph

G

and areferen e edge

e = (u

′

_{, v}

′

₎

, tree

T

e

is

re ursivelydened as follows. At ea h step, a split omponent

G

∗

, a pairof

verti es

{u, v}

,and anode

ν

in

T

e

are given. A node

µ

orresponding to

G

∗

isintrodu edin

T

e

andatta hedtoitsparent

ν

. Verti es

u

and

v

arethepoles

of

µ

and denotedby

u(µ)

and

v(µ)

, respe tively. Thede omposition possibly

re ursonsomesplit omponentsof

G

∗

. Atthebeginningofthede omposition

G

∗

_{= G}

− {e}

,

{u, v} = {u

′

_{, v}

′

}

,and

ν

isaQ-node orrespondingto

e

.

Base Case: If

G

∗

onsists of exa tlyone edge between

u

and

v

, then

µ

is a

Q-nodewhoseskeletonis

G

∗

itself.

Parallel Case: If

G

∗

is omposed of at leasttwomaximal split omponents

G

1

, . . . , G

k

(

k

≥ 2

)of

G

withrespe tto

{u, v}

,then

µ

isaP-node. Graph

2.2. DATASTRUCTURESFORPLANARGRAPHS 21

e

1

, . . . , e

k

and orrespondingto

G

1

, . . . , G

k

,respe tively. The

de omposi-tionre urson

G

1

, . . . , G

k

,with

{u, v}

aspairofverti esforeverygraph,

andwith

µ

asparentnode.

Series Case: If

G

∗

is omposed of exa tlyone maximal split omponent of

G

with respe t to

{u, v}

and if

G

∗

has utverti es

c

1

, . . . , c

k−1

(

k

≥ 2

),

appearing in this order on a path from

u

to

v

, then

µ

is an S-node.

Graph skel

(µ)

is the path

e

1

, . . . , e

k

, where virtual edge

e

i

onne ts

c

i−1

with

c

i

(

i = 2, . . . , k

− 1

),

e

1

onne ts

u

with

c

1

, and

e

k

on-ne ts

c

k−1

with

v

. The de omposition re urs on the split omponents

orrespondingto ea h of

e

1

, e

2

, . . . , e

k−1

, e

k

with

µ

as parentnode, and

with

{u, c

1

}, {c

1

, c

2

}, . . . , {c

k−2

, c

k−1

}, {c

k−1

, v

}

as pair of verti es,

re-spe tively.

Rigid Case: Ifnoneoftheabove asesapplies,thepurposeofthe

de ompo-sitionstepis that ofpartitioning

G

∗

into the minimumnumberof split

omponentsand re urringonea hof them. Weneedsomefurther

de-nition. Givenamaximalsplit omponent

G

′

ofasplit pair

{s, t}

of

G

∗

, avertex

w

∈ G

′

properly belongs to

G

′

if

w

6= s, t

. Given a split pair

{s, t}

of

G

∗

,amaximalsplit omponent

G

′

of

{s, t}

isinternal ifneither

u

nor

v

(thepoles of

G

∗

)properlybelongs to

G

′

, external otherwise. A

maximalsplitpair

{s, t}

of

G

∗

isasplitpairof

G

∗

that isnot ontained

intoan internalmaximal split omponentof anyother splitpair

{s

′

_{, t}

′

_}

of

G

∗

. Let

{u

1

, v

1

}, . . . , {u

k

, v

k

}

bethemaximalsplitpairsof

G

∗

(

k

≥ 1

)

and,for

i = 1, . . . , k

,let

G

i

betheunionofalltheinternalmaximalsplit

omponents of

{u

i

, v

i

}

. Observethat ea h vertex of

G

∗

either properly

belongstoexa tlyone

G

i

orbelongstosomemaximalsplitpair

{u

i

, v

i

}

.

Node

µ

is anR-node. Graphskel

(µ)

is the graphobtainedfrom

G

∗

by

repla ingea hsubgraph

G

i

with thevirtualedge

e

i

between

u

i

and

v

i

.

The de omposition re urs on ea h

G

i

with

µ

as parent node and with

{u

i

, v

i

}

aspairofverti es.

Forea hnode

µ

of

T

e

,weaddtoskel

(µ)

thevirtualedge

(u, v)

representing

the parentof

µ

in

T

e

. Wesay thatan edge

e

′

of

G

proje ts to avirtualedge

e

′′

ofskel

(µ)

,forsomenode

µ

in

T

e

,if

e

′

belongstothepertinentgraphofthe

node of

T

e

orresponding to

e

′′

. Fig. 2.2 depi tsa bi onne ted planargraph

anditsSPQR-tree.

Property 2.1 Let

C

bea y leof

G

andlet

µ

beany nodeof

T

e

. Then,either

P

S

R

S

P

S

R

R

R

(a) (b)

Figure2.2: (a) Abi onne ted planargraphand(b) itsSPQR-tree,rooted at

any Q-node adja ent to the R-node whose internal verti es are bla k. The

skeletonsof theinternalR-nodesofthe treearerepresentedinside theboxes.

The virtualedge representingthe parentof a node

µ

in the skeleton of

µ

is

drawnasadottedline.

ofvirtual edges thatindu ea y le in skel

(µ)

.

The SPQR-tree

T

e

of a graph

G

with

n

verti esand

m

edges has

m

Q-nodes and

O(n)

S-, P-, and R-nodes. Also, the total number of verti es of

theskeletons stored at the nodes of

T

e

is

O(n)

. Finally, SPQR-trees an be

onstru tedandhandlede iently. Namely,givenabi onne tedplanargraph

G

, theSPQR-tree

T

e

of

G

anbe omputedin lineartime[GM00℄.

UnrootedSPQR-Trees

Nowwedes ribehowtomodify

T

e

inordertohaveanunrootedtree

T

.

Trees

T

e

and

T

have the same nodes and ar s. They only dier in the

skeleton of their nodes. Given a node

µ

e

of

T

e

, with split pair

{u, v}

and

parent

ν

e

, thevirtualedge

(u, v)

isaddedto skel

(µ

e

)

to obtainskel

(µ)

in

T

.

Hen e, in an unrooted SPQR-tree

T

, an ar

(µ, ν)

identies two virtual

edges

e(ν

|µ) ∈

skel

(µ)

and

e(µ

|ν) ∈

skel

(ν)

that representhowthesplit

om-ponent

ν

atta hes to skel

(µ)

and how the split omponent

µ

atta hes to

skel

(ν)

,respe tively.

For unrooted SPQR-trees an equivalent on eptof pertinent graphis

2.2. DATASTRUCTURESFORPLANARGRAPHS 23

and

ν

onsists of removing

e(ν

|µ)

from skel

(µ)

and

e(µ

|ν)

from skel

(ν)

and

identifying their orrespondingend-verti es. Givenanode

µ

of

T

, the whole

graph

G

anbeobtainedbyre ursivelymerging

µ

withitsadja entnodes. We

all su hanoperation mergingof

T

. If

e(ν

|µ)

isavirtualedge ofskel

(µ)

, we

dene pertinent

(µ, e(ν

|µ))

as the subgraph obtained by removing

e(ν

|µ)

and

re ursively merging

µ

with its adja ent nodes with the ex eption of

ν

. The

graphpertinent

(µ, e(ν

|µ))

dened on

T

oin ides withthegraphpertinent

(µ)

dened on

T

e

when

ν

isonthepathfrom

µ

totherootof

T

e

.

Observethat,twoSPQR-trees

T

e

′

and

T

e

′′

,rootedattwodierentedges

e

′

and

e

′′

of

G

, orrespondtothesameunrootedtree

T

.

Using SPQR-Trees to Represent Planar Embeddings

Let

G

beabi onne tedgraphand let

T

bethe SPQR-treeof

G

. Graph

G

is

planarifandonlyiftheskeletonsofallthenodesof

T

areplanar[BDD00℄.

TheSPQR-tree

T

an beused to representall the planarembeddings of

G

. Infa t,suppose thatone of the ombinatorialembeddingsoftheskeleton

of ea h nodeis hosen. A ombinatorial embedding of

G

an beobtainedby

merging the skeletons of all the adja ent nodes of

T

while preserving their

embedding.

Observethat:

(i) theskeleton of an S-node admits exa tly one ombinatorial embedding

(ea hvertexhasdegreetwo);

(ii) the skeleton of a P-node admits as many ombinatorial embeddings as

thenumberofpermutationsofitsvirtualedges;and

(iii) the skeleton of an R-node, whi h is tri onne ted, admits exa tly one

ombinatorial embedding up to a reversal of the adja en y lists of its

verti es.

Hen e,a ombinatorialembedding

Γ

of

G

isidentiedbyspe ifyingforea h

R-nodeoneofitstwopossibleembeddingsandforea hP-nodeapermutation

ofitsadja entnodes,asdes ribedin[BDD00℄. Wehavethefollowing.

Property 2.2 A planar embedding of the skeleton of every node of

T

deter-mines aplanar embeddingof

G

andvi e versa.

Inordertorepresenttheexternalfa e

f

intheSPQR-tree

T

,observethat

a fa e is uniquely identied bythe set of edges in ident to it, with the only

Given a fa e

f

of a ombinatorial embedding

Γ

, the unique subtreeof

T

whose leaves are theQ-nodes in ident to

f

is alled the allo ation tree of

f

.

Ea h node of the allo ation tree of

f

is an allo ation node of

f

. Figure 2.3

showsexamplesofallo ationtrees.

P

S

S

R

R

S

P

R

R

(a) (b)

Figure2.3: (a)A bi onne ted planargraph

G

and (b)the allo ationtreesof

thetwofa esof

G

markedwithastar.

Let

µ

beanallo ationnodeof

f

. Inskel

(µ)

thereexistsexa tlyonefa e

f

µ

that orrespondsto

f

,in thesense that

f

µ

willbetransformedinto

f

when

themergingof

T

isperformed. We all

f

µ

the representative of

f

in skel

(µ)

.

Inthe following,wewill denote by

f

botha fa e of

Γ

and its representative

fa eintheskeletonofoneofitsallo ationnodes. Wesaythat

f

belongstoall

itsallo ation nodes. Observethat, ifthe graphis asimple y le, it ontains

onlytwofa es,whoseallo ationtreeis thewhole SPQR-tree.

Therefore, aplanarembedding

hΓ, fi

an berepresentedbyasuitable

la-beling of

T

. Namely, ea h R-node is labeled with aBoolean valueand ea h

P-nodewiththe ir ularorderingofitsadja entnodes. Theexternalfa e

f

is

representedbyitsallo ationtree.

The following lemma shows the relationship between fa es belonging to

nodesthatareadja entin

T

.

Lemma2.1 Let

µ

and

ν

betwoadja ent nodesofanSPQR-tree

T

ofagraph

G

withplanar embedding

hΓ, fi

.

1. Thereareexa tly two fa es

f

′

and

f

′′

of

Γ

thatbelong both to

µ

and to

ν

.

2. Inskel

(µ)

(skel

(ν)

)

f

′

and

f

′′

2.2. DATASTRUCTURESFORPLANARGRAPHS 25

3. If

µ

(

ν

)isnotanS-node,then

e(ν

|µ)

(

e(µ

|ν)

) istheonlyedge sharedby

f

′

and

f

′′

inskel

(µ)

(skel

(ν)

).

Proof: Observe that when merging the skeletons of

µ

and

ν

the two fa es

in identto

e(ν

|µ)

areidentiedwiththetwofa esin identto

e(µ

|ν)

,andsu h

fa es orrespondtothesamefa es

f

′

and

f

′′

of

Γ

. Also,skel

(µ)

andskel

(ν)

do

notshareotherfa es.

Fa es

f

′

and

f

′′

arerepresentedinskel

(µ)

(skel

(ν)

)bythetwofa esadja ent

to

e(ν

|µ)

(

e(µ

|ν)

). Onlyifanode,say

µ

,isanS-node,

f

′

and

f

′′

analsoshare

otheredgesfurtherthan

e(ν

|µ)

,thatis,thevirtualedgesrepresentingthenodes

Part II

Chapter 3

Topologi al Morphing of Planar

Graphs

In this hapter

1

weanalyze the relationshipsamong dierent planar

embed-dingsofthesamegraphandstudyhowtwoplanarembeddings anbemorphed

oneintotheotherwiththeminimumnumberofelementary hanges,while

pre-servingthementalmapoftheuser. We allthisproblemTopologi alMorphing,

in analogywith the well-known Geometri Morphing problem, in whi h it is

studied howtwoplanardrawings anbemorphedone intotheotherwiththe

minimumnumberofelementary hanges.

First, we haveto de ide whi h elementary hangesare admittedin order

to preservethe mental map; then, wehaveto denewhi h operationsbetter

des ribesu h hanges;nally,wehavetostudytheproblemofminimizingthe

number of these operations. Wedene twooperations for morphing

embed-dings thatdes ribenaturaltransformationsand weshowthattheproblem of

morphingembeddingswiththeminimumnumberofsu hoperationsisNP-hard

for bi onne ted planar graphs. Further, we givepolynomial-time algorithms

forsomerestri tedversionsoftheproblemand, basedonsu halgorithms,we

giveaxed parametertra tablealgorithmforthegeneral ase.

1

Partoftheworkpresentedinthis hapterisajointworkwithPierFran es oCortese,

3.1 Introdu tion

Ausefulfeatureofagraphdrawingeditoristhepossibilityofsele tinga ertain

fa e of the drawing and promoting it to be the external fa e (for instan e,

see[dO℄). Inordertopreservethemental map, theuserwould liketheeditor

toexe utesu hanoperationwithasfew hangesto thedrawingas possible.

Theaboveoperationisjustanexampleofatopologi alfeaturethatwould

be useful to have at disposal from an editor. More generally, it would be

interesting to have an editor allowing the user to look at a drawing and to

spe ifyinsomeway,e.g.pointingatverti esoredges,anewembedding. Su h

an embedding ould be even requested at a more abstra t level, asking the

editortogotoonewithminimumdepth,orwithminimumradius,et . Again,

theeditorshouldtransformthe urrentembeddingintothenewonesmoothly,

i.e.,withtheminimumnumberof hanges.

A similar problem o urs when an editor has to geometri ally morph a

drawingintoanotherone,spe iedinsomewaybytheuser,whilekeepingthe

topologyun hanged. Inthis ase,the operationsperformedby theeditorare

topology-preservingtranslationsands alingofobje ts. Again,theuserwould

liketoseetheminimumnumberofintermediatesnapshots.

Theexisten eofageometri morphingbetweentwodrawingswasaddressed

surprisinglylongago. In

1944

,Cairnsprovedthat betweenanytwo

straight-linedrawingsofatriangulationthereexistsamorphinwhi hanyintermediate

drawing is straight-line planar [Cai44℄. This result was extended to general

planar graphs by Thomassen in 1983 [Tho83℄. The rst algorithms to nd

su h morphings were proposed by Floater and Gotsman, in

1999

, for

trian-gulations [FG99℄ and by Gotsman and Surazhsky, in

2001

, for generalplane

graphs[GS01℄. Whilethesear hforageometri straight-line morph between

twogiven drawingsofaplanargraphwith apolynomialnumberofstepsand

with abounded size of the needed gridis still open, somere entstudies

ad-dresstheproblemforthespe ial asesofpoly-linemorphing[LP08℄,orthogonal

drawings[LPS06,BLS05℄,andarbitraryplanedrawings[EKP03℄. See[Lub07℄

fora ompletesurveyonthissubje t.

We study the morphing between two drawingsfrom the topologi al

per-spe tive and we all it topologi al morphing. There are many ways to state

theproblem, ranging from the family of graphs,to theadmitted operations,

totheir ompleteness,totheirabilityto apture hangesthatarenaturalfor

theuser,andtothemetri sthatdistinguishagoodmorphingfromabadone.

3.1. INTRODUCTION 31

(a) (b) ( ) (d)

Figure3.1: Asequen eofipsandskipstransformingaplanarembedding.

1. We onsider bi onne tedplanargraphs,sin ethis lassof graphsisthe

buildingblo kofseveralgraphdrawingmethodologies.

2. We onsideroperationsthatmoveentireblo ksofthedrawing,identied

bysome onne tivityfeatures, in one singlestep. Namely, usingaterm

thatis ommonin planaritytestingliterature,we allip theoperation

thatips a omponentarounditssplit pair. Also,borrowingtheterm

fromthe ommonropeskippinggameplayedby hildren,we allskipthe

operationthatmovestheexternalfa etoasele tedfa ebyskippingan

entire omponentwithoutmodifyingthe ombinatorialembedding. More

formaldenitionsforthetwooperationswill begivenlater.

3. We use the numberof performed operations as the metri to evaluate

morphings and we onsider atopologi al morphing good if the editor

anperformitwithfewipsand skips. Intuitively,thefeweroperations

areperformed,thebetterthemental mapoftheuserispreserved.

Asanexample,supposethatthegraphisembeddedasshowninFig.3.1(a)

andthattheuserwouldliketoobtaintheembeddinginFig.3.1(d). Aminimum

sequen e ofoperationsthat performssu hamorphing onsists ofippingthe

omponent separated by the square verti es of Fig. 3.1(a), then by skipping

the omponent separatedby thesquare verti esof Fig.3.1(b), andnally by

skippingtheedgeseparatedbythesquareverti esofFig.3.1( ).

Wepresentthefollowingresults. Let

G

beabi onne tedplanargraphand

denoteby

hΓ, fi

oneofits ombinatorialembeddings

Γ

with

f

asexternalfa e.

Suppose that

hΓ

1

, f

1

i

is the urrent topology and that

hΓ

2

, f

2

i

represents a

target topology hosen by the user. In Se t. 3.3 we show that, if both ips

with the minimum number of ips and skips is NP- omplete. Motivated by

su haresultweta kleseveralrestri tedproblems. InSe t.3.4wegivealinear

time algorithm to move the external fa e from

f

1

to

f

2

with the minimum

numberofoperationwhen

Γ

1

= Γ

2

andonlyskipsareallowed. InSe t.3.5we

showthatthetopologi almorphingproblem anbee ientlysolvedif

G

does

not ontainanyparallel tri onne ted omponents. InSe t. 3.6 weshowthat

theproblem is xed-parameter tra table. Denitions and properties of basi

operationsarein Se t.3.2, while on ludingremarksarein Se t.3.7.

3.2 Flip and Skip Operations

Let

G

beabi onne tedplanargraphandlet

hΓ, fi

beaplanarembeddingof

G

, where

Γ

isa ombinatorialembeddingand

f

istheexternalfa e.

In thefollowing weformally dene theip and skip operations, that an

beusedtomodify

hΓ, fi

and,asa onsequen e,thelabelingoftheSPQR-tree

T

of

G

representing

hΓ, fi

. Intuitively, a ip operation ips a omponent

arounditssplit pair,while askipoperationallowstheexternalfa e to skip

an entire omponent, promoting a new external fa e without modifying the

ombinatorialembedding.

First,wedenetheipoperationwithrespe ttoaplanarembedding

hΓ, fi

.

Se ond,weshowhowitmodiesthelabelingof

T

representing

hΓ, fi

.

Let

{u, v}

bea maximalsplit pair of

G

and let

G

i

1

, with

i = 1 . . . q

, be a

set of topologi ally ontiguous maximal split omponents of

G

w.r.t.

{u, v}

.

Let

G

1

=

S

q

1

G

i

1

bethesubgraphof

G

obtainedastheunionofallthe

G

i

1

. We

denetheipoperationon

hΓ, fi

withrespe tto

G

1

: ip

(

hΓ, fi, G

1

) =

hΓ

′

_{, f}

′

i

,

where

Γ

′

isobtainedfrom

Γ

byreversingtheadja en ylistsofalltheverti es

of

G

1

, but for

u

and

v

, and by reversingthe order of theedges of

G

1

in the

adja en y lists of

u

and

v

. Fa e

f

′

is determined as follows. If at least one

outof

u

and

v

is notin

f

,then

f

′

_{= f}

. Otherwise,

f

′

istheuniquefa e of

Γ

′

ontainingboththe edgesbelongingto

f

andnotbelonging to

G

1

,and some

edgesof

G

1

notbelongingto

f

.

Asanexample,seetheipoperationappliedtotheembeddingofFig.3.1(a)

thatyieldstheembeddingofFig.3.1(b).

Nowweshowhowthelabelingof

T

ismodiedbyaipoperationip

(

hΓ,

f

_{i, G}

1

)

. For ea h maximal split omponent

G

i

1

of

G

, with

1

≤ i ≤ q

, with

respe tto

{u, v}

ontainedinto

G

1

, onsiderthenode

µ

i

of

T

su hthat

perti-nent

(µ

i

, e(ν

i

|µ

i

)) = G

i

1

, where

ν

i

isanodeadja entto

µ

i

in

T

. Observethat

q > 1

impliesthat

ν

i

isthesameP-node

µ

P

forea h omponent

G

i

3.2. FLIPANDSKIPOPERATIONS 33

q = 1

implies that

ν

s

6= ν

t

for ea h

1

≤ s, t ≤ q

and

s

6= t

. Further, onsider

thesubtree

T

i

1

of

T

rootedat

µ

i

andnot ontaining

ν

i

. Then,whenoperation

ip

(

hΓ, fi, G

1

) =

hΓ

′

_{, f}

′

i

isperformed,thelabelingof

T

representing

Γ

′

is

ob-tained from the labelingof

T

representing

Γ

by omplementing theBoolean

value of all the nodes of

T

i

1

, for ea h

i = 1 . . . q

, and, if

q > 1

, by reversing

thesubsequen e orrespondingto

µ

1

, µ

2

, . . . , µ

q

in the ir ularorderingofthe

adja entnodesof

µ

P

. If

G

1

ontainssomeedgesbelongingto

f

,thenthenew

externalfa e

f

′

isobtainedaspreviouslydes ribedandthenewallo ationtree

mustbeevaluateda ordingtoit.

With the intent of maintaining the mental map of the user, we add the

onstraintthataipoperationip

(

hΓ, fi, G

1

)

annotbeperformedif

G

1

on-tains all the edges of the external fa e

f

, be ause we regard that a ipping

of theentire externalstru ture ofthegrapharoundaninternal omponentis

undesirablefrom a omprehensionpointof view.

Thefollowingpropertiesdes ribethreebasi featuresoftheipoperation.

Property 3.1 ip

(f lip(

hΓ, fi, G

1

), G

1

) =

hΓ, fi

.

Property 3.2 If

G

1

isapath, then ip

(

hΓ, fi, G

1

) =

hΓ, fi

.

Property 3.3 If

G

− G

1

isa path, then ip

(

hΓ, fi, G

1

) =

hΓ, fi

, where

Γ

is

obtained from

Γ

byreversingthe adja en y listsofall the verti es.

Let

Γ

1

bea ombinatorialembeddingof

G

andlet

Γ

2

beatarget

ombi-natorial embedding of

G

. Itis easyto see that itis alwayspossibleto nda

sequen e of ipoperationsthat leads from

hΓ

1

, f

1

i

, foran arbitrary

f

1

∈ Γ

1

,

to

hΓ

2

, f

2

i

, for a suitable

f

2

∈ Γ

2

. Also, su h a sequen e is omposed of a

linearnumberof operationsand an be omputedin lineartime. Infa t,ip

operations allow both to arbitrarilypermutethe ir ular list asso iated with

ea hP-nodeandtoreversetheadja en ylistsoftheskeletonofea hR-node.

Weformalizethis on eptin thefollowinglemma.

Denoteby

F(Γ

1

, Γ

2

)

theminimumnumberof ipsto obtain

hΓ

2

, f

2

i

from

hΓ

1

, f

1

i

,foranarbitrary

f

1

∈ Γ

1

andasuitable

f

2

∈ Γ

2

.

Lemma3.1 For any two ombinatorial embeddings

Γ

1

and

Γ

2

of

G

we have

that

F(Γ

1

, Γ

2

)

is

O(n)

, where

n

isthenumber ofverti esof

G

.

Proof: ConsiderthelabelingoftheSPQR-treeof

G

representing

Γ

1

. Itiseasy

tondasequen eofipssu hthatea hipeithergivestoanR-nodethelabel