Information Technology Reference
In-Depth Information
degree at least four; see Fig.2f.If
v
3
had a neighbor in
v
5
,...,v
n
, then this could only
be
v
k
,asotherwise
would be crossed by two independent edges. Since
G
has
at least 6 vertices, we assume w.l.o.g.that
k>
5.Since
v
4
and
v
k
is not a separation
pair, there has to be an edge
{
v
1
,v
4
}
{
v
,v
m
}
for some 4
<<k
and a
j/
∈{
4
,...,k
}
.But
such an edgewould not be possible in an outer-fan-planar drawing.
Lemma 7.
Let
G
be a 3-connected outer-fan-planar graphwithatleast six vertices. If
G
contains a
K
4
withavertex of degree 3, then this
K
4
hastobedrawn consecutively
on circle
C
in any outer-fan-planardrawing of
G
.
Proof.
Observe that any outer-fan-planar drawing of a
K
4
contains exactly one pair of
crossing edges. If two 2-hops cross, then all vertices of the
K
4
are consecutive. If the
K
4
contains two crossing long edges, then each of the vertices of the
K
4
is incident to
an outer edge not contained in the
K
4
;thus, has degreeatleastfour. If a long edgeanda
2-hop cross, assume that the vertices around
C
are labeled such that
v
1
,v
2
,v
3
,v
k
induce
a
K
4
for some 5
k<n
;seeFig.2g.Since
v
1
,
v
3
and
v
k
are incident to an outer edge
not contained in the
K
4
,theyhavedegreeatleastfour. We claim that
v
2
has degree at
least four. Since
v
3
and
v
k
is not a separation pair, there is an edge between a vertex
among
v
4
,...,v
k−
1
and
v
2
or
v
1
andanedge between a vertex among
v
k
+1
,...,v
n
and
v
2
or
v
3
. Choosing
v
1
and
v
3
in the first and second case respectively, yields two
independent edges crossing
≤
{v
2
,v
k
}
.So,
v
2
is connected to a vertex outside
K
4
.
Lemma 8.
Let
G
be a 3-connected graphwith
n
≥
5
vertices andlet
v
∈
V
[
G
]
be a
vertex of degree three thatiscontained ina
K
4
.Then,
G
−{
v
}
is 3-connected.
Proof.
Let
a
,
b
,
c
and
d
be four arbitrary vertices of
G
−{
v
}
.Since
G
was 3-connected,
there was a path
P
from
a
to
b
in
G
.Assume that
P
contains
v
.Since
v
is
only connected to vertices that are connected to each other, there is also another path
from
a
to
b
in
G
−{
c, d
}
−{
c, d
}
not containing
v
. Hence,
a
and
b
cannot be a separation pair
in
G
−{
v
}
.Since
a
and
b
were arbitrarily selected,
G
−{
v
}
is 3-connected.
Lemma 9.
Let
G
be a 3-connected graphwith
n>
6
vertices, let
v
1
,
v
2
,
v
3
and
v
4
be
four vertices thatinduce a
K
4
,such thatthedegree of
v
3
is three. Then,
G
−{
v
3
}
has
amaximalouter-fan-planardrawing if
G
has amaximalouter-fan-planardrawing.
Proof.
Consider a maximal outer-fan-planar drawing of
G
on a circle
C
and let
v
1
,
v
2
,
v
3
,
v
4
,...,v
n
be the order of the vertices on
(recall Lemma 7). Assume to the
contrary that after removing
v
3
,wecouldaddanedge
e
to the drawing;seeFig.2h.By
Lemma 6,
C
{
v
3
,v
1
}
is the only edgeincidentto
v
3
that crosses some edges of
G
−{
v
3
}
.
Hence, there must be an edge
e
that is crossed by
e
and
{
v
3
,v
1
}
.Since
{
v
3
,v
1
}
crosses
, it follows that
e
has to be incident to
only edges incident to
v
2
that also cross
{
v
1
,v
4
}
v
2
.Further, since
G
plus
e
is outer-fan-planar it follows that
e
is incident to
v
1
or
v
4
. Moreover, since
G
plus
e
is not outer-fan-planar it follows that
e
is incident to
v
4
.
Let
i
be maximal so that there is an edge
−{
v
3
}
{
v
2
,v
i
}
.If
i
=
n
,then
v
1
and
v
i
is a
separation pair: Any edge connecting
{
v
i
+1
,...,v
n−
1
}
to
{
v
2
,v
3
,...,v
i−
1
}
and not
being incident to
v
2
crosses
can only be incident
to
v
1
, a contradiction. Now, let
j>
4 be minimumsuch that there is an edge
{
v
2
,v
i
}
.Butedges crossing
{
v
2
,v
i
}
{
v
2
,v
j
}
.
