50 Pages
English

Disse tions orientations and trees

Gain access to the library to view online
Learn more

Description

Niveau: Supérieur, Doctorat, Bac+8
Disse tions, orientations, and trees, with appli ations to optimal mesh en oding and to random sampling ÉRIC FUSY and GILLES SCHAEFFER LIX, É ole polyte hnique, Fran e and DOMINIQUE POULALHON LIAFA, Université Paris 7, Fran e We present a bije tion between some quadrangular disse tions of an hexagon and unrooted binary trees, with interesting onsequen es for enumeration, mesh ompression and graph sampling. Our bije tion yields an e ient uniform random sampler for 3- onne ted planar graphs, whi h turns out to be determinant for the quadrati omplexity of the urrent best known uniform random sampler for labelled planar graphs [Fusy, Analysis of Algorithms 2005?. It also provides an en oding for the set P(n) of n-edge 3- onne ted planar graphs that mat hes the entropy bound 1 n log 2 jP(n)j = 2+ o(1) bits per edge (bpe). This solves a theoreti al problem re ently raised in mesh ompression, as these graphs abstra t the ombinatorial part of meshes with spheri al topology. We also a hieve the optimal parametri rate 1 n log 2 jP(n; i; j)j bpe for graphs of P(n) with i verti es and j fa es, mat hing in parti ular the optimal rate for triangulations.

  • spheri al

  • algorithm

  • derived maps

  • appli ation leads

  • tra ed ba

  • uniform sampling

  • algorithms

  • rooted

  • random generation

  • maps


Subjects

Informations

Published by
Reads 10
Language English
Document size 1 MB

Dissections,
orien
tations,
and
for
edded
Sub
trees,
=
with
for
applications
origin
to
2
optimal
sphere
mesh
??

algorithm
ding
dditional
and
Bender
to
)
random
set
sampling
Whitney
?RIC
ote
FUSY
edge.
and
indep
GILLES
a
SCHAEFFER
et
LIX,
Com
?cole
ting,
p
traced
olytechnique,
al
F
asymptotic
rance
ij
and

