Information Technology Reference
In-Depth Information
2
Recognizing and Drawing Maximal Outer-Fan-Planar Graphs
In this section, we prove that given a graph
G
=(
V,E
) on
n
vertices, there is a poly-
nomial time algorithm to decide whether
G
is maximal outer-fan-planar and if so a
corresponding straight-line drawing can be computed in linear time. By Lemma 1, we
only have to check, whether
G
has a straight-line drawing on a circle
that is fan-planar.
Note that such a drawing is determined by the cyclic order of the vertices on
C
C
.Since
fan-planar graphs with
n
vertices have at most 5
n
10 edges [18], we may assume that
the number of edges is linear in the number of vertices. We first consider the case that
G
is 3-connected and then using SPQR-trees we show how the problem can be solved for
biconnected graphs. Observe that biconnectivity is a necessary condition for maximal
outer-fan-planarity. Indeed, if an outer-fan-planar drawing has a cut-vertex
c
, it is easy
to see that it is always possible to draw an edge connecting two neighbors of
c
while
preserving the outer-fan-planarity.
−
The 3-Connected Case.
Assume that a straight-line drawing of a 3-connected graph
G
with
n
vertices on a circle
C
is given. Let
v
1
,...,v
n
be the order of the vertices around
C
2
(mod
n
),anda
long edge
otherwise.
G
is a
complete 2-hop graph
,ifthereareallouter
edges and all 2-hops, butnolong edges. Two crossing long edges are a
scissor
if their
end-points form two consecutive pairs of vertices on
.Anedge
{
v
i
,v
j
}
is an
outer edge
,if
i
−
j
≡±
1(mod
n
),a
2-hop
,if
i
−
j
≡±
. We say that a triangle is an
outer
triangle
if two of its three edges are outer edges. We call an outer-fan-planar drawing
maximal
, if adding any edge to it yields a drawing that is not outer-fan-planar.
Ouralgorithm is based on the observation that if a graph is 3-connected maximal
outer-fan-planar, then it is a complete 2-hop graph, or we can repeatedly remove any
degree-3 vertex from any 4-clique until only a triangle is left. In a second step, we
reinsert the vertices maintaining outer-fan-planarity (if possible). It turns outthatwe
have to check a constant number of possible embeddings. In the following,weprove
some necessary properties. The first three lemmas are used in the proof of Lemma 5.
Their proofs are based on the 3-connectivity of the input graph; see Fig. 2a, 2b and 2c.
C
Lemma 2.
Let
G
be a 3-connected outer-fan-planar graph embedded onacircle
C
.If
twolong edges cross, then two of its end-points are consecutiveon
C
.
Lemma 3.
Let
G
be a 3-connected outer-fan-planar graph embedded onacircle
C
.If
there are twolong crossing edges, then there is a scissor, as well.
Lemma 4.
Let
G
be a 3-connected graph embedded onacircle
withamaximal
outer-fan-planardrawing.If
G
contains a scissor, then its end vertices induce a
K
4
.
C
Lemma 5.
Let
G
be a 3-connected graphwithamaximalouter-fan-planardrawing
and assumethatthedrawing contains atleast onelong edge. Then,
G
contains a
K
4
withall four vertices drawn consecutively on thecircle.
Proof.
First consider the case where the graph contains at least two crossing long edges
and, thus, by Lemma 3 a scissor. Removing the vertices of a scissor, splits
G
into two
connected components. Assume that we have chosen the scissor such that the smaller
