Information Technology Reference
In-Depth Information
Proof.
Let
H
beaouter-fan-planar graph and let three consecutive vertices
v
1
,v
2
,v
3
in-
duce a triangle. Assume, we want to insert a vertex
v
adjacent to
v
1
,v
2
,v
3
. By Lemma 6,
we have to insert
v
between
v
1
and
v
2
or between
v
2
and
v
3
. Note that the edges that
are incident to
v
2
and cross
arealsocrossedbyanedge
e
incident to
v
.So,if
there is an edgeincidentto
v
2
that was already crossed twice before inserting
v
,this
would uniquely determine whether
e
is incident to
v
1
or
v
3
and, thus, where to insert
v
.
We will now show that after the first insertion each relevant vertex is incident to an
edge that is crossed at least twice. When we insert the first vertex we create a
K
4
.From
the second vertex on, whenever we insert a new vertex, it is incident to an edgethatis
crossed at least twice. Also, after inserting the second degree 3 vertex, three among the
four vertices of the initial
K
4
are also incident to an edgethatiscrossedatleasttwice.
The forth vertex of the initial
K
4
is not the middle vertex of a triangle consisting of
three consecutive vertices. It can only become such a vertex if its incident inner edges
are crossed by a 2-hop. But then these inner edges are all crossed at least twice.
{
v
1
,v
3
}
Summarizing, we obtain the following theorem; in order to exploit this result in the
biconnected case, it is also tested whether a prescribed subset (possibly empty) of edges
can be drawn as outer edges.
Theorem 1.
Givena3-connected graph
G
withasubset
E
of its edgeset,itcan be
tested in lineartime whether
G
is maximalouter-fan-planar and has an outer-fan-
planardrawing such thattheedges in
E
are outer edges. Moreover if suchadrawing
exists, it can be constructed in lineartime.
Sketch of Proof.
Let
n
be the number of vertices. By Lemma 10, a complete 2-hop
graph has only a constant number of outer-fan-planar embeddings which can be com-
puted in linear time. Whenever we remove a vertex from the graph, we append it to
aqueue. Any vertex that was removed from the queue will never be appended again.
Hence, there are at most
n
iterations.
To check whether the degree three vertices can be reinserted back in the graph, we
only have to consider in total four different embeddings. Assume that we want to insert
avertex
v
into an outer triangle
v
1
,v
2
,v
3
.Thenwejust have to check whether
v
1
or
v
3
are incident to edges other than the edge
that cross an edgeincidentto
v
2
.This
can be done in constant time by checking only two pairs of edges.
{
v
1
,v
3
}
The Biconnected Case.
We now sketch how to test outer-fan-planar maximality on a
biconnected graph.
Lemma 12.
Let
v
1
,...,v
n
be theorderofthe vertices aroundthecircleinanouter-
fan-planardrawing of a 3-connected graph
G
.Ifwecan add avertex
v
between
v
1
and
v
n
withanedge
{
v,v
i
}
for some
i
=2
,...,n
−
1
,then
i
=2
or
i
=
n
−
1
.
Proof.
Otherwise, since
v
1
,v
i
cannot be a separation pair of
G
, there has to be an edge
from a
v
k
for some
k
=2
,...,i
−
1 that crosses
{
v,v
i
}
and hence an edge
{
v
k
,v
n
}
.
Since
v
n
,v
i
cannot be a separation pair of
G
, there has to be an edge
{
v
1
,v
}
for some
=
i
+1
,...,n
−
1.But now there are three independent edges crossing.