DOMINIQUE
i
POULALHON
to
LIAF
tially
A,
study
Universit?
where
P
d
a
No.
ris
This
7,
terest,
F
ey
rance
t
W
graphs
e
wing
presen
[
t
T
a
and

generation
b
ork
et
an
w
mer-
een
where
some
of
quadrangular
(
dissections
3
of
i
an
2
hexagon

and
elled)
unro
j
oted
2
binary
By
trees,
ha
with
b
in
omorphisms,
teresting
that


for
a
en
and
umeration,
mark
mesh
Name,

20YY,
and
planar
graph
is
sampling.
t
Our
it

a
yields
t
an
t

dra
t

uniform

random
Graph
sampler
Categories
for
Descriptors:

Mathematics
planar
algorithms
graphs,
Algorithms
whic
W
h

turns
ding,
out
INTRODUCTION
to
this
b
b
e
k
determinan
of
t
the
for
an
the
[Bender

ask

simple
y
remark
of
ula
the
i;


t
2
b

est
j
kno
2
wn
+
uniform
for
random
of
sampler

for
graphs
lab
er-
elled
and
planar
+
graphs
n
[
y
F
theorem
usy
these
,
e
Analysis
unique
of
on
Algorithms
to
2005
that

ts
It
r
also

pro
maps
vides
map
an
em

the
ding
o
for
with
the
orien
set
CM
P
ol.
(
Mon
n
ages
)

of
map.
n
algorithm
-edge
of

enden
planar
in
graphs
and
that
is
matc

hes
k
the
ingredien
en
in
trop

y
straigh
b
line
ound
wing
1
for
n
planar
log
[
2
hon
jP
al.,
(
Dra
n

)
and
j

=
G.2.1
2
Discrete
+

o
binatorial
(1)
General
bits
erms:
p
A
er
Key
edge
ords
(bp
Phrases:
e).
Coun
This
Co
solv
Random
es
1.
a
One

of
problem
w


tly
e
raised

in
to
mesh


Ed
as
in
these
A
graphs
ic

Mathematic
the
Monthly


binatorial
he
part
ed
of
a
meshes
explanation
with
the

able
top
form
ology
jP
.
n;
W
j
e
j
also
1
ac
5
hiev
4
e
n
the
2
optimal
2
parametric
+
rate

1
j
n
i
log
2
2
(1)
jP
the
(
y
n;
the
i;
of
j
(unlab
)
planar
j
with
bp
v
e

for

graphs
n
of
i
P
j
(
edges,
n
going
)
innit
with
.
i
a
v
of

[1933],
and
graphs
j
v

essen
matc
a
hing
em
in
edding
particular
the
the
up
optimal
home-
rate
so
for
their
triangulations.
amoun
Our
to

of
ding
o
relies
d
on
onne
a
d
linear
,
time
a
algorithm
is
to
graph

b
an
in
orien
plane
tation
r
asso
ote

means
to
a
the
ed
minimal
ted
Sc
A
hn
Journal
yder
V
w
V,
o
N,
o
th
d
P
of
10
a
.2

?ric
F
the
ds.
algorithms
usy
Let
et
uniform
al.
n
1.1
ula
Graphs,

dissections
outputs
and
in
trees
1.1
Another
and
kno
j
wn
the
prop
t
ert
plane
y
uniform
of
with

e
planar
t
graphs
N,
with
of
n
with
edges
5
is
3-
the
b


that
are
they
ondence
are

in
form

b
one-to-one


i.e.,
ondence
P
with
all
dissections
uniform
of
rst
the
oulalhon
sphere
are
in
A
to
v
n
the
quadrangles
b
that
ro
ha
to
v
as
e
jP
no
er

i

Mullin
The
whic
heart
It
of
o
our
of
pap
binary
er
that
lies

in

a
leading
further
of
one-to-one
r

v
ondence.
[1964]
Theorem
A
1.1.
is
Ther
ro
e
giv
is
t
a
ro
one-to-one
equal

same
orr
0
esp

ondenc

e
ph
b
et
etwe

en
ran-
unr
testing
o
ra
ote
V
d
quite
binary
ed.
tr

e
represen
es
n
with
jP
n
coun
no

des
edges
and
utte
unr
renemen
o
in
ote
that
d
ij
quadr
um
angular
ro
disse
maps


of
(due
an
Sc
hexagon
[1968])
with
F
n
follo
interior
explains
vertic
of
es

and
pro
no
since

ypical

en
The
men
mapping
one-to-one
from
ecializes
binary
to
trees
triangulations
to
with
dissections,
degree
whic
the
h
deriv
w

e
for

ote
the
with

originally
e
Bro
,

is
Random
easily
b
describ
Theorem
ed

and
sampler
resem

bles
algorithm

n
that
random
w
the
ere
n


tly
edges
prop
hances
osed
ts.
for
yield
simpler
for
kinds
.
of
generation
maps
maps

or
haeer
w
1997;
in
Bouttier
(see
et
b
al.
1994;
2002;
Sc
P
v
oulalhon
es
and
planar
Sc
used
haeer
dra

[de
The
et
pro
Journal
of
V,
that
th
the
in
mapping
olv
is
Theorem
a
leads

to
is
implicit
instead
tation
rather
the

um
relying
ers
on
0
new
j
prop
ting
erties
oted
of
maps

n
orien
due
tations
T
[Ossona
[1963]),
de
its
Mendez
t

discussed
related

to
yields
Sc
of
hn
0
yder
j
w
n
o
b
o
of
ds
oted
of

triangulations
with
and
v

and
planar

maps
to

and
hn
hellen
yder
erg
1990;
from
di
h
Battista
orm
et
(1)
al.
ws.
1999;
partially
F
the
elsner


the
.

Con
of
v

ersely

,
binomials,
the
these

t
of
of
the
tree
tree
umerations.
from
us
the
tion
dissection
the
relies

on
sp
a
par-
linear

time

algorithm
plane
to
(i.e.,

maps
the
all
minimal
of
Sc
3),
hn
to
yder
rst
w
e
o
ation
o
the
ds
ting
of
ula
a
un-

o
map
d
(or
triangulations
equiv
i
alen

tly
found
,
y
the
wn
minimal
using

metho
0
1.2
-orien
sampling
tation

of
ypro
the
of
asso
1.1

an
deriv
t
ed
random
map,
for
see
oted

maps,
9).
an
This
that,
problem
en
is
,
of
a
indep
elemen
endan
in
t
set
in
0
terest
of
and
oted
our
maps
algorithm
n
has
with
for

example
for
applications
elemen
in
The
the

graph
a
dra
sampler
wing
P

ij
text
The
[Bonic
random
hon
of
et
of
al.
lik

triangulations
It
3-
is
graphs
akin
as
to

Kan
mathematical
t's
ysics

references
ordering
[Am
[Kan
j?rn
t
al.
1996;
P
Ch
and
uang
haeer
et
and
al.
arious
1998;
yp

of
hon
dom
et
graphs
al.

2003;
for
Castelli-Aleardi
graph
and
wing
Devillers
(see

F
but
ysseix
again
al.]).
the
CM
pro
Name,
of
ol.
of
No.

Mon
is
20YY.Dissections
and
trees

des
time-complexit
2
3
similar
The
with
b
the
est
y
previously
the
kno
A
wn
information
algorithm


e
haeer
a

prepro
had
translate
exp
our
ected
p

in
y
balanced
O
the
(
(
n
motiv
5
Gotsman
=
The
3
A
)
w
for
that
P
al.
0
et
n
Boltzmann
,
in
and
the
w
for
as
imate
m
is
uc
with
h

less
bits.

er
t
jP
for
,
P
etter
0
3D
ij
in
,
with
ha

ving
Gotsman
ev
w
en
when
exp
N,
onen
generator
tial
dev

authors
plexit
the
y
of
for
e
i=j
used
or
the
j
random
=i
general
tending
tly
to
al.
2
ro
(due
usy
to
(
Euler's
sampling
form
time
ula
1.3
these

ratio
y
are
3-
b
y
ounded
In
ab
ded
o
ord
v
is
e
en
b

y
1
2
j
for
es


maps).
giv
In
the

and
6,
v
w
uge
e

sho

w
1999;
that
y
our
olygonal
generator
t
for

P
y
0
relation
n
y
or
with
P
V
0
Fi-
ij
uniform
p
planar
erforms

in
ed
linear
of
time
usy

v
if
ensiv
i=j

or
dirsky
j
The
=i
heme
tends
the
to
[Bo
2

where
d
it
to
b
relies
ecomes
a
at
ork
most
generation

elop
F
hon
rom
Thanks
the
generator


p
of
oin
has
t
of
of
2
view,
size
it
ev
is
in
also
appro
desirable
uniform
to

w
b
ork
Theorem
with
p
the

uniform
time
distribution
planar
on
edges
planar
binary
graphs.
no
Ho
the
w
e
ev
y
er,
thesis
random
2
(lab

elled)
in
planar
sense:
graphs
y
app
of
ear
graphs,
to
tit
b
log
e
n

tends
hallenging
n
mathematical
innit
ob
that

for
[Osth
)
us
a
et
tee
al.
rate.
2003;

McDiarmid
transmission
et
meshes
al.


a
A
on
Mark
for
o
part
v
The

dealt
hain


ouma
v
but
erging

to
that
the
ha
uniform
ecome
distribution
[Alliez
on
for
planar
surv
graphs
of
with

i
raised
v



w
eral
as
with
giv
top
en
Journal
b
V,
y
th
Denise
nally
et
new
al.
random
[1996],
for
but
graphs
it
as
resists
tly
kno
elopp
wn
b

one
hes
the
for
[F
p

er-
a

oids
sampling
exp
[Wilson
e


and
tations
has
[Bo
unkno
et
wn

mixing

time.
sc
As
is
opp
to
osed
one
to
in
this,
dirsky
a
al.

but
e
metho
sc
to
heme
it
to
a
sample
generator
planar
on
graphs
samplers,
w
new
as
framew
prop
for
osed
random
b

y
dev
Bo
ed
dirsky
[Duc
et
et
al.

[2003],
to
with
random
amortized
for

oted
y
maps,
O
algorithm
(
[F
n

6
a
:
y
5
O
)
n
.
)
This
exact
result
uniform
is
and
based
en
on
erforms
a
linear

for
e
x-

size
o-
sampling.
sition

of
ding
planar
third
graphs:
ypro
a
of
planar
1.1
graph
the

ossibilit
b
to
e
de

linear
osed
a
in

to
graph
a
n
tree-structure
b
whose
a
no
tree
des
n
are
des.
o
turn

tree
b
b
y

ro
b
oted
a

paren
maps.
w
Generating
of
a
n
planar
This
graph
de

optimal
to
the



the
hing
trop
probabilities
p
so
edge
as
this
to
of
generate
i.e.,
the
quan

y
osition
n
tree
2
with
(
suitable
)
probabilit
,
y;
to
then
when
a
go
random
to
ro
y
oted
so

a
map
de
is
P
generated
n
for


e
h
b
no
guaran
de
on
of

the
Applications

for
osition
storage
tree.
fast
Bo
of
dirsky

et
ha
al.
e
[2003]
tly
use
ated
the
h
so-called
literature


e
particular
metho
the
d
binatorial
[Nijenh
of
uis
meshes.
and
rst
Wilf
algorithms
1978;
only
Fla
triangular
jolet
[Rossignac
et
T
al.
and
1994;

Wilson
man

meshes
to
larger
tak
so
e
p
adv
meshes
an
v
tage
b
of
prominen
the
(see

and
e


a
osition
t
of
ey).
planar
question
graphs.
optimalit
Our
of
new
ders
random
as
generator
in
for
with
ro

oted
pro

b
maps
sev


their
dealing
amortized
meshes


to
ology
O
CM
(
Name,
n
ol.
3
No.
)
Mon
.
20YY.4

?ric
F
of
applications
2.1
usy
The
et
map
al.
A
[Gotsman
b
2003;
requires
Kho
leads
dak

o
oth
vsky
i
et
of
al.
b

a
Since
tations,
these
5),
meshes
a
are
yder
exactly
b
triangu-
unlab
lations
is
(for
In
triangular
an
meshes)
with
and
ed


planar
dissections
graphs
follo
(for
pro
p
deriv
olyhedral
that
ones),
w
the
7)

result:
ders

in
also
[P
o
oulalhon
orien
and
of
Sc
a
haeer
pr

at
and
d
in
N,
the

presen
algorithm
t
for
pap
The
er

resp
trees
ectiv
some
ely
them
pro
(Section
v
binary
e
b
that
mapping
tra
existence
v
of
ersal
auxiliary
based

algorithms
their

ed
ac
three
hiev
result:
e
discuss
optimalit
and
y
maps.
.

On
w
the
to
other
of
hand,
planar
in
the
the
ds

,
text
pro
of
1

the
data
e

A
almost
b
optimal
in
algorithms
that
ha
do
v
ts.
e
e
b
of
een
V
prop
this
osed
in
[He
=
et
our
al.
ecializes
2000;

Lu
1.4

pap
that
er
are
w
based
preliminaries:
on
maps
separator
v
theorems.
2),
Ho

w
w
ev
3).
er
main
these
the
algorithms
w
are
and
not
the
truly
quadrangular
optimal
that
(they
a
get
from
"
uniqueness

tri-orien
to
dissections.
the
of
en
whic
trop
in
y
the
but
maps
at
0
the
dela


of
after
an


our
trolled
these


of
ting
the
(Section

ding
ts
oted
in
third
the
to
linear
ortan


y).
presen
Moreo
time
v
the
er,
-orien
although
deriv
they
a
rely

on
onds
a
Sc

o

to
e
e).

10
they
the
do
of
not
algorithm.
supp
the
ort
w

t
t


2.
requests.
r
As
map
opp
er
osed
of
to

that,
plane,
our
er
algorithm
are
shares

with
meet
[He
endp
et
planar
al.
to
1999;
o

one
hon
outer
et
Journal
al.
V,

th
the
range.
prop
particular
ert
the
y
j
that
2
it
4
pro
new

sp
essen
to
tially
optimal
the
der

triangulations.
de
Outline
of
the
a
er
spanning
pap
tree.
starts
More
t
precisely
o
it
of
is
denitions
just
the
the
and
balanced
in
paren
olv
thesis
(Section

and
de

of
ondences
a
et
binary
een
tree,
(Section
and
Then

our
of
result
the
4),
initial
mapping
dissection
et
that
een
are
trees
not
some
presen
of
t
hexagon
in
y
the

tree


this
b
is
e


ws
v
the
ered
and
from
of
the


tation
de
our
b
The
y
of
a
this
simple
theorem,
v
h
ariation
the
on
tro
the
of
in
so-called
terpretation
ed
of
and
the

sym
-orien
b
is
ols.
y
A
to

8,
queries
is,

the
th

us
to
b
of
e
main
dealt
in
with

in
e
time
ely
prop

ortional
(Section
to
sampling
the
6)
degree

of
(Section
v
ro


[Castelli-Aleardi
The
et
application
al.
us

our
using
imp
the
t

in
h
9
of
e
[Munro
t
and
linear
Raman
algorithm
1997;

He
minimal
et
0
al.
tation

the
Finally
ed
w
of
e

sho
map
w
h
that

the
to

minimal
de
hn

w
b
o
e
alluded
mo
ab
died
v
to
Finally
b

e
is
optimal
to
on

the
of

this
P
tation
(
Figure
n;
summarizes
i;

j
et
)
een
.
dieren
Since
families
the
ob
en
w
trop

y
DEFINITIONS
of
Plana
this
maps

planar
is
is

prop
smaller
em
than
edding
that
an
of
elled
P
graph
(
the
n
where
)
op
as
means
so
edges
on
smo
as
simple
j
that
i
not
n=
but
2
their
j
oin

A
n
map
1
said
=
b
2
r
,
ote
the
if
resulting
edge
parametric
the


der
CM
is
Name,
more
ol.

No.
t
Mon
in
20YY.Dissections
and
trees
manner
j
d

B
5
trees

ot-no
planar
on
graphs
ed

t
maps
th
deriv
of
ed
of
maps
a

later
quadrangulations
n
deriv
to
ed
tree
maps
hoice
with
the
orien
e
tation
ot-edge
dissections

of
r
the
wing
hexagon
no
dissections
t
of
trees
the
w
hexagon
of
with
+
orien
ro
tation
Catalan
binary

trees
in
paren
The
thesis
de.

white-r
de
Journal
iter
v
ative
a
algorithm
e
tr
stem.
ansp
binary
osition

op
a
er
.
ations
tree,
op
a
ening
ro

ro
e
son
r
ery
eje
of


Whitney
n
folklor
ectiv
e
0
Fig.
oted
1.
ha
Relations
es,
b
on
et
w
w
ted
een
ers:
in
+1
v

olv
greedily
ed
white
ob
v

up

of
the
ro
r
o
o
,
ot-e
ro
dge
V,
,
By
is
tion
mark
require
ed
o
and
tr
orien
a
ted
is

ro
h
ro
that
th
the
no
outer
r

,
la

ys
ot-le
on
this
its
oted
righ
on
t.
tree
The
do
origin
with
of
ev
the
(including
ro
de)
ot-edge
a
is
a

This
r
v
o
usual
ot-vertex
oted
.
b
V
enien

F
and
1
edges
denote
are
b
said
and
to
the
b
and
e
trees
outer
des
or
e
inner
lea
dep
pro
ending
y
on
).
whether
trees
they
kno
are
e

y
t
um
to
0
the
1
outer
n

The
or
a
not.
b
A
sa
planar
k
map
that
is



onne
is

the
d
the
if
rst
it
a
has

at
either
least
d
4
ote
edges
ending
and
of

A
not
V
b
N,
e
3.


b
en
y
w
the
shall
remo
that
v
r
al
ote
of
binary
t
e
w
has
o
ro
v
that

a
The
The
rst
ot-edge

a
planar
oted
map
tree
is
us
the
a
tetrahedron,
de,
whic
the
h
o
has
de
6
to
edges.
leaf,
W
the
e
o
denote
af
b
With
y
denition
P
ro
0
binary
n
up
(resp
dra
ectiv
the
ely
in
P
top
0
wn
ij
starting
)
the
the
ot-leaf,
set
ery
of
de
ro
the
oted
ot-no

has
planar
father,
maps
left
with
and
n
righ
edges
son.
(resp.
(v
i
minor)
v
ariation

the
and
denition
j
ro

binary
A
will

e
planar
v
map
t
is
on.
outer-triangular
or
if

its
,
outer
e

resp
is
ely
triangular.
y
2.2
n
Plane
B
trees,
n
and
sets
half-edges
binary
Plane
ro
tr
binary
e
with
es
no
are
(they
planar
v
maps
n
with
2
a
v
single
as

v
the
b
outer

one.
n
A
These
v
oted
ertex
are
is
ell

wn
a
b
le

af
b
if
the
it
n
has
b
degree
jB
1,
n
and
=
no
n
de
2
otherwise.
n
Edges
.

v
t
of
to
binary
a

leaf
e
are


y
stems
blac
,
or
and
so
the

other
v
are
ha

e
entir

e

e
unique
dges
to
.

Observ
of
e

that
the
plane
no
trees
As
are

unr
oted
o
binary
ote
are
d
black-r
trees.
ote
Binary
or
tr
o
e
d
es
dep
are
on
plane

trees
the
whose
ot
no
CM
des
Name,
ha
ol.
v
No.
e
Mon
degree
20YY.6

?ric
F
e

OF
usy
D
et

al.
n
no
disse
de.
sa
The
and
sets
of
of
adaptation
blac
resp
k-ro
dissections
oted
are
(resp.
v
white-ro
k
oted)
ro
binary
0
trees
blac
with
t
i

blac
w
k
map
no
with
des
Euler's
and
will
j

white
0
no
.
des
of
is
so
denoted
h
b
b
y
k
B
ertex


ij

(resp.
omplete
b
2.
y
on
B

Æ
and
ij
and
);
a
and

the
V,
total
dissections
set

of
quadrangular
ro
no
oted
b


binary

trees
ro
with
denoted
i
Q
blac
n
k
dissections
no
degree,
des
b
and
blac
j
edge
white
a
no
unique
des

is
ij
denoted
quadrangulations
b
j
y
the
B
and
0
of
ij
blac
.
inner
It
ro
will

b
outer
e
v

v
v
o
enien
CORRESPONDENCES
t

to
een
view
angular

erg
h
maps.
en
us
tire
w
edge
Q
of
with
a
e
tree
Journal
as
th
a
ely)
pair
the
of
inner
opp
ha
osite
+
half-

e
F
dges
on,
eac
the
h
quadrangular
one
b

e
t
.
to
ro
one
and
extremit

y
ectiv
of
y
the
[
edge
n
and
=
to
0
view


quadrangulations
h
ev
stem
v
as
maps
a
greedily
single
,
half-edge
and
inciden

t
a
to
ertex
the
one.
no

de
to
holding
of
the
e
stem.
Q
More
set
generally

w
i
e

shall
v

h
maps
ot-
that
blac
ha
y
v
the
e
oted
entir
with
e
inner
e
j
dges

(made
that
of
ertex
t
A
w
is
o
the
half-edges)
v
and
hexagon
stems
degree
(made
these
of
are
only
t
one
t
half-edge).
hexagon.
It
F
is
MAPS
then
a
also
et
natural
quadrangulations
to
hereafter
asso
see

hellen
one
and

outer-triangular
to


quadrangulations
h

half-edge,
angular
sa
Giv
y
oted
,
Q
the
w

v
on
M
its
ro
righ
A
t.
V
In
N,
the
oted,

ectiv
of

trees,
of
there
hexagon
is
n
only
v
the
These
outer
v

n
so
2
that

all
to
half-edges
relation.
get
rom
the
w
same

asso
of

hexagon

y
2.3

Quadrangulations
simply
and
e
dissections
irr
A

quadr

angulation
The
is
of
a
oted
planar
quadrangulations
map
of
whose
oted

dissections
(including
resp
the
ely
outer
b
one)
Q
ha
=
v
n
e
0
degree
and
4.
0
A
[
disse
D

n
of
As
the
of
hexagon
and
by
ha
quadr
e
angular
en

the
es

is
these
a

planar
e
map

whose
y
outer
in

k
has
white,
degree
that
6
h
and

inner
blac

v
ha
to
v
white
e

degree
a
4.
is

up
that
the
do
hoice
not
the
delimit
W
a
denote

y
are
0
said
the
to
of
b
oted
e

sep
with
ar
blac
ating
v
.
and
A
white
quadrangulation

or

a
that
dissection
ro
of
v
the
is
hexagon
k;
b
b
y
D
quadrangular
ij

set
is
ro
said

to
dissections
b
i
e
k
irr
v
e
and

white
if
v
it
and
has
h
at
the
least
ot-v
4
is

k.
and

has
dissection
no

separating
if

three
The
white
rst


the
quadrangulation
ha
is
e
the
exactly

Hence,
e,
three
whic

h

has
to
6
w


W
edges
e
the
denote
3.
b
BETWEEN
y
AMILIES
Q
PLANAR
0
This
n

the
folklore
set
b
of
w
ro

oted
and

maps,
quadrangulations

with
mapping,
n
[Mullin

Sc

b
the

outer
its
one.
to
Euler's

relation
3.1
ensures
maps
that

these
Let
quadrangulations
rst
ha
ho
v
the
e
mapping
n
orks.
+
en
2
ro
v
quadrangulation

2
W
0
e
endo
denote
ed
b
its
y
ertex
D
let
n
b
(
the
D
oted
0
obtained
n
CM
)
Name,
the
ol.
set
No.
of
Mon
(ro
20YY.Dissections
and
trees
and
Pr
e

D
7

(a)
yields
A
t
quadrangulation
irr
(b)
th
with
a
its
ij
blac

k
dissection
diagonals
y
(c)
omplete
giv
outer-triangular
es
and
a
its
planar
3.1
map.
0
Fig.
etwe
2.

The
et
angular
v
mapping:
to
from
map
a

ro
map
oted
The

etwe
quadrangulation
vertic
to
vertic
a
lines
ro
Journal
oted


wing
planar
theory
map.
The
b
e-
y
0
linking,
a
for
ij

r
h
dissections


f
triangular
of
whic
Q
useful
(ev
is
en
giv
the

outer
b

k
the
e
t
see
w
the
o
(Angular
diagonally
mulate
opp
a
osed
e
blac

k
white
v
d

3
of
of
f
Theorem
;
erg
the
V,
ro

ot
order
of
The
M
is
is
in

maps.
hosen
mapping)
to
mapping
b

e
en
the
and
edge
and

e
onding

to
P
the
Q
outer
3.2

maps
of

Q
same
,

orien
mapping,
ted
een
so
maps
that

M
will
and
v
Q

ha
This
v
ery
e
angular
same
a
ro
,
ot-v
D
ertex,
ob-
see
linking
Figure
o
2.

The
inner
map
D
M
new
is
3.
often
is

map
the
Theorem
primal
with
map
mapping,
of
for
Q

.

A

similar



using
i
white
and
v
es

onne
instead
with
of
and
blac

k
The
ones
ws
w
that
ould
see
giv
hellen
e
A
its
V
dual
N,
map
in
(i.e.,

the
kwise
map
around
with
origin.
a
follo
v
theorem
ertex
a
in
result

the
h
of

Theorem
of
(Angular
M
.
and
angular
edge-set
is

bije
onding
b
to
twe
the
P

n
b
Q
et
n
w
mor
een
pr
v


bije
and
b

en
of
0
M
and
).
0
The
.

Outer-triangula
of

the
and
primal
red
map

is
The
easily

in
a
v
also
ertible.
angular
Giv
b
en
w
an
outer-
y

ro
and
oted

map
dissections,
M
h
,
pro
the
e
in
ery
v
in
erse
7

8.

mapping
in
v
adding
similar
a
the
v
mapping:
ertex
en


a
D

asso
e-vertex
to
in
the

M
h
tained

y
(ev
the
en
w
the
blac
outer
v
one)
of
of
h
M

and
of
linking
b
a
a
v
edge,
ertex
Figure
v
The
and
M
a


primal
ertex
of
v
.
f
3.2
b
mapping
y
border).
an
angular
edge
for-
if
d
v

is
disse

is
t
bije
to
b
the
en

olor
f
d

omplete
onding
e-
to
disse
v
with
f
black
.
es
Keeping
j
only
vertic
these
and


v

ertex
maps

i
edges
es
yields
j
a
inner
quadrangulation.
es.
The
oof.
ro
pro
ot
follo
is
similar

as
hosen
of
as
3.1,
the
[Mullin
edge
Sc
that
b
follo

ws
CM
the
Name,
ro
ol.
ot
No.
of
Mon
M
20YY.8

?ric
F
dge
dual
dissections.
usy
the
et

al.
link
(a)
ed
A
example,
dissection,
dual
(b)
ertex
blac
of
k
primal
diagonals,
f
(c)
v
the
M

3(d).
map,

(d)
of
the
ed
deriv
one
ed
D
map.

Fig.

3.
o
The
h
angular
ertex
mapping
eeping
with
and
b
h
order:
to
from
of
a
vertic

M

primal

the
dissection
has
(a)
primal
to
V,
an
v
outer-triangular
maps


map
ed
(c).
as
The
f

o
deriv
f
ed
and
map
y
is
w
sho
w
wn
at
in
dge-vertex
(d).
obtained
3.3
dual
Derived
three
maps
edges.
In
regularit
its
outer
v
an
ersion
outer
for
map

sho
dissections,

the
v
angular
the
mapping
submap

0
also
primal
b
dual
e
the
form
map.
ulated

using

the
e

Journal
of
th
deriv
a
ed
Similarly
map,
deriv
whic

h
en
will

b
the
e
M
v
is
ery
ws;
useful
inner
throughout
D
this
t

k
(in
t
particular
y
when
dge
dealing
t
with
ones
orien
dual
tations).
These
Let
edges,
M
the
b
diagonals
e
in
an
new
outer-triangular
an

The
map,
is
and
y
let
primal
M
and


b
white
e

the
,
map
e
obtained
,
from
the
the

dual

of
half-edge
M
ard
b
F
y
deriv
remo
the
ving
3(a)
the
in
dual
k
v

ertex
and

are
onding
es
to
ed
the
.
outer
(

of
of
of
M

.
(resp.
Then

the
is
derive
map
d
map
map
deriv
M
,
0
triangular
of
b
M

is
and
the
ha
sup
same
erimp
A
osition
V
of
N,
M
edge-v
and
and
M
dual

ertex.
,
,
where
denes

ed
h
of
outer

v
Giv
ertex
a


es
dissection
an
,
additional
deriv
half-edge
map

0
to
D
w

ard
follo
the
for
outer
h


F
of
or
,
example,
the
Figure
w
3(d)
blac
sho
v
ws

the
to
deriv
b
ed
a
map
e
of
,
the
the
map
w
giv
white
en
b
in
a
Figure
e

.
The
t
map
o
M
whic
is
are

t
the
o
primal
of
map
,
of
tersect
M
a
0
v
and

the
e
map
.
M
deriv

map
is
then

b
the
k
dual
the
map
and
of
edges
M
all
0

.
the
Observ
outer
e
ones
that
their
the
t
sup
Finally
erimp
for
osition
sak
of
of
M
y
and

M
of

six

v
a
of
v
0
ertex
es
of
additional
degree

4
w
for
the


h
or
edge
the
e
ed
of
of
M
dissection
,
Figure
due
is
to
wn
the
Figure
in
Blac
tersection
v
of
are
e
primal
with
es
its
white
dual

edge.

These
vertic
v
of

deriv
of
map
M
0
0
The
are
M

M
e
)
dge-vertic
M
es

.
the
An
v
edge
and
of
edges
M
the
0
v
either
and

edges)
onds

to
primal
an
(resp.
half-edge
dual
of
)
M
the
when
ed
it
Clearly

M
an
a
edge-v
outer
ertex
and,
and
y
a
a
primal

v
dissection
ertex,
its
or
map
to
v
an
the
half-edge
deriv
of
map.
M
CM

Name,
when
ol.
it
No.

Mon
an
20YY.Dissections
and
trees
e
e
ounded

the
9
to
(a)

A
n
binary
2
tree,
length
(b)

a
Journal
lo


to


(c)
um
and
inner
the
Let
partial
als

the
Fig.
the
4.
s
The
paren
partial


the
4.
to
BIJECTION
binary
BETWEEN
outer
BINARY
b
TREES
tire
AND
the
IRREDUCIBLE
v
DISSECTIONS
outer
4.1

Closure
er
mapping:
um
from
um
trees
r
to
.
dissections
t
Lo
of

for
and
is
pa
th
rtial
An

in
Giv
w
en
obtain
a

map
an
with
edge
en
Observ
tire
n
edges
and
and

stems
1
(for
and

er
a
k
tree),

w
T
e
en
dene
in
a

lo
terv

2,
al
b

the
e
in
op
b
eration,

whic
(that
h
no
is
unmatc
based

on
2
a


stems

of

y
kwise

w
illustrates
alk
r
around
and
the
Figure
map:
V,
this
of
w
w
alk
of
alongside
sho
the

b
us
oundary
the
of
eration
the
dissection
outer
with
map
outer
visits
dge
a
b

en
of

stems
outer
and
that
en
T
tire
des
edges,
2
or
n
more
tire
precisely
lo
,
b
a
n

of
of
y
half-edges
um
ha
outer
ving
Hence,
the
the
outer
er

stems
on

their
there
righ
6
t-hand
half-edges.
side.
stems
When
als
a
on
stem
of
is
these
immediately
ha
follo
at
w
a
ed
w
in
p
this
b
w
um
alk

b
als
y
and
three
the
en
er
tire
in
edges,
length
its
the
lo
er



w

stems).
in
s
the
b

r
of
=
an

opp

osite
unmatc
half-edge
half-edges
for
v
this
hexagon
stem,
w
whic
to
h
hexagon)
is
quadrangular

Figure
hed

to

farthest
2
endp
2)
oin
particular
t
en
of
A
the
V
third
N,
en
hings
tire
the
edge:
thesis
this
ord.
amoun
example
ts
partial
to
is

wn
the
Figure
stem
Complete
in
Let
to
no
an

en
partial
tire
op
edge,
to
so
a
as
of
to
hexagon

quadrangular
or
An

entir

half-e
a
is
quadrangular
half-edge

elonging
This
an
op
tire
eration
and
is
t
illustrated
the
in

Figure
e
4(b).
a
Giv
tree
en
with
a
no
binary
has
tree
+
T
stems
,
2
the
2
lo
en

half-edges.

h


b

e
y
p
the
erformed
um
greedily
er
un
stems
til
b
no
2
more
n
lo
b

of

en
is
half-edges.
p
if
ossible.
denotes

n
h
b
lo
of

hed)

in

partial
a
of
new
,
en
are
tire
k
edge,
outer
ma
tire
yb
Moreo
e
er,
making
delimit
a
terv
new
of
lo
half-edges

the

tour
p
the
ossible.

It
in
is
als
easy
v
to
length
see
most
that
otherwise
the
lo
nal

map,
ould

e
the
ossible.
p
r
artial
e

n
e
b
of
of
T
h
,
terv
do
of
es
1
not
s
dep
e
end
n
on
b
the
of
order
h
of
terv
the
of
lo
0

is,

n
Indeed,
b
a
of

des
paren
t
thesis
t
w
o
ord
hed
is
Then
asso
and

are
to
related
the
y

relation

+

s
kwise
6
b
The
oundary
omplete
of
e
the
in
tree,
all
with
hed
an
with
op

ening
to
paren

thesis
the
of
in
w
unique
eigh
a
t
(up
3
rotation
for
the
a
that
stem
only
and
b
a


5(a)
paren
the
thesis

for
the
a
(
side
=
of
;
en
=
tire
,
edge;
a
then
example
the
giv
future
in
lo
5(b).

CM

Name,

ol.
ond
No.
to
Mon
matc
20YY.10

?ric
F
the
if
outwar
usy
that
et
V,
al.
v
its
oriente
a
to
w
half-edges
see
inner
orien
is
dissection
(a)
with

edges

orien
when
of
r
half-edges,
=
n
2
tri-orientation
and
that
s
of
=
to
2
ely
.
inner
(b)
An
Case
ha
of
other
the
w
binary
A
tree
are
of
righ
Figure
of
4(a).
An
Fig.
d
5.
ard
The
is

a

orien
Lemma
e
4.1.
naturally
The
of

w
e
tree
of
its
a
de
binary
an
tr
an
e
half-
e
h
is
v
an
3,
irr
half-edges
e
b

ard,
disse
to

t
of

the
w
hexagon.
ard),
Pr
oth
oof.
b
Assume
with
that

there

exists
or
a
of
separating
Journal

th
C
tation,
in
orien
the
is

e
of
it
T
to
.
origin
Let
if
m
ted

origin.
1
is
b
with
e
of
the
outde
n
of
um
v
b
as
er
b
of

v
ted

The
in
a
the
dened
in
tation
terior

of
y
C
outdegree
.
6(a)
Then
A
there
dissection
are
tation
2
half-edges
m
b
edges
edges)
in
outer
the

in
resp
terior
0
of

C
w

a
to

Euler's
b
relation.
in
Let
Figure
v
is
b
e
e
if
a
o
v
e
ertex
is,
of
ted
T
and
that
out
b
bi-oriente
elongs
are
to
ted
the
Let
in
an
terior
w
of
tri-orien
C

after
D
the


edges
Consider
bi-orien
the
orien
orien
in
tation
on
of
A
edges
V
of
N,
T
notion
a
orien
w
where
a
are
y
ted).
from
half-edge
v
said
(only
b
for
inwar
the
if
sak
is
e
ted
of
w
this
its
pro
and
of
d
).
it
Then
orien
no
out
des
its
of
If
T
map
ha
endo
v
ed
e
an
outdegree
tation
2,
its

the
v
gr
,
e
whic
a
h
ertex
has
is
outdegree
dened
3.
the
This
um
orien
er
tation
its
naturally
t

orien
an
out
orien
ard.
tation
(unique)
of
of
edges
binary
of
is
the
as

orien
with
of
the
half-edges
same
h
prop
an
ert
no
y
has
(except
3,
that
Figure
v
for

example.
of
tri-orientation
the
a
hexagon
is
ha
orien
v
of
e
inner
outdegree
(i.e.,
0).
edges
Hence
elonging
there
inner
are

at
that
least
and
2
v
m
ha
+
e
1
ectiv
edges
outdegree
in
and
the
and
in
h
terior
t
of
o
C
of
,
same
a
edge

not
tradiction.
oth
4.2
e
T
ted
ri-o
w
rientations
see
and
6(b).
op
edge
ening
said
T
b
ri-o
simply
rientations.
d
In
its
order
w
to
half-edges
dene
v
the
same
mapping
(that
in
one
v
orien
erse
in
to
ard
the
the

one
w
w
e
and
need
d
a
they
b
b
etter
orien
description
out
of
ard.
the
D

e


on
endo
the
ed

a
map
tation.
b

y

the
of
original
is
tree.
simple
Let
C
us
of

that
orien
either
tations
ted
of
simply
the
ted
half-e
the
dges
terior
of
C
a
their
map
t.
(in
CM

Name,
trast
ol.
to
No.
the
Mon
usual
20YY.