Planar Graphs via Well Orderly Maps and Trees

-

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

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


Subjects

Informations

Published by
Reads 7
Language English
Report a problem

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
on
v
the
b
input
on
graph.
n
Besides
b
the
of
pure
in

random
binatorial
eled
asp
graph
ect,
ere
the
:
\enco
n
ding"
and

:
h
n
is
for
also
unlab
relev

an
b
t
are
in
:
Com-
n
puter
2
Science
54
where
[BGH03
a
V
lot

of
Gim
atten
enez
tion
No
is
[GN
giv
sho
en
ed
to
the
the
um

er
t
edges
represen
random
tation
eled
of
graphs
discrete
asymptotically
ob
with

mean
A

t
:
least
n
t
and
w
ariance.
o
represen
elds
of
of
-no
application
m
of
planar
high
has
in
long
terest
.
are
ur

[T
with
pioneered

4
planar
-bit
graph
ding
represen
has
tation:
een
Computer
v

later
[KADS02,
y
KR99
and
,
estbro
Ros99
[KW95]

3
and
58
Net
.
w
and
orking
[MR97]
[FJ89,
prop
GH99
a
,
m
Lu02,
8
Tho01].
bit
1.1.
ding
R
on
elate
4-page
d
b
Works
of
Ob
graphs
viously
[Y
,
In
without
series
a

sharp
et
asymptotic
[CLL01,
form
+
ula,

prop
the
erties
ding
and
4
b
3
eha
5
vior
thanks
of
orderly
large
trees,
random
generalization
ob
Sc

yder's


b
℄Planar
Graphs,
via
p
n
e
W
a
ell-Orderly
at
Maps
Apart
and
b
T
een
rees
upp
3
this
1.2.
graph
Our
n
R
82
esults
3
An
organized
y

planar
of
em
W
b

edding
maps,
of
planar
an
plane
n
discs.
-no
(30
de
bits
planar
than
graph
with

the
b
ted
e
in
seen
hn
as
and
a
graphs
subgraph
en.
of
area
an
b
n
n
-no

de
[BGH03
triangulation
paragraph,
of
Gr
the
an
plane.
only
Giv

en
nen
a
d
triangulation
of
and
4
a
or
set
(clearly
of
alw
edges
+
to
y
b
v
e
new
k
er
ept
planar
(or
The
remo
W
v
relationships
ed),
sup
a

planar
ted
map
the
and
of
the
n

planar
onding
our
graph
on

triangulation
b
that
e
on

n
The
and

using
v
with
erse

is
planar
false
realizers.
in
used
general.
tation
There
l-Or
is
gr
no
of
kno
so
wn
oin
metho
the
d
are
to
b
uniquely

asso
is

its
a
b
triangulation
log
to
061)
a
91
planar
no
graph.
:
Ho
er
w
2
ev
bits
er,
ys
in
m=
[BGH03
n

for
a
planar
linear-time
least
algorithm
m
is
6).
giv
ound
en
um
to
edges

unlab
a
is
triangulation
w
of
er
the
follo
plane
describ
in
2
a
et

ell-orderly
w
and
a
trees,
y
The
for
is
an

y

planar
to
graph,
b

eled
giv
to
en
b
a
in
planar
are
em
application
b
is
edding.
b
The
minimal
reader
a
should
the
k
sho
eep
triangulations
in
dra
mind
of
that
7
there
7
is
straigh
a-priori
16
no
6
unique
olylines.
em
Planar
b
Realizers
edding
w
of
results
a
ab
planar
w
graph.
er-triangulations
Some
the
pla-
results
nar
pro
em
new
b
2.1.
eddings
and
ha
Maps
v
(or
e
)
in
b
teresting

graph
the
prop
edges
erties
their
based
When
on

the
the
Sc
onen
hn
the
yder's
the
partition


all
h90
homeomorphic

planar
of
o
triangulations
one
in
the
to
um
trees.
er
A
edges:
new
2

:
of

planar
:
em
bits
b
er
eddings
de
is
2
prop
82
osed
p
in
edge

,
the
:
wel
m
l-or
is
derly
a
maps
smaller
,
4
a
3
more
5

bits
e
ecause,
v
an
ersion

of
graph
the
at
or
3
derly

maps
6
of
n
Ch
A
uang
b
et
on
al.
n

b
The
of
t
of
w
random
o
eled
main
graph
prop
presen
erties
as
of
ell.
w
pap
ell-orderly
is
maps
as
that
ws.

e
b
e
e

exploited
the
for
b
graph
w

w
ding
maps,
are:
er-triangulations
1)
Sc
ev
yder's
ery
also
planar
realizers.
graph
new
admits
ding

presen
h
in
an
3,
em
in
b
4
edding,
applications
and
the
2)
um
giv
er
en
unlab
a
planar
w
and
ell-orderly
the
map,
um
w
er
e
edges

random
uniquely
graphs
asso
giv

Another
a
of
triangulation.
results
The
an
main
er
result
ound
of
the
this
grid
pap
of
er
random
is
of
to
plane.
giv
e
e
w
a
plane
go

o
e
d
wn
appro
grids
ximation
dimensions
for
most
the
8
n

um
8
b
using
er
tlines
of
11
w
n
ell-
5
orderly
n
maps.
p
As
2.
a
ding
b
Graphs
y-pro
Minimal

In
it

giv
e
es
some
a
from
new

upp
out
er
graphs,
b
ell-orderly
ound
sup
on
and
the
In
n
last
um
these
b
are
er
to
of
v
planar
a
graphs:
represen
p
theorem.
(
Planar
n
aphs
)
Wel
6
derly
30
A
:
map
061
plane
n
aph
.
is
More
em
in
edding
terestingly
a
,
planar
the
on

plane
binatorial
that
analysis
meet
enables
at
us
endp
to
ts.
giv
the
e
is
an
along
explicit
edges,

remaining
ding

of
ts


h

maps
from
(and
un
th
ounded
us
o-
of
t,
planar
these
graphs)
are
as
to
a
A
function
map
of
r
n
ote
and
if
m
of
,
edges4


hon
the
is
des,
et
H
al.
r
is
in
distinguished
2
and
H
orien
G
ted.
In
This
T
determines
its
a
in
r
v
o
of
ot
a
e
d
dge
map
,
ot
a
one
r
tree
o
unrelated
ot
alizers
no
three
de
{
(its
en
origin)
prop
and
.
a
e
r
resp
o
r
ot
.

et
e
e
(to
ar
its
e
left),
l-or
also
e

T
the
that
external
related

a
e
tree
or
father.
outerfac
are
e
alizer
.
not
A
T
triangulation
in
of
edges
the
1
plane
in
(or
it
a
the
maximal

plane
spanning
graph)
l-or
is
all
a
ell-orderly
planar
.
map
l-or

if
h
with
that
a
all
1.
the
a

and
are
of
triangles.

In
a
this
ot
pap
l-or
er,
has
only
e
simple

planar
in
graphs
w
or
same
maps
ell-orderly
are
of

H
A
to
plane
endp
tree
the
is,
b
as
all
usual,
no
a
the
ro
ro
oted
2.2.
tree
riangulations
(the
is
ro
(the
ot
external
is
,
a
edges
no
hold
de)
v

kwise
h
v
that
en
the
in
siblings
0
of
en
a
),
no
has
de
y
are
t
linearly
is
ordered.
v
Equiv
ro
alen
T
tly
a
,
tr
it
H
is
no
a
are
planar
H
map
to
with
planar
one
a

map
Among
ot
the

no
ell-orderly
des
ot
of
e
a
ell-orderly
tree,
spanning.
w

e
b
distinguish
onne
the
gr
ro
v
ot,
no
the
.
inner
a
no
in
des
that
and
l-or
the
r
lea
.
v
a
es.
map
A
ot
spanning
unique
tree
tr
of
r
a
,
planar
also
map
ompute
is
ar
a
1
subset
orderly
of
span
its
but
edges
the
that
Observ
forms
y
a
ell-orderly
tree
edge

h
all
resp
its
w
no
(i.e.
des.
t
Let
t
T
one
b
m
e
to
a
:
ro
are
oted

spanning
to
tree
particular
of

a
to
planar
of
map
T
H
R
,
Sup
and
r
let
a
v
partition
1
terior
;
that
:
on
:
in
:
T
;
1
v
of
n
h
b
wing
e

the
no

Fig.


kwise
of
preordering
t
of
lea
the
0
no
in
des
lea
in
2
T
in
.
lea
Tw
1
o
in
no
i
des
if
are
exists,
unr
the
elate
ert
d
that
if
paren
neither
of
of
j
them
an
is
of
an
i

A
of
oted
the
tree
other
of
in
is
T
wel
.
derly
An
e
edge
of
of
if
H
the
is
des
unrelated
T
if
w
its
in
endp
with
oin
ect
ts
T
are
A
unrelated.
map
A
is
no
wel
de
derly
v
with
i
o
is
v
or
it
derly
tains
in
w
H
tree
with
ro
resp
v
ect
Observ
to
that
T
w
if
tree
the

edges
Theorem

([BGH03
t
L
to
G
v
e
i

in

H
planar
form
aph,
the
let
follo
b
wing
any
four
de
(p
G
ossibly
Then
empt
admits
y)
map,
blo
omputable

line
ks
time,
in
is

wel

derly
kwise
of
order
o
around
v
v
Mor
i
over,
(see
wel
Fig.
derly
2(b)):
of
{
o
B
v
P
a
(
wel
v
derly
i
e
):
of
the
o
edge
v

which
t
an
to
b
the

paren
d
t
line
of
time.
v
Fig.
i
t
in
o
T
trees
;
0
{
the
B
triangulation
<
only
(
is
v
w
i
tree.
):
e
edges
b
that
denition
are
w
unrelated
no
in
an
T
of
and
whic

is
t
with
to
ect
no
a
des
ell-orderly
v
T
j
one
with
oin
j
is
<
descendan
i
of
;
other
{
in
B
)
C
ust
(
elong
v
the
i
T
):
indeed
edges
edges
that
either
are
or

a
t
de
to
its
the
In

all
hildren
edges
of
t
v
H
i
the
in
ot
T
T
;
in
and
.
{
Minimal
B
e
>
and
(
er-T
v
A
i
e
):
of
edges
triangulation
that
a
are
of
unrelated
in
in
edges
T
edges
and
do

lie
t
the
to

no
to
des
sets
v
0
j
T
with
,
j
2
>

i

.
that
A
follo
no

de
for
v
h
i
terior
is
de
wel
(see
l-or
2(a)):
derly
the
if

it
order
is
the
orderly

and
with
if
is:
the
ving

T

,
kwise
tering
rst
T
edge
,
(
ving
v
T
i
,
;
tering
v
T
j
,
)
ving
2
T
B
and
>
tering
(
T
v
;