Information Technology Reference
In-Depth Information
(and their incident edges) yields a graph such that each of the remaining components is
( k
1)-outerplanar. The outerplanarity of a plane graph G is the minimumvaluefor k
such that G is k -outerplanar.
2.1
Balanced Circle-Contact Representations
Theorem 1. Every n -vertex k -outerplanar graphwithmaximum degree Δ admits a
circle-contact representationwhere theratio of the maximum andthe minimum diame-
ter is at most f ( Δ ) k +log n ,forsome positivefunction f .In particular, when Δ is a fixed
constant and k is
O
(log n ) ,this ratio is polynomialin n .
In order to prove the theorem, we need the following result from [18].
Lemma 1 (Malitz-Papakostas). The vertices of every triangulated planar graph G
with the maximum degree Δ can be represented bynonoverlapping disksin theplane
so thattwodisks are tangenttoeach other if andonly if thecorresponding vertices are
adjacent, andforeach twodisksthat are tangenttoeach other, theratio of theradii of
thesmaller to thelarger disk is atleast ʱ ʔ− 2 with ʱ =
1
3+2 3
0 . 15 .
As a direct corollary, every maximal planar graph with maximumdegree Δ =
O
(1)
and diameter d =
O
(log n ) has a balanced circle-contact representation. Theorem 1
goes beyond this.
Proof of Theorem 1: To prove the claim, it is sufficient to show how to augment a given
k -outerplanar graph into a maximal planar graph with additional vertices so that its
maximumdegree remains
( k +log n ). By Lemma 1,
the resultinggraph admits a circular contact representation with the given bounds on
the ratio of radii. Removing the circles corresponding to the added vertices yields the
desired balanced representation of the original graph.
Let G be an n -vertex k -outerplanar graph with the maximumdegree Δ .Iftheouter-
planarity k of G is bounded by a constant, we can easily augment G to logarithmic di-
ameter, preserving its constant maximumdegree, as follows. Inside each non-triangular
face f of G , insert a balanced binary tree with
O
( Δ ) and its diameter becomes
O
leaves and
then triangulate the remaining non-triangular faces by inserting an outerpath (an out-
erplanar graph whose weak dual is a path) with constant maximumdegree; see Fig.2.
However, such an augmentation results in a maximal planar graph with the diameter
log
|
f
|
levels and
|
f
|
(a)
(b)
(c)
Fig. 2. (a) A face, (b) augmentation with a balanced binary tree, (c) triangulation with grey edges
 
Search WWH ::




Custom Search