Dynamic programming for graphs on surfaces

-

English
61 Pages
Read an excerpt
Gain access to the library to view online
Learn more

Description

Niveau: Supérieur
Dynamic programming for graphs on surfaces Ignasi Sau CNRS, LIRMM, Montpellier Joint work with: Juanjo Rue Ecole Polytechnique, Paris, France Instituto de Ciencias Matematicas, Madrid, Spain Dimitrios M. Thilikos Department of Mathematics, NKU of Athens, Greece [An extended abstract appeared in ICALP'10] Ignasi Sau (CNRS, LIRMM) CIRM, Marseille October 19, 2010 1 / 29

  • over all

  • orientable surface

  • instituto de ciencias matematicas

  • any compact

  • joint work


Subjects

Informations

Published by
Reads 9
Language English
Document size 1 MB
Report a problem
aSisNC(uL,SRMMRInaIgtcbore912,10102/)CIRM,MarseilleO
[An extended abstract appeared inICALP’10]
Dynamic programming for graphs on surfaces
Joint work with:
Ignasi Sau CNRS, LIRMM, Montpellier
Dimitrios M. Thilikos Department of Mathematics, NKU of Athens, Greece
Juanjo Rue´ ´ Ecole Polytechnique, Paris, France InstitutodeCienciasMatem´aticas,Madrid,Spain
9
19erobct/20201,2
2
Background
1
5
Conclusions and further research
Outline
9
Sketch of the enumerative part
4
Main ideas of our approach
3
Motivation and previous work
u(CNsiSaIRMMRS,L,MaMC)RIllOesrieIgna
Main ideas of our approach
4
Sketch of the enumerative part
Background
2
Motivation and previous work
3
30102,91
1
5
Conclusions and further research
Outline
92/lleirsMaerobcteOisan(uaSgI)CMMM,IRRSCNIR,L
iSasgnIelliotcOM,MResraRMLICIM)(CauS,NR
Tis a tree where all the internal nodes have degree 3. µis a bijection between the leaves ofTandE(G).
Abranch decompositionof a graphG= (V,E)is tuple(T, µ) where:
For eacheE(T), we definemid(e)=V(Ae)V(Be).
Each edgeeTpartitionsE(G)into two setsAeandBe.
Thebranchwidthof a graphG(denotedbw(G)) is the minimum width over all branch decompositions ofG:
Thewidthof a branch decomposition is maxeE(T)|mid(e)|.
bw(G) =(Tm,iµn)emEa(Tx)|mid(e)|
104/29
Branch decompositions and branchwidth
ber19,20
Orientable surfaces: obtained by addingg0handlesto the sphereS2, obtaining the g-torusTgwithEuler genuseg(Tg) =2g.
Non-orientable surfaces: obtained by addingh>0cross-capsto the sphereS2, obtaining a non-orientable surfacePhwithEuler genuseg(Ph) =h.
Surface Classification Theorem:
any compact, connected and without boundary surface can be obtained from the sphereS2by addinghandlesandcross-caps.
SURFACE=TOPOLOGICAL SPACE,LOCALLYFLAT
RN,SuaC()MICILMRasiSIgn02,91reb
Surfaces
92/501sear,MRMtoOcleil
,LRSMMIRSasiCNu(angI
Orientable surfaces: obtained by addingg0handlesto the sphereS2, obtaining the g-torusTgwithEuler genuseg(Tg) =2g.
any compact, connected and without boundary surface can be obtained from the sphereS2by addinghandlesandcross-caps.
Surface Classification Theorem:
SURFACE=TOPOLOGICAL SPACE,LOCALLYFLAT
9
Surfaces
Non-orientable surfaces: obtained by addingh>0cross-capsto the sphereS2, obtaining a non-orientable surfacePhwithEuler genuseg(Ph) =h.
MaM,IR)CeOlleirs91rebotc2/50102,