Planar Graphs via Well Orderly Maps and Trees

Cyril Gavoille

Description

Niveau: Supérieur
Planar Graphs, via Well-Orderly Maps and Trees Ni olas Boni hon 1 , Cyril Gavoille 1 , Ni olas Hanusse 1 , Dominique Poulalhon 2 , Gilles S haeer 3 1 Laboratoire Bordelais de Re her he en Informatique, Universite Bordeaux I, Fran e fboni hon, gavoille, hanusseglabri.fr 2 Laboratoire d'Informatique Algorithmique, Fondements et Appli ations (LIAFA) ase 7014, 2, pla e Jussieu, 75251 Paris Cedex 05, Fran e poulalhonliafa.jussieu.fr 3 Laboratoire d'Informatique de l' E ole Polyte hnique (LIX) E ole polyte hnique, 91128 Palaiseau Cedex, Fran e gilles.s haeerlix.polyte hnique.fr Abstra t The family of well-orderly maps is a family of planar maps with the property that every onne ted planar graph has at least one plane embedding whi h is a well-orderly map. We show that the number of well-orderly maps with n nodes is at most 2 n+O(log n) , where 4:91. A dire t onsequen e of this is a new upper bound on the number p(n) of unlabeled planar graphs with n nodes, log 2 p(n) 6 4:91n.

• onne ted


• planar graph


• orderly map


• no known


• planar graphs


• all interior


• well-orderly maps


• priori no unique

Sujets

• Planar graph

Informations

• Publié par: chaeh
• Nombre de lectures: 7
• Langue: English

Extrait

Planar
Graphs,
via
of
MSW05],
82
W
b
ell-Orderly
edding
Maps
des
and
n
T

rees
27

orst-case,

tro
hon
is
1
on
,
as
Cyril
that
Ga
asymptotic
v
tly
oille
from
1
unlab
,
p

planar
Han
er
usse
ed
1
asymptotic
,
upp
Dominique

P
n
oulalhon
n
2
sup
,
MSW05]).
Gilles
b
Sc
n
haeer
has
3
e
1
on
Lab
More
oratoire

Bordelais
using,
de
4

and
herc
edge.
he
w
en
the
Informatique,
graphs
Univ
ell-kno
ersit
(cf.


e
n
Bordeaux
graphs.
I,
w
F
r
rance
b
f
eled
b
gro
onic
n
hon,
,
ga
27.2268
v
men
oille,
limit
han
er
usse
on
g
eled

form
2
n
Lab
trivial
oratoire
en
d'Informatique

Algorithmique,
of
F
upp
ondemen
to
ts
ding
et
a
Applications
explicit
(LIAF
algorithm
A)
planar

the
7014,
rate
2,
91
place
no
Jussieu,
2
75251
p
P
w
aris
triangulation,
Cedex
1.
05,
Coun
F
um
rance

p
n

a
3
long-standing
Lab
umeration
oratoire
W87]).
d'Informatique
kno
de
ula
l'
for

b
Ecole
eled
P
are
olytec
and
hnique
b
(LIX)
gr

of
Ecole
n
p
p
olytec
of
hnique,
graphs
91128
des.
P
rate,
alaiseau
=
Cedex,
p
F
1
rance
tly

w

32.1556
olytec
y
hnique.fr
sho

