Information Technology Reference
In-Depth Information
v
j
1
v
v
v
2
v
3
v
i
1
v
i
2
v
i
v
i
v
4
v
1
v
1
v
1
v
j
2
v
s
v
i
+1
v
j
v
i
4
v
n
v
n
v
i
3
v
n
v
j
3
v
k
v
k
(a)
(b)
(c)
(d)
v
k
+1
v
k
+2
v
3
v
3
v
3
v
2
v
2
v
2
v
k
v
v
4
v
4
v
4
e
v
k
v
v
1
v
1
v
1
v
5
v
k
v
5
v
1
v
i
v
i
+1
e
v
j
v
v
n
v
n
v
k
(f)
v
k
(e)
(g)
(h)
Fig. 2.
Different configurations used in: (a) Lemma 2, (b) Lemma 3, (c, d) Lemma 4, (e) Lemma 5,
(f) Lemma 6, (g) Lemma 7, (h) Lemma 9
of the two components is as small as possible (thus, scissor-free) and that the vertices
around
i
, i.e.,
the component induced by
v
2
,...,v
i−
1
is the smaller one. Recall that by Lemma 4 a
scissor induces a
K
4
.
If
i
=3, i.e., if
C
are labeled such that this scissor is
{
v
1
,v
i
+1
}
,
{
v
i
,v
n
}
with
i
≤
n
−
{
v
1
,v
3
}
is a 2-hop, then
G
should contain either
{
v
2
,v
n
}
or
{
v
2
,v
4
}
,
as otherwise
v
1
and
v
3
is a separation pair; see Fig. 2d. Say w.l.o.g.
{
v
2
,v
n
}
. Then,
v
1
,
v
2
,
v
3
together with
v
n
induce a
K
4
with all vertices consecutive on circle
C
.
If
i>
3,let
{
v
k
,v
}
, 1
≤
k<
≤
i
be a long edgesuch that there is no long
k
<
edge
{
v
k
,v
}
=
{
v
k
,v
}
with
k
≤
≤
;seeFig. 2e. Then, no long edge
is crossing the edge
, as otherwise by Lemma 3 such a crossing would yield a
new scissor, contradicting the choice of
{
v
k
,v
}
{
v
1
,v
i
+1
}
and
{
v
i
,v
n
}
.Since
{
v
k
,v
}
is not
crossed by a long edge, it must be crossed by exactly one 2-hop, say
{
v
k−
1
,v
k
+1
}
.
Now,
−
k>
3 is not possible, since we could add the edge
{
v
k
+1
,v
}
, which is long.
Hence,
k
=3and by maximality of the outer-fan-planar drawing,
v
k
,v
k
+1
,v
k
+2
,v
induces a
K
4
with all vertices consecutive on
−
C
. Finally, if
G
contains no two crossing
long edges, let
{
v
k
,v
}
, 1
≤
k<
≤
n
be a long edgesuch that there is no long edge
k
<
≤
{
.Bythesameargumentation as above, we
obtain that
v
k
,v
k
+1
,v
k
+2
,v
induces a
K
4
with all vertices consecutive on
v
k
,v
}
=
{
v
k
,v
}
with
k
≤
C
.
Lemma 6.
Let
G
be a 3-connected outer-fan-planar graphwithatleast six vertices. If
G
contains a
K
4
withall vertices drawn consecutively on circle
,then this
K
4
contains
exactly one vertex of degree three andthis vertex is neither thefirstnor thelast of the
four vertices.
C
Proof.
Let the vertices around circle
be labeled so that
v
1
,
v
2
,
v
3
,
v
4
induce a
K
4
.
Since
v
1
and
v
4
is not a separation pair, there is an edge between
v
2
or
v
3
and a vertex,
say
v
k
,among
v
5
,...,v
n
. Hence, three outofthefour vertices
v
1
,
v
2
,
v
3
and
v
4
have
C
