Information Technology Reference
In-Depth Information
Theorem 2. Givenabiconnected 4-planar graph G , wecan compute in O ( n ) time an
octilineardrawing of G withat most 1 bend per edgeonan O ( n 2 )
×
O ( n ) integer grid.
Proof. The SPQR-tree
can be computed in O ( n )-time and its size is linear to the
size of G [8]. The pertinent degrees of the poles at every node can be pre-computed by
a bottom-up traversal of
T
.Drawing a P-node requires constant time; S- and R-nodes
require time linear to the size of the skeleton. However, the sum over all skeleton edges
is linear, as every virtual edge corresponds to a tree node.
T
The Simply Connected Case. Themainideaofouralgorithm is to root the BC-tree at
some arbitrary B-node. With exception of the root, every B-node contains a designated
cut vertex that links it to the parent. Similar to the biconnected case, we define an
invariant for the drawing of a subtree. The cut vertex that links the subtree to the parent
is located in the upper left corner of the bounding box. Due to lack of space, we only
state the main result; its proof is given in [1].
Theorem 3. Givenaconnected 4-planar graph G , wecan compute in O ( n ) time an
octilineardrawing of G withat most 1 bend per edgeonan O ( n 2 )
×
O ( n ) integer grid.
3
Octilinear Drawings of 5-Planar Graphs
In this section, we focus on planar octilinear drawingsof5-planargraphs. As in Sec-
tion 2, we first consider the case of triconnected 5-planar graphs and then we extend
our approach first to biconnected and then to the simply connected graphs.
The Triconnected Case. Let G =( V,E ) be a triconnected 5-planar graph and ʠ =
{
be a canonical order of G . We place partitions P 0 and P 1 similar to the
4-planar case. Assume that we have already constructed a drawing for G k− 1 which is
stretchable in the following sense: If e ∈ E ( G k− 1 ) is an edge incident to the outer face,
then there is a cut which crosses e and can be utilized to horizontally stretch the drawing
of G k− 1 . In other words, one can define a cutthrougheveryedge incident to the outer
face of G k− 1 ( stretchability-invariant ).
If P k =
P 0 ,...,P m }
is a chain, it is placed exactly as in the case of 4-planar graphs,
but with different port assignment. Among the northern available ports of vertex v i
( v j , resp.), edge ( v i ,v i ) (( v j ,v j ),resp.)uses the eastern-most unoccupied port of v i
(western-most unoccupied port of v j ,resp.);seeFig.4a. If P k does not fit into the gap
between v i and v j in G k− 1 , then we horizontally stretch G k− 1 between v i and v j to
ensure that the horizontal distance between v i and v j is at least
{
v i ,...,v j }
+1. This can
be done due to the stretchability-invariant, as both v i and v j are on the outer face of
G k− 1 . Potential crossingsintroduced by edges of P k containing diagonal segments can
be eliminated by employing similar cuts to the ones presented in the 4-planar case. So,
we may assume that G k is plane. Also, G k complies with the stretchability-invariant, as
one can define a cut that crosses any of the newly inserted edges of P k andthenfollows
one of the cuts of G k− 1 that crosses an edge between v i and v j .
|
P k |
 
Search WWH ::




Custom Search