Information Technology Reference
In-Depth Information
We claim that j =5. If this is not the case, then similarly to the previous case v 4 and v j
would be a separation pair in G
−{
v 3 }
plus e , which is not possible due to Lemma 8.
It follows that G has to contain edge
{
v 1 ,v 5 }
:Since G is outer-fan-planar, in G there
cannot be an edge
{
v 4 ,v k }
for some k =6 ,...,n , since it would cross
{
v 2 ,v 5 }
which
is crossed by
{
v 3 ,v 1 }
.So,
{
v 1 ,v 5 }
crosses only edges incident to v 2 that are already
crossed by
could be added to G without violating
outer-fan-planarity; a clear contradiction. Since e and
{
v 3 ,v 1 }
and
{
v 4 ,v 1 }
. Hence,
{
v 1 ,v 5 }
{
v 2 ,v n }
both cross
{
v 1 ,v 5 }
it
follows that e =
{
v 4 ,v n }
.Butnow, v 5 and v n has to be a separation pair.
Remark 1. Let G be a graph with 6 vertices containing avertex v of degree three. Then
G is maximal outer-fan-planar if and only if G
is a K 5 missing one of the edges
that connects a neighbor of v to one of the other two vertices.
−{
v
}
Lemma 10. It can be tested in lineartime whether agraph is a complete 2-hop graph.
Moreover, if agraph is a complete 2-hop graph,then it has a constant number of outer-
fan-planarembeddings andthese can be constructed in lineartime.
Proof. Let G be an n -vertex graph. We test whether G is a complete 2-hop as follows.
If n
,then G is either K 4 or K 5 . Otherwise, check first whether all vertices
have degree four. If so, pick one vertex as v 1 , choose a neighbor as v 2 and a common
neighbor of v 1 and v 2 as v 3 (if no such common neighbor exists then G is not a complete
2-hop). Assume now that we have already fixed v 1 ,...,v i , 3 ≤ i<n . Test whether
there is a uniquevertex v
∈{
4 , 5
}
that is adjacent to v i and v i− 1 .Ifso,set
v i +1 = v . Otherwise reject. If we have fixed the order of all vertices check whether
there are only outer edges and 2-hops. Do this for any possible choices of v 2 and v 3 ,
i.e., for totally at most 6 choices.
V
\{
v 1 ,...,v i }
Remark 2. No degree 3 vertex can be added to an n -vertex complete 2-hop with n
5.
We are now ready to describe ouralgorithm. If the graph is not a complete 2-hop
graph, recursively try to remove a vertex of degree 3 which is contained in a K 4 .If
G is maximal outer-fan-planar, Lemmas 5 and 6 guarantee that such a vertex always
exists in the beginning. Remark 2 guarantees that also in subsequent steps there is a
long edge and, thus, Lemmas 8 and 9 guarantee that also in subsequent steps, we can
apply Lemma 5 as long as we have at least six vertices. Remark 1 guarantees that we
can also remove two more vertices of degree 3 ending with a triangle.
At this stage, we already know that if the graph is outer-fan-planar, it is indeed max-
imal outer-fan-planar. Either, we started with a complete 2-hop graph or we iteratively
removed vertices of degree three yielding atriangle. Note that in the latter case we must
have started with 3 n
6 edges. On the other hand, if we apply the above procedure to
an n -vertex 3-connected maximal outer-fan-planar graph, we get that the number of its
edges is exactly 2 n or 3 n
6.
Finally, we try to reinsert the vertices in the reversed order in which we have deleted
them. By Lemma 7, we can insert the vertex of degree three only between its neighbor,
that is, there are at most two possibilities where we could insert the vertex. Lemma 11
guarantees that in total, we have to check at most four possible drawingsfor G .
Lemma 11. When reinserting a sequence of degree 3 vertices starting fromatriangle,
at most thefirsttwo vertices havetwochoices where they could be inserted.
 
Search WWH ::




Custom Search