h
The
[D
family
lo
of
ound
w
from
ell-orderly
n
maps
of
is
graphs.
a
of
family
!
of
o
planar
[D
maps
a
with
of
the
een
prop
℄
ert

y
ga
that
precise
ev

ery
2268777685.

b
planar
,
graph
℄
has

at
planar
least
,
one
em
plane
an
em
linear-time
b
ding
edding
for
whic
eled
h
graphs
is
in
a
w
w
a
ell-orderly
of
map.
:
W
bits
e
er
sho
de
w
of
that
:
the
bits
n
er
um
Key
b
ords.
er
graph,
of
realizer,
w
ell-orderly
ell-orderly
In
maps

with
ting
n
n
no
b
des
of
is
planar
at
with
most
no
2
is
n
w
+
wn
O
unsolv
(log
graph-en
n
problem
)
[L
,
There
where
no

wn

form
4
or
:
estimate
91.
the
A
um

er

unlab
of
planar
this
There
is
only
a
er
new
lo
upp
er
er
ounds
b
the
ound
owth
on
ate
the
the
n
of
um
um-
b
ers
er
(
p
)
(
unlab
n
planar
)
with
of
no
unlab
This
eled
wth
planar
dened
graphs

with
lim
n
!1
no
(
des,
)
log
=n
2

p
ranges
(
et
n
een
)
and
6
(a
4
eradditivit
:
argu-
91
t
n
ws
.

The
a
result
exists
is
VW96,
then
The
used
w
to
b
sho
on
w

that
asymptotics
asymptotically
the
almost
um
all
er
(lab
lab
eled
planar
or
This
unlab
is
eled),
the
(con-
n


or
+
not)
(
planar
)
graphs
VW96,
with
and
n
non
no
estimation
des

ha
b
v
giv
e
in
b

et
[GN]
w
determined
een
and
1
v
:
a
85
estimation
n
it:
and

2
:
:
The
44
er
n
ound
edges.

Finally
due
w
[BGH03
e

obtain
a
as

an
of
outcome
graphs.
of
precisely
our
after

suitable
binatorial
b
analysis
and2


random
ounds
ed
hon
e
et
that
al.
m=
triangulation
al.
of
sho
the
eled
planar
tation
graph,
based
it
or
is
v
sho
ha
wn
in
that
eled

w
h
℄
em
normal
b
an
eddings
Munro

of
b
trees
e
v
represen
generation
ted
simple
b
erimen
y
Bo
a
generator
binary
the
string
b
of
.
length
edges
at
2
most
70
5
and
:
in
007
21
n
graphs
bits.


ok
h
2
a
planar
represen
98
tation
spanning
implies
ed
that
an
p
kno
(
w
n
has
)
last
6

2
w
5
lab
:
n
007
[BGK03
n
p

planar
(32
ts
:
of
1556)
actually
n
in
.
more
T
pro
ec
um
hnically
lab
,
85
en
℄
umerating
ounds
unlab
:
eled
tly
graphs
℄
is
b
more
planar
Æ
(
than
v

de
ting
history
the
a
lab
b
eled
Keeler
v
:
ersion.
then
And,
n
as
em
p
℄
oin
al.
ted

out
n
in
of
℄
e
almost
.
all
k
lab
mo
eled
little
2-
ab
and
graphs.

er,
planar
planar
graphs
een
ha
in
v
Using
e
o
exp
Denis
onen
℄
tially
that,
large
,
automorphism
planar
groups.
e
In
In
other
et
w
ha
ords,
the
W
(uniform)
righ
lab
t's
Although
Theo-
exp
rem
b
[W

ri71
algorithm),
℄
ed
do
n
es
of
not
random
hold
graph
for
2
random
b
planar
ed
graphs;
the
the
er
asymptotic
a
n
planar
um
1
b
[GM02]
er
54
of
the
lab
these
eled
1
and
and
unlab
n
eled
ery
planar

graphs
y
dier
w
in
n
more
of
than
lab
the
is
n
linear
!
2

)
i.e.,


n
<
-edge

a
.
T
So,
℄
an
m
asymptotic
that
on
impro
the
b
n
W
um
to
b
m
er
Raman
of
osed
lab
+
eled

planar
the
graphs
edding
w
(see
ould
a
not
Lu
giv
CGH
e
rened
a
to
sharp
+
lo
to
w
a
er
hn
b
h90
ound
describ
on
precisely
the
F
gro

wth
of
rate
adequate
of
del,
p
ery
(
is
n
wn
).
out
The
planar
situation
Ho
with
ev
resp
random
ect
of
of
graphs
the
b
upp
in-
er
estigated
b
the
ound

is
a
not
Mark
b
v
etter.
hain,
A
et
planar
[D
graph
sho

ed
b
exp
e
tally
em
random
b
eled
edded
graphs
in
v
man
2
y
edges.
w

a
dirsky
ys,
al.
and
℄
to
v

designed
v
rst
er
olynomial-time
the
random
graph
of
from
eled
a
graphs.
suitable
limited
triangulation
their
requires
erimen
a
(mainly
deep
y
understanding
time
of
y
plane
this
triangulations,
they
in
w
particular
that
their
the
en
um
umeration
er
with
edges
resp
a
ect
lab
to
planar
sev
is
eral
than
parameters
n
dep
The
ending
est