Information Technology Reference
In-Depth Information
The next lemma claims that odd cycles in the crossinggraph correspond to K 5 (the
proof uses similar arguments as the proof of Lemma 3.
Lemma 4. Let G be amaximally dense outer fan-planar graphandlet ʓ be an outer
fan-planardrawing of G .If CR( ʓ ) contains a cycle C of length 5 ,then thesubgraph
of G induced by theend-vertices of theedges corresponding to the vertices of C is K 5 .
We now prove the upper bound on the density of outer fan-planar graphs.
Lemma 5. Let G be amaximally dense outer fan-planar graphwith n vertices and m
edges. Then m
3 n
5 edges.
Proof. Let ʓ be an outer fan-planar drawing of G . We first claim that G is biconnected.
Suppose by contradiction that G is not biconnected, and let C 1 and C 2 be two distinct
biconnected components of G that share a cut-vertex v .Let u be the first vertex of G
encountered while moving from v clockwise on the external boundary of ʓ [ C 1 ],and
let w be the first vertex encountered while moving from v counterclockwise on the
external boundary of ʓ [ C 2 ]. One can suitably add edge ( u,w ) in ʓ , still getting an
outer fan-planar drawing, which contradicts the hypothesis that G is maximally dense.
Now, by Corollary 1, CR( ʓ ) can only have either even cycles or cycles of length 5.
Also, by Lemma 4, every cycle of length 5 in CR( ʓ ) corresponds to a subset of edges
whose end-vertices induce K 5 . We prove the statement by induction on the number h
of K 5 subgraphs in G .
Base Case. If h =0then, by Lemma 2, G has at most 3 n
6 edges.
InductiveCase. Suppose by induction that the claim is truefor h
0,andsuppose
G contains h +1subgraphs that are K 5 .Let G be one of these h +1subgraphs.
Let e =( u,v ) be an edgeontheouter face of ʓ [ G ] that is not on the outer face of ʓ .
Vertices u and v are a separation pair of G , otherwise there would be a vertex of G that is
not on the outer face of ʓ , which is impossible because ʓ is an outer fan-planar drawing
by hypothesis. Hence, we can split G into two biconnected subgraphs that share only
edge e , one of them containing G .Let G 1 ,G 2 ,...,G k ( k
5) be the biconnected
subgraphs of G distinct from G such that each G i shares exactly one edge with G .
Each G i ( i =1 , 2 ,...,k ) contains at most h subgraphs that are K 5 , and therefore it has
at most 3 n i
5 edges by induction, where n i denotes the number of vertices of G i .On
the other hand, G has 3 n
5=10edges, where n =5is the number of vertices
of G . It follows that m
3( n + n 1 +
···
+ n k )
5( k +1)
k ( k
5). Since
n + n 1 +
···
+ n k
n +2 k we have m
3( n +2 k )
5( k +1)
k =3 n
5.
The existence of an infinite family of outer fan-planar graphs that match the 3 n
5
bound is proved in the next lemma. Refer to Fig. 4 for an illustration.
Lemma 6. Fo r any integer h
1 there exists an outer fan-planar graph G with n =
3 h +2 vertices and m =3 n
5 edges.
Proof. Consider h graphs X 1 ,...,X h ,such that each X i is a K 5 graph, for i =
1 ,...,h . We now describe how to construct G . The idea is to “glue” X 1 ,...,X h to-
gether in such a way that they share single edges one to another. The proof is by induc-
tiononthenumber of merged graphs. Denote by G i the graph obtained after merging
 
Search WWH ::




Custom Search