Deza M.M., Laurent M. Geometry of Cuts and Metrics
Подождите немного. Документ загружается.
21.3
Proofs
323
Using
7/Ji,
by
the
construction
of
Section 21.2, we
obtain
the
graph
a.pi'
which
is
A-embedded
into
the
hypercube
H(ni)
via
;jji.
By
the
minimality
of
the
graphs
a.p1,a.p2
(see
Claim
21.2.10),
we
deduce
that
<p
establishes
the
equivalence
of
the
embeddings
;jji
and
;jj2'
Hence, a is
iI-rigid.
This
shows
Corollary
21.1.6.
Corollary
21.1.7 now follows easily.
Indeed,
if
G is
iI-rigid,
then
a is
iI-rigid,
which
implies
that
each factor a
h
is
iI-rigid
(as a
product
of
graphs
is
iI-rigid
if
and
only
if
each
factor is
iI-rigid;
see
Proposition
7.5.2). Therefore, each
ah
is one
of
the
following graphs: K
2
, K3, K3x2,
or
~H(m,
2)
for m
;:::
5,
which
are
all
hypercube
embeddable
with
scale
2.
Therefore, G is
hypercube
embeddable
with
scale 2, i.e., G is
an
isometric
subgraph
of
a half-cube
graph.
I
Proof
of
Corollary 21.1.8.
Suppose
G
has
n nodes.
If
some
factor
a
h
is a cocktail-
party
graph
Kmx2'
then
m <
n.
Hence,
by
Lemma
7.4.4,
ah
is
hypercube
embeddable
with
scale 2
k
-
l
,
if
2
k
-
1
< n - 1
::;
2k.
All
other
factors
are
also
hypercube
embeddable
with
scale 2
k
-
1
since k
;:::
2 as n
;:::
4. Hence, G is
hypercube
embeddable
with
scale 2
k
-
l
,
which implies
that
its
minimum
scale
1)
satisfies:
1)
::;
2
k
-
1
< n -
1.
I
Proof
of
Proposition 21.1.10. Let G = (V,
E)
be
a
connected
graph
on
n nodes
and
m edges. All
the
ingredients for
constructing
an
algorithm
permitting
to
recognize
whether
G is
an
isometric
subgraph
of
a half-cube have
been
essentially
given earlier, especially
in
Remark
21.2.12
(taking
A = 2). We
describe
the
main
steps
of
the
proof.
Let
Xo
be
a given
node
of
G. Given two edges e,
e'
in
G, we
remind
the
defini-
tion
of
the
quantity
(e,
e') from
relation
(21.2.13); recall
that
(e,
e')
E
{O,
±1,
±2}.
Moreover,
if
e:=
(x,y)
and
e':=
(x',y') are
such
that
dG(xo,y) = dG(xo,x) + 1, da(xo,Y') = dG(xo, x') + 1
(Le.,
if
e, e'
belong
to
the
set
Eo
defined
in
(21.2.1)),
then
(e,
e')
;:::
°
in
the
case
when
G is
an
isometric
subgraph
of
a half-cube
graph.
A "trick" used
in
Deza
and
Shpectorov
[1996]
in
order
to
reduce
the
complexity
is
to
consider a
spanning
tree
rather
than
the
entire
set
Eo.
The
algorithm
consists
of
the
following
steps
(i)-(v).
(i) Let T
= (V, ET)
be
a
spanning
tree
in
G
such
that
dT(XO,
x) =
dG(xo,
x) for all nodes x
in
G.
(Such
a
tree
can
be
constructed
in
Oem)
time
using a
breadth
first
search
algo-
rithm.)
(ii)
For
any
two edges e =
(x,y),
e' = (x',y') E ET (such
that
Xo
E
G(x,y)
n
G(x', y')) check
whether
(e,
e') E
{O,
1, 2}.
If
not,
then
G
cannot
be
isometrically
embedded
in
a half-cube
graph.
(iii) Define a
relation",
on
ET
by
letting
e
'"
e'
if
(e,
e') =
2.
324
Chapter
21. fil-Graphs
Verify
that
this
relation
is
an
equivalence relation
on
ET.
If
not,
then
G
cannot
be
isometrically
embedded
in a half-cube graph.
(iv) Define a
graph
~
on
the
set of equivalence classes of
(ET'
~),
where
there
is
an
edge between two classes e
and
e
l
if
(e,
e
/
) =
1.
Check
that
this
graph
is
well defined, i.e.,
that
the
value of
(e,
e
/
) does
not
depend
on
the
choice of
the
elements
e,
e
l
in
the
classes.
If
not,
then
G
cannot
be
isometrically
embedded
in
a half-cube graph.
(v)
Check
whether
~
is
a line graph. (This
can
be
done
in
O(m/)
time
if
~
has
m
l
edges (Lehot [1975]); note
that
m
l
< n
2
.)
If
not,
then
G
cannot
be
isometrically
embedded
in a half-cube graph.
Let HE
be
a
graph
whose line
graph
is~.
One
can
then
construct
an
isometric
embedding
of G into a half-cube
graph
in
the
following way.
We
label
each
node
x of G by a set X in a recursive
manner.
First,
label
Xo
by
Xo:=
0.
Let
e:=
(x,y)
be
an
edge
ofG
such
that
Xo
E
G(x,y)
and
suppose
that
x has
been
already
labeled by
X.
The
equivalence class e (in
(ET'
~))
is a
node
of
~
and,
thus,
corresponds to
an
edge p(e) in HE, p(e) being a two-element
set. We
label
the
node
y by
the
set
Y
:=
XUp(e).
Let
us check
that
this
labeling
x
f-+
X provides
an
isometric embedding of G into a half-cube
graph.
Observe
that
Ip(e)
n p(e') I =
(e,
e
/
)
for all edges
e,
e
l
E
ET.
In
particular,
p(e) n p(e
/
) = 0
if
and
only if
the
edges e
and
e
l
are
not
in relation by
B.
We first show
that
IXI
= 2dc(xo, x) for all x E
V.
For this, let (xo, Xl,
...
,xp
:=
x)
be
the
path
from
Xo
to x in
T,
where p
:=
dc
(xo, x). Let
ei
denote
the
edge
(Xi-l,
Xi) for i =
1,
...
,p. By
the
construction,
x
is
labeled by
the
set
X
:=
p(el) U
...
U p(e
p
).
Hence,
IXI
=
2p
= 2dc(xo, x), as
the
p(ei)'s are pairwise disjoint since
the
edges
el,
...
, e
p
are
not
in
relation
by
B.
We now show
that
IY
LY/I
= 2dc(y, yl) for all
y,
yl E
V.
We prove it
by
induction
on
the
quantity
s
:=
dc(xo,y) +
dC(XO,Y').
We
can
suppose
that
y
and
yl are
distinct
from
xo.
Let x
be
the
predecessor of
yon
the
path
from
Xo
to y in
T,
and
let
Xl
be
the
predecessor of yl on
the
path
from
Xo
to
yl
in
T.
Set e
:=
(x,y)
and
e
l
:=
(X/,yl). By
the
induction
assumption, we
have
IX
LXII
= 2dc(x, Xl),
IX
LY/I
= 2dc(x, yl),
IX
'
LYI
= 2dc(y,
Xl)
or, equivalently,
(a)
{
IX
n XII = dc(xo, x) + dc(xo,
Xl)
- dc(x, Xl),
IX
n Y/I = dc(xo, x) + dc(xo, yl) -
dc(x,
yl),
IX
'
n
YI
= dc(xo, y) + dc(xo,
Xl)
- dc(y, Xl).
21.4 More
on
R1-Graphs
325
By
the
construction, Y = X U p(e),
Y'
=
X'
U p(e') and, thus,
(b)
IY n Y'I =
IX
n Y'I +
IX'
n
YI-IX
n X'I +
Ip(e)
np(e')I·
On
the
other
hand,
IY
6Y'I
=
WI
+ IY'I -
21Y
n Y'I = 2dc(xo,y) + 2dc(xo, y') -
21Y
n Y'I·
Therefore, using (a), (b)
and
(21.2.13),
we
obtain
IY
6Y'I
= 2(dc(x,y') +
dc(y,x')
-
dc(x,x')
-Ip(e)
np(e')I) = 2dc(y,y'),
which concludes
the
proof.
I
21.4
More
about
iI-Graphs
We
group
here several
additional
facts
and
results
on
structural
properties
of
Rl-graphs.
We saw
in
Proposition
19.1.2
that
every
hypercube
embeddable
graph
is
R]-rigid. Hence,
we
have
the
following chain of implications:
G
is
an
isometric
subgraph
of a hypercube
===?
G
is
R
1
-rigid
===?
G is
an
isometric
subgraph
of a half-cube
graph
Several classes of graphs were shown to
be
R1-rigid
in
Deza
and
Laurent
[1994a];
among
them,
the
half-cube
graph
~H(n,
2)
for n
-#
3,4,
the
Johnson
graph
J(n,
d)
for d
-#
1,
the
Petersen
graph,
the
Shrikhande
graph,
the
dodeca-
hedron,
the
icosahedron, any weighted circuit.
The
method
of
proof
is
analogue
to
that
of
Proposition
19.1.2; namely, one shows
that
the
path
metric
ofthe
graph
in
question
lies
on
a simplex face
of
the
corresponding
cut
cone.
This
question
of
R1-rigidity is
further
investigated for
other
classes of graphs
in
Chepoi, Deza
and
Grishukhin
[1996], Deza
and
Grishukhin [1996c], Deza, Deza
and
Grishukhin
[1996].
An
interesting fact
is
that,
if
an
R
1
-graph
G
is
not
Rl-rigid,
then
this
is
essentially due to
the
fact
that
complete graphs
on
at
least four nodes are
not
Rl-rigid. Indeed,
it
follows from
Theorem
21.1.3
that
any R1-embedding of G
arises from
an
R1-embedding
of
its
extension
G.
As G is a
Cartesian
product
of
complete
graphs, cocktail-party graphs
and
half-cube graphs,
the
variety
of
R1-embeddings
of
G follows from
the
variety of R1-embeddings of its factors.
But
the
half-cube
graph
is
R1-rigid unless
it
coincides
with
K4
or
K
4x2
. Moreover,
any
R1-embedding
of
Knx2
arises from some R1-embedding
of
K
n
, since
the
path
metric
of
Knx2
can
be
constructed
from
the
path
metric
of
Kn
via
the
antipodal
operation
(recall Section 7.4). Therefore,
the
variety
of
R l-embeddings
of
G
and,
hence,
that
of
G, arises from
the
variety
of
R1-embeddings of
the
complete graph;
326
Chapter
21. £1-Graphs
we
will
study
in
detail
in
Chapter
23
the
variety
of
embeddings
of
the
complete
graph.
In
fact,
we
will see
in
Proposition
21.4.4 below
that,
if
an
£1-graph is
not
£1-rigid,
then
it
must
contain
a clique
on
at
least 4 nodes.
We have seen in
Chapter
19 several
structural
characterizations for isometric
sub
graphs
of
hypercubes. We present below
in
Theorem
21.4.2 a
structural
characterization
for isometric
sub
graphs
of
half-cube graphs.
This
result is
due
to
Chepoi, Deza
and
Grishukhin
[1996]
and
it
can
be
seen as
an
analogue
of
Theorem
19.2.5 for isometric
subgraphs
of
hypercubes.
On
the
other
hand,
no
result
of
this
type
is known for £1-graphs
in
general.
Thus,
the
following
problem
is open.
Problem
21.4.1.
Find
a
structural
characterization
for
£l-graphs (e.g.,
in
terms
of
forbidden
isometric
subspaces).
Such a
characterization
exists for some classes
of
graphs. For instance, we gave
in
Theorem
17.1.8 a
structural
characterization for
the
graphs
with
a universal
node
that
are
£1-graphs. We presented
this
result
in
Part
II
since
its
proof
relies
on
the
techniques
of
hypermetrics
and
Delaunay polytopes.
In
particular,
we
saw in Corollary 17.1.10
that,
if G is a
graph
on
n
2:
28
(resp. n
2:
37) nodes,
then
its
suspension "iJG is
an
£1-graph
if
and
only if "iJG is
hypermetric
(resp.
"iJG satisfies
the
5-gonal inequalities
and
is
of
negative type).
Let us now
turn
to
the
study
of
isometric
subgraphs
of
half-cube
graphs
(that
is, £1-graphs
with
scale 2). We need a definition. Given
an
integer k
2:
0,
let
Tk =
(X,
d
k
) denote
the
distance space
on
X
:=
{ao,
ai,
a2, a3, a4, b
o
, b
1
,
b
2
, b
3
, b
4
}
defined by
dk(ai,aj)
=
dk(bi,bj):=
1 for all
0:-::;
i <
j:-::;
4,
dk(ao, b
o
)
:=
k + 2,
dk(ai,
b
i
)
:=
k for i =
1,2,3,4,
dk(x,
y)
:=
k + 1 elsewhere, i.e.,
on
the
pairs
(ao, bi),
(b
o
, ai)
(i
=
1,2,3,4)
and
(ai,bj)
(i
-Ij
E
{1,2,3,4}).
In
the
case k =
0,
the
distance space
To
coincides (up
to
gate
O-extension)
with
the
graphic
metric
space
of
the
graph
K6
\ e, which
has
minimum
scale 4
(recall Section 7.4). As
d
k
=
do
+
k8({ao,aJ,a2,a3,a4}),
every Tk
is
hypercube
embeddable
with
scale
4.
In
fact, no Tk is hypercube
embeddable
with
scale 2
and
the
distance
spaces Tk
turn
out
to be
the
only
obstructions
for isometric
embeddability
in
half-cube graphs.
Theorem
21.4.2.
Let
G = (V,
E)
be
an
£1
-graph.
Then,
G is an
isometric
subgraph
of
some
half-cube graph
if
and
only
if
its
graphic
metric
space (V,
do)
does
not
contain
Tk
(k
2:
0) as
an
isometric
subspace.
Proof.
We
start
with
verifying
that
the
distance space Tk =
(X,
d
k
) (k
2:
0) is
not
hypercube
embeddable
with
scale
2.
This
is known for To. Suppose
that
Tk
21.4 More
on
iI-Graphs
327
admits
a hypercube embedding with scale 2
and
let k 2 1 be
the
smallest index
for which this is true. Consider a decomposition
2dk
= L 8(8)
6(S)
EC
k
where
Ck
is a collection of (not necessarily distinct)
cut
semimetrics on
X.
All
cut
semimetrics in
Ck
are dk-convex by Lemma 4.2.8. Note
that
the
only d
k
-
convex
cut
semimetric
8(8)
with
the
property
that
al E 8
and
b
i
~
8 is
8(8
0
)
:=
8({ao,al,a2,a3,a4}). Hence this
cut
semimetric occurs 2k times in
C".
Now,
2d" -
28(8
0
)
coincides
with
2d"_1
and
admits
a decomposition as a
sum
of
cut
semimetrics (as k 2 1).
This
shows
that
T"-I
too
admits
a scale 2 hypercube
embedding, yielding a contradiction.
Conversely, let G
=
(V,
E)
be
an
iI-graph
that
is
not
an
isometric
subgraph
of
a half-cube graph.
We
show
that
(V,
de)
contains some n as
an
isometric
subspace. By Corollary 21.1.5, G
is
an
isometric subgraph of a Cartesian
product
of
half-cube graphs
and
cocktail-party graphs.
This
product contains some Kmx2
with
m 2 5 (else, G would have scale 2). Say, G is
an
isometric subgraph of
the
graph
r
:=
Kmx2 x
H,
where m 2 5
and
H is a product
of
half-cube
and
cocktail-party graphs. Moreover,
we
can suppose
that
Kmx2 contains a subgraph
Km+1
\ e such
that,
for every node v of
Km+1
\
e,
the set
{v}
x
V(H)
contains
at
least one node of G (for, if not, one could have replaced Kmx2 by a smaller
cocktail-party
graph
or by a complete graph). Denote by K the set
of
nodes of
Km+l \ e forming a clique of size m. For every node v of Kmx2
we
call
the
set
{
v}
x V
(H)
a fiber in
the
product
r.
The
following can be easily observed:
(a)
Every union of fibers of
the
form:
UVEKo
{v}
x
V(H)
where Ko
~
K,
is
convex (with respect to the
path
metric of
r).
We
claim:
(b)
The
set V(G) n
(UvEK{V}
x
V(H))
contains a clique of size m
meeting each fiber
{v}
x V
(H)
(v
E
K)
in exactly one node.
For this, let
C
~
V(G)n(UvEK{V} x
V(H))
be a clique of
maximum
size (whose
elements all have
the
same H -coordinate). Suppose
that
C n ( { w} x V
(H))
= 0
for some w E
K.
Note
that
every node x E V(G) n
({
w} x
V(H))
is
at
the
same
distance from all nodes in
Cj
choose such x for which this distance is minimum.
For every node y
E C consider a shortest
path
in G from x to Yj this
path
is
entirely contained in
the
union of
the
two fibers containing x
and
Y (by (a)). Say,
this
path
is
of
the
form (x, fj,
...
, y).
The
node fj does not belong to
the
same
fiber as
x (by
the
minimality assumption on x). Thus, fj belongs to
the
fiber of
y. Now,
the
nodes x
and
fj (for y E
C)
form a clique of larger size
than
C.
This
shows
that
(b) holds.
Let
C
~
V(G) be a clique of size m meeting each fiber {v} x
V(H)
for v E
K.
Denote by
w,w'
the two nonadjacent nodes in Km+l \ e
with
wE
K,
w'
~
K.
Let s denote
the
node of C lying in the fiber
{w}
x V
(H).
By assumption,
the
fiber {w'} x V
(H)
also contains some node of G. Every such node is
at
the
same
328
Chapter
21. £1-Graphs
distance
k ? 1 from all nodes
in
C \ {s}; choose
such
a
node
t for which
the
distance
k is
minimum.
Thus,
da(s,
t)
=
k+1
and
da(t,
y)
= k for all y E C\
{s}.
Consider
a
shortest
path
in
G from t
to
y E C \
{s};
it
is
of
the
form (t,
y',
...
, y)
where
y'
belongs
to
the
same
fiber as y by
the
minimality
assumption
on
k.
Therefore,
the
nodes
t,
y'
(for y E C\
{s})
form a clique
and
da(y,
y')
= k
-1
for
y E C \
{s}.
As IC \
{s}
I ? 4
we
have found
within
{s,
t}
u
{y,
y'
lyE
C \
{s}}
an
isometric
subspace
of
(V,
da)
of
the
form
Tk-1.
This
concludes
the
proof. I
Corollary
21.4.3.
Let
G
be
an
£1-graph
and
suppose
that
G does
not
have
a
clique
of
cardinality
5.
Then,
G is
an
isometric
subgraph
of
a half-cube graph.
I
Combining
facts
about
£1-graphs
established
earlier
in
this
chapter
and
in
the
proof
of
Theorem
21.4.2, one
can
show
the
following refinement
of
the
result
from
Corollary
21.4.3.
Proposition
21.4.4.
Let
G
be
an
£1
-graph
that
does
not
contain
a clique
of
size
4,
then
G is £1-rigid (and, thus, is
an
isometric
subgraph
of
a half-cube graph).
Proof.
Suppose
that
G is
an
£1-graph which is
not
£l-rigid. Following
the
nota-
tion
from
Section
21.2, let
k k
G
~
G =
II
G
h
~
G =
II
Gh,
h=l
h=1
where
II~=1
Gh is
the
canonical
metric
representation
of
G
and
each factor G
h
is
a
complete
graph
Km
(m
? 2), a
cocktail-party
graph
Kmx2
(m
? 2),
or
a half-
cube
graph
iH(m,
2)
(m?
5).
By
Corollary 21.1.6, G is
not
£1-rigid. Therefore,
some
factor
G
h
is
not
£1-rigid
and,
thus,
is
Km
or
Kmx2
with
m ?
4.
This
implies
that
Gh
contains
a clique
of
size m ? 4 (see
the
proof
of
Claim
21.2.8). Now,
we
have
that
G is
an
isometric
subgraph
of
Gh x
H,
where H
:=
IIhl#h Ghl.
One
can
easily verify
that
the
statement
from
relation
(b)
in
the
proof
of
Theorem
21.4.2
remains
valid
in
the
present
situation.
Thus,
we
have found a clique
of
size m ? 4
in
G. I
In
particular,
we find
again
that
bipartite
£1-graphs
are
£l-rigid
but
we
also find,
for
instance,
that
tripartite
£1-graphs are £1-rigid.
Let
us now
return
to
general £1-graphs. A
question
of
interest
is
to
classify
£1-graphs
within
some
restricted
classes
of
graphs.
Such
a classification is known,
for
instance,
for
distance-regular
graphs
(recall Corollary 17.2.9).
This
question
is
studied
in
several
papers
for
other
classes
of
graphs,
that
we now
mention
briefly.
The
graphs
G for which
both
G
and
its
complement
G
are
£1-graphs
are
studied
in
Deza
and
Huang
[1996a]
and
£1-embeddability
of
graphs
related
with
some
designs is considered
in
Deza
and
Huang
[1996b].
21.4 More
on
1\
-Graphs
329
Recently, Deza
and
Grishukhin [1996c] classify
1\-graphs
within
polytopal
graphs
(that
is, I-skeleton
graphs
of
polytopes) of a variety of well-known poly-
topes, such as semiregular, regular-faced polytopes, zonotopes, Delaunay poly-
topes
of
dimension
S;
4,
and
several generalizations of prisms
and
antiprisms.
Deza, Deza
and
Grishukhin
[1996]
study
the
class of
polytopal
graphs arising
from fullerenes. Fullerenes
and
their
duals have
many
applications
in
chemistry,
computer
graphics, microbiology, architecture, etc. For instance,
they
occur as
carbon
molecules, spherical wavelets, virus capsids
and
geodesic domes.
They
can
be
defined in
the
following way. A fullerene
Fn
is
a simple 3-dimensional
polytope
with
n vertices
that
are
arranged
in
12
pentagons
and
~
-10
hexagons.
Such
polytopes
can
be
constructed
for every even n
2':
20, except n = 22. Among
other
results, Deza, Deza
and
Grishukhin
[1996]
show
that
any
hypermetric
fullerene
graph
is
1'1-embeddable
(and
thus
has scale
2,
by
Proposition
21.4.5
below)
and
give
an
infinite family of fullerenes F20a2
(a
integer) which are
1'1-
embeddable
with
an
icosahedral group of symmetries.
Related
work
is
made
by Deza
and
Stogrin
[1996]
who
study
1'1-embeddability
of
the
(infinite)
graphs
arising as skeletons
of
plane
tilings.
In
particular,
they
classify such 1'1-graphs for all semiregular
and
2-uniform
partitions
of
the
plane,
their
duals
and
regular
partitions
of
the
hyperbolic plane.
Several
authors
study
1'1-graphs
within
the
class of
planar
graphs.
First,
as
an
application
of
Corollary 21.4.3,
we
obtain:
Proposition
21.4.5.
Every
planar
1'1
-graph has scale 2 (that is, is
an
isometric
subgraph
of
a half-cube graph). I
Prisakar,
Soltan
and
Chepoi
[1990]
show
that
every
planar
graph
satisfying
the
following conditions (i)-(iv) is
an
1'rgraph.
Suppose a plane drawing
of
G
is
given;
then
the
conditions
on
G are: (i) every edge belongs to
at
most
two
faces; (ii) each interior face of G has
at
least five nodes; (iii) any two interior
faces intersect
in
at
most one edge; (iv) each interior
node
has
degree
2':
4.
Deza
and
Thma
[1996]
characterize 1'1-graphs
within
the
class
of
subdivided
wheels. A wheel
is
the
graph
obtained
from a circuit C
by
adding a new
node
adjacent
to
all nodes
on
C.
For instance,
K4
is
a wheel; Figure 31.3.12 (a) shows
a wheel where C
has
length
6.
Let us call subdivided wheel
the
graph
which is
obtained
from a wheel
by
replacing some edges
of
the
circuit C by
paths.
See
Figure
21.4.7; there,
the
dotted
lines indicate
paths
and
the
indication 'even'
or
'odd'
on
a face
means
that
the
circuit
bounding
it
has
an
even or
odd
length.
The
following result is proved in Deza
and
Thma
[1996].
Theorem
21.4.6.
A subdivided wheel is
an
1'1
-graph
if
and
only
if
it
is
not
one
of
the graphs shown
in
Figure 21.4.7 (a),(b),(c). Moreover,
it
is 1'1-rigid
if
and
only
if
it
is
distinct
from K
4
•
I
330
Chapter
21.
iI-Graphs
(a) (b) (c)
Figure
21.4.7:
Subdivided
wheels
that
are
not
iI-graphs
Chepoi,
Deza
and
Grishukhin
[1996]
further
study
iI-graphs
within
the
class
of
planar
graphs
satisfying
the
following two conditions: (i) each face of G is
bounded
by
an
isometric
cycle; (ii) two interior faces
meet
in
at
most
one edge
(assuming
a
plane
embedding
is given).
In
particular,
they
show
that
every
outerplanar
l
graph
is
an
iI-graph.
Another
example
of
graphs
satisfying (i), (ii)
consists
of
triangulations;
that
is,
planar
graphs
admitting
a
plane
embedding
in
which every
interior
face is
bounded
by a cycle
of
length
3.
Bandelt
and
Chepoi
[1996c] show
that
every
triangulation
with
the
property
that
all
interior
vertices
have degree
larger
than
5 is
an
iI-graph
and,
moreover, is
iI-rigid.
Moreover, by
Proposition
21.4.4, every
triangulation
which is
an
iI-graph
and
does
not
have
K4
as
an
induced
subgraph
is
iI-rigid.
1
An
outerplanar graph is a
planar
graph
admitting
a
plane
embedding
in
which
all
nodes
lie
on
one
face.
Part
IV
Hypercube
Embeddings
and
Designs
Introduction
In
Part
IV,
we
study
the question of embedding semimetrics isometrically in the
hypercube and, in particular, its link with the theory of designs.
Let
t
:2:
I be
an
integer. A very simple metric is the equidistant
metric
on n
points, denoted by
2tl
n
,
which takes
the
same value
2t
on each pair of points.
The
metric
2tl
n
is obviously hypercube embeddable. Indeed, a hypercube em-
bedding
of 2tJl
n
can
be
obtained by labeling
the
points by pairwise disjoint sets,
each
of
cardinality t. A basic result established in
Chapter
22
is
that,
for n
large enough (e.g., for n
:2:
t
2
+ t + 3), this embedding is essentially
the
unique
hypercube embedding of 2tJl
n
.
Moreover,
for
n
:2:
t
2
,
the existence of another
hypercube embedding of
2tJl
n
depends solely
on
the existence of a projective
plane of order
t.
In
Chapter
23,
we
further investigate how various hypercube
embeddings of
2t:D.n
arise from designs.
We
then
consider in
Chapter
24 some
other
classes of metrics for which
we
are able to characterize hypercube embed-
dability. Typically, these metrics have a small range
of
values so
that
one can still
take advantage of
the
knowledge available
for
their
equidistant submetrics. For
instance, one can characterize the hypercube embeddable metrics
with
values in
the
set {a,
2a},
or {a,
b,
a +
b}
(if two of a,
b,
a + b are odd), where a, b are given
integers. Moreover, this characterization yields a polynomial time algorithm for
checking hypercube embeddability of such metrics.
We
recall
that,
for general
semimetrics,
it
is an NP-hard problem to check whether a given semimetric is
hypercube embeddable. Several additional results related
to
the notion of hy-
percube embeddability are grouped in
Chapter
25,
namely, on
cut
lattices, quasi
h-points
and
Hilbert bases
of
cuts.
We
now recall some definitions
and
terminology
that
we
use in this
part.
Let
d be a distance on the set
Vn
:=
{I,
...
,
n}.
Then,
d is said to
be
hypercube
embeddable
if there exist vectors
Ui
E {o,I}m (for some m
:2:
1)
(i
E V
n
)
such
that
(a)
d(i,j)
=11
Ui
-
Uj
IiI
for all
i,j
E V
n
.
Let M denote the n x m
matrix
whose rows are
the
vectors
U
1,
...
,
Un;
!vI is the realization
matrix
of
the
embedding U
1,
•.•
,Un
of
d. Any
matrix
arising as the realization
matrix
of some hypercube embedding of d
is
called
an
h-realization
matrix
of d. Each vector
Ui
can
be
seen as
the
incidence
vector of a subset of
{I,
...
,m}.
Hence,
(b)