Labeling Schemes for Tree Representation

This paper deals with compact label-based representations for trees. Consider an

n

-node undirected connected graph

G

with a predefined numbering on the ports of each node. The

all-ports

tree labeling

${\mathcal L}_{all}$

gives each node

v

of

G

a label containing the port numbers of all the

tree

edges incident to

v

. The

upward

tree labeling

${\mathcal L}_{up}$

labels each node

v

by the number of the port leading from

v

to its parent in the tree. Our measure of interest is the worst case and total length of the labels used by the scheme, denoted

M

up

(

T

) and

S

up

(

T

) for

${\mathcal L}_{up}$

and

M

all

(

T

) and

S

all

(

T

) for

${\mathcal L}_{all}$

. The problem studied in this paper is the following: Given a graph

G

and a predefined port labeling for it, with the ports of each node

v

numbered by 0,...,deg(v) – 1, select a rooted spanning tree for

G

minimizing (one of) these measures. We show that the problem is polynomial for

M

up

(

T

),

S

up

(

T

) and

S

all

(

T

) but NP-hard for

M

all

(

T

) (even for 3-regular planar graphs). We show that for every graph

G

and port numbering there exists a spanning tree

T

for which

S

up

(

T

) =

O

(

n

log log

n

). We give a tight bound of

O

(

n

) in the cases of complete graphs with arbitrary labeling and arbitrary graphs with symmetric port assignments. We conclude by discussing some applications for our tree representation schemes.