Path Graphs, PR-trees, and Split Decomposition
Speaker: | Steve Chaplick |
---|---|
Affiliation: | Wilfrid Laurier University |
Room: | Mathematics & Computer Building (MC) 5158 |
Abstract:
Path
graphs
are
the
intersection
graphs
of
paths
in
trees.
In
this
talk
we
introduce
a
new
data
structure,
the
PR-tree,
to
characterize
the
sets
of
path-tree
models
of
path
graphs.
We
then
describe
an
O(nm)
time
algorithm
to
construct
a
PR-tree
from
a
given
graph
via
Split
Decomposition
(note:
this
matches
the
best
known
recognition
algorithm
for
path
graphs).
From
this
algorithm
we
provide
a
new
characterization
of
path
graphs
by
split
decomposition.
Finally,
we
show
that
an
implicit
form
of
the
PR-tree
can
be
represented
in
O(n)
space.
Note:
for
those
familiar
with
PQ-trees
and
interval
graphs
(i.e.,
the
intersection
graphs
of
subpaths
of
a
path),
the
PR-tree
represents
path
graphs
in
the
same
way
that
the
PQ-tree
represents
interval
graphs
(i.e.,
the
PQ-tree
of
an
interval
graph
G
represents
the
set
of
all
permutations
of
the
maximal
cliques
of
G
where
the
maximal
cliques
incident
with
each
vertex
occur
consecutively).