On Bipartite Drawings and the Linear Arrangement Problem.
The bipartite crossing number problem is studied and a connection between this problem and the linear arrangement problem is established.  A lower bound and an upper bound for the optimal number of crossings are derived, where the main terms are the optimal arrangement values. Two polynomial time approximation algorithms for the bipartite crossing number are obtained. The performance guarantees are O(log n) and O(log2 n) times the optimal, respectively, for a large class of bipartite graphs on n vertices. No polynomial time approximation algorithm which could generate a provably good solution had been known. For a tree, a formula is derived that expresses the optimal number of crossings in terms of the optimal value of the linear arrangement and the degrees, resulting in an O(n1.6) time algorithm for computing the bipartite crossing number.The problem of computing a maximum weight biplanar subgraph of an acyclic graph is also studied and a linear time algorithm for solving it is derived. No polynomial time algorithm for this problem was known, and the unweighted version of the problem had been known to be NP-hard, even for planar bipartite graphs of degree at most 3.
Introduction
The planar crossing number problem calls for placing the vertices of a graph in the plane and drawing
the edges with Jordan curves, so that the number of edge crossings is minimized. This problem has
been extensively studied in graph theory [32], combinatorial geometry [22], and theory of VLSI [16].
In this paper we study the bipartite crossing number problem which is an important variation of the
planar crossing number. Throughout this paper E) denotes a connected bipartite graph,
are the two classes of independent vertices, and E is the edge set. We will assume that
# The research of the first author was supported by NSF grant CCR-9528228. The research of the second and fourth
authors was supported in part by the Alexander von Humboldt Foundation and by the Slovak Scientific Grant Agency
grant No. 95/5305/277. Research of the third author was supported in part by the Hungarian NSF contracts T 016 358
and T 019 367, and by the NSF contract DMS 970 1211. A preliminary version of this paper was published at WADS'97.
m. A bipartite drawing [13], or 2-layer drawing of G consists of placing
the vertices of V 0 and V 1 into distinct points on two parallel lines and then drawing each edge using
a straight line segment connecting the points representing the endvertices of the edge. Let bcr(G)
denote the bipartite crossing number of G, that is, bcr(G) is the minimum number of edge crossings
over all bipartite drawings of G.
Computing bcr(G) is NP-hard [11] 1 but can be solved in polynomial time for bipartite permutation
graphs [29]. The problem of obtaining nice multiple layer drawings of graphs (i.e. drawings with
small number of crossings), has been extensively studied by the graph drawing, VLSI, and CAD
communities [6, 7, 19, 30, 31]. In particular one of the most important aesthetic objectives in graph
drawing is reducing the number of crossings [23]. Very recently J-unger and Mutzel, [14] and Mutzel [20]
succeeded to employ integer programming methods in order to compute bcr(G) exactly, or to estimate
it, nevertheless, these methods do not guarantee polynomial time convergence. In fact, although a
O(log 4 n) times optimal polynomial time algorithm for approximating the planar crossing number
of degree bounded graphs has been known [17], no polynomial time approximation algorithm whose
performance is guaranteed has been previously known for approximating bcr(G). A nice result in this
area is a fast polynomial time algorithm of Eades and Wormald [7] which approximates the bipartite
crossing number by a factor of 3, when the positions of vertices in V 0 are fixed.
In this paper we explore an important relationship between the bipartite drawings and the linear
arrangement problem, which is another well-known problem in the theory of VLSI [4, 5, 15, 18, 28].
In particular, it is shown that for many graphs the order of magnitude for the optimal number of
crossings is bounded from below, and above, respectively, by minimum degree times the optimal
arrangement value, and by arboricity times the optimal arrangement value, where the arboricity of
G is the minimum number of acyclic graphs that G can be decomposed to. Hence for a large class
of graphs, it is possible to estimate bcr(G) in terms of the optimal arrangement value. Our general
method for constructing the upper bound is shown to provide for an optimal solution and an exact
formula, resulting to an O(n 1.6 computing bcr(G) when G is a tree. The presence
of arboricity in our upper bound allows us to relate some important topological properties such as
genus and page number, to bcr(G). In particular, our results easily imply that when G is "nearly
planar", i.e. it either has bounded genus, or bounded page number, then, the asymptotic values of
bcr(G), and the optimal arrangement are the same, provided that G is not too sparse.
A direct consequence of our results is that for many graphs, the bipratite drawings with small
sum of edge lenghts also have small bipartite crossings, and vis versa, and therefore, a suboptimal
solution to the bipartite crossing number problem can be extracted from a suboptimal solution to the
linear arrangement problem. Hence, we have derived here, the first polynomial time approximation
algorithms for bcr(G), which perform within a multiplicative factor of O(log n log log n) from the
optimal, for a large class of graphs. Moreover, we show here that the traditional divide and conquer
paradigm in which the divide phase approximately bisects the graph, also obtains a provably good
approximation, in polynomial time, for bcr(G) within a multiplicative factor of O(log 2 n) from the
optimal, for a variety of graphs. Crucial to verifying the performance guarantee of the divide and
conquer algorithm, is a lower bound of # G nb # (G)), derived here, for bcr(G), where b # (G), # < 1/2,
and # G are the size of the #-bisection and minimum degree of G, respectively. This significantly
improves Leighton's well-known lower bound of # b 23
(G)) [16] which was derived for the planar crossing
number of degree bounded graphs. The class of graphs for which the performance of our approximation
algorithms is guaranteed is very large, and in particular contains those regular graphs, degree bounded
graphs, and genus bounded graphs, which are not too sparse. Another notable aspect of relating bcr(G)
to the linear arrangement problem is that, both algorithms produce drawings with near optimal number
of crossings in which the coordinates of all vertices are integers, so that the total edge length is also
Technically speaking, the NP-hardness of the problem was proved for multigraphs, but it is widely assumed that it
is also NP-hard for simple graphs.
near optimal, with the same performance guarantee as for the number of crossings.
We also study biplanar graphs. A bipartite graph E) is called a biplanar, if it has a
bipartite drawing in which no two edges cross each other. Eades and Whitesides [8] have shown that
the problem of determining largest biplanar subgraph is NP-hard even when G is planar, and the
vertices in V 0 and V 1 have degrees at most 3 and 2, respectively. This raised the question of whether
or not computing a largest biplanar subgraph can be done in polynomial time when G is acyclic [20].
In this paper we present a linear time dynamic programming algorithm for the weighted version of
this problem in an acyclic graph. (The weighted version was first introduced by Mutzel [20].)
Section 2 contains our general results regarding the relation between bcr(G) and the linear arrangement
problem. Section 3 contains the applications, and includes several important observations, the
bisection based lower bound for bcr(G), and the approximation algorithms. Finally, Section 4 contains
our linear time algorithm for computing a largest biplanar subgraph of a tree.
Linear arrangement and bipartite crossings
We denote by d v the degree of v, and by d # v
denote the number vertices adjacent to v of degree 1. We denote by # G the minimum degree of G.
A bipartite drawing of G is obtained by: (i) placing the vertices of V 0 and V 1 into distinct points on
two horizontal lines y 0 , y 1 , respectively, (ii) drawing each edge with one straight line segment which
connects the points of y 0 and y 1 where the endvertices of the edge were placed. Hence, the order in
which the vertices are placed on y 0 and y 1 will determine the drawing.
Let DG be a bipartite drawing of G; when the context is clear, we omit the subscript G and write
D. For any e # E, let bcr D (e) denote the number of crossings of the edge e with other edges. Edges
sharing an endvertex do not count as crossing edges. Let bcr(D) denote the total number of crossings
in D, i.e.
The bipartite crossing number of G, denoted by bcr(G) is the minimum number of crossings of edges
over all bipartite drawings of G. Clearly,
We assume throughout this paper that the vertices of V 0 are placed on the line y 0 which is taken
to be the x-axis, and vertices of V 1 are placed on the line y 1 which is taken to be the line
For a vertex x-coordinate in the drawing D. We call the function
the coordinate function of D. Throughout this paper, we often omit the y coordinates.
Note that xD is not necessarily an injection, since for a # V 0 , and b # V 1 , we may have xD (a) = xD (b).
Given an arbitrary graph E), and a real function define the length of f , as
The linear arrangement problem is to find a bijection of minimum length.
This minimum value is denoted by -
L(G).
E) and D be a bipartite drawing of G. Define the length of D to be
In this section we derive a relation between the bipartite crossing number and the linear arrangement
problem.
Let D be a bipartite drawing of E) such that the vertices of V 0 are placed into the
points
(1, 0), (2, 0), ., (|V 0 |, 0).
For its neighbors satisfying xD the
median vertex of v,
We say that D has the
median property if the vertices of G have distinct x-coordinates and the x-coordinate of any vertex v
in V 1 is larger than, but arbitrarily close to, xD (med(v)), with the restriction that if a vertex of odd
degree and a vertex of even degree have the same median vertex, then the odd degree vertex has a
smaller x-coordinate. Note that if D has the median property, then xD is an injection.
When the bipartite drawing D does not have the median property, one can always convert it to a
drawing which has the property, by first placing the vertices of V 0 in the same order in which they
appear in D into the locations (1, 0), (2, 0), ., (|V 0 |, 0), and then placing each v # V 1 on a proper
position so that the median property holds. Such a construction is called the median construction and
was utilized by Eades and Wormald [7] to obtain the following remarkable result.
Theorem 2.1 [7] Let E), and D be a bipartite drawing of G. If D # is obtained using the
median construction from D, then
E) and D be a bipartite drawing of G. Consider an edge let u be a
vertex in V 0 # V 1 so that u /
# {a, b}. We say e covers u in D, if the line parallel to the y axis passing
through u has a point in common with the edge e. Thus for neither a nor b
are covered by e. However, a vertex c # V 1 with xD (c) = xD (a) is covered by e. Let ND (e) denote
the number of those vertices in V 1 which are covered by e in D. We will use the following two lemmas
later.
Lemma 2.1 For let D be a bipartite drawing of G. Recall that xD is the coordinate
function of D. Then, the following hold.
(i) Assume that xD (v) is an integer for all x # V 0 . Then, there is a bijection f
so that for any e = ab # E, it holds
(ii) Assume that D has the median property. Then for the bijection f # in (i), it holds
d a d # a
m.
Proof. To prove (i), we construct f # by moving all vertices in V to integer locations. Formally, let
be the order of vertices of V
that we may have xD (w i since xD may not be an
injection.) the proof of (i) easily follows. (In particular note that
the factor +1 appears in the upper bound, since the end point of e which belongs to V 1 may not have
an integer coordinate.) For (ii), let Assume x(a) > x(b), and let v be any
vertex in V 1 covered by e in D. Since D has the median property, at least #d v /2# of vertices adjacent
to v are separated from v in D by the straight line segment e. This means, in this case, that vertex
v generates at least # G /2# G - 1)/2 crossings on e. Moreover, vertex v, even if it has degree
1, generates one crossing on e, since v and med(v) are separated by the line segment e in D. Thus
G+1. Now assume xD (a) < xD (b), and let v be a vertex covered
by e. Then, v generates at least d v - # dv
crossings on e provided that v is not a vertex
of degree 1 which is adjacent only to a. Consequently, in this case, bcr D (e) # (ND (e) - d # a
We conclude that in either case, bcr D
a , and
consequently, using (i),
To finish the proof of (ii) take the sum over all
Lemma 2.2 Let E), and let D be a bipartite drawing of G which has the median
property, then
dv #2
with an arbitrary small # > 0.
Proof. To prove the claim, let uv # E with has the median property,
thus v is placed arbitrary close to u. So we may assume that |x D (v) - xD (u)| #
This way the total sum of the contributions of all edges which are incident to a vertex of degree one
in V 1 to L xD is at most |V 1 | #
# and the claim follows. 2
We now prove the main result of this section.
Theorem 2.2 Let
L(G).
Proof. Let D be a bipartite drawing of G. We will construct an appropriate bijection f
{1, 2, ., n}. Let D # be a drawing which is obtained by applying the median construction to D. Let
its neighbors with xD #
i be an integer, 1 # i #d v /2#, and let u be a vertex in V 0 so that xD #
Observe that u generates d u crossings on the edges u i v and u dv -i+1 v, if it is not adjacent to v.
Similarly, u generates d u - 1 crossings on the edges u i v and u dv-i+1 v, if it is adjacent to v. Thus
Note that D # has the median property, thus for
and hence (1) implies
Using (2) observe that, for
(bcr
Thus, using (3), when d v # 2 is even, we have
dv
(bcr
dv
Moreover, when d v # 2 is odd, we have,
dv
where the upper bound is obvious, and the lower bound holds since no vertex adjacent to v is between
and u
. Consequently, when d v # 2 is odd, we have,
dv
where the last line is obtained by observing that xD # (u
Combining this with (3), for odd d v , we obtaindv
dv
We note that since (5) is weaker than (4), it must also hold when d v is even, and conclude by summing
dv #2
dv #2
v .
Using Lemma 2.2, we get
v . (6)
Consider the bijection f # in Part (ii) of Lemma 2.1. Then
Observe that # G # 2 implies P v#V 0
Hence (6) implies
v . (7)
Observing that L f # -
, and
v , we obtain
which finishes the proof. 2
Next, we investigate the cases for which the error term P v#V d 2
v can be eliminated from Theorem
2.2.
Corollary 2.1 Let E) so that m # (1
# and # are positive constants. Then
Proof. To prove the result we will first show that for any bipartite drawing D of G it holds,
For now assume that (8) holds. It is easy to see that bcr(G) # m-
1+# m,
we conclude that 1)bcr(G). Combining this inequality with (8), we obtain
v , and thus
and the claim follows from Theorem 2.2.
To prove (8), let D be any bipartite drawing of G, and let v # V 0 so that d v - d # v # 2. Let
be the set of vertices of degree at least 2 which are adjacent to v, and assume with
no loss of generality that xD
be an integer, 1 # i # dv -d # v
and note that any vertex u generates at least one crossing on the edges
and u dv-i+1 v. Thus bcr(vu
2 #, and therefore
We conclude that by summing
Similarly we can show that 2bcr(D) # ( P v#V 0
hence the claim follows. 2
Remarks. The conditions of Corollary 2.1, involving # and # are not restrictive at all. For instance,
any bipartite graph of minimum degree at least 3, satisfies the conditions. We identify more additional
graphs which satisfy these conditions in Section 3.
2.2 An upper bound
We now derive an upper bound on bcr(G). We need the following obvious lemma.
Lemma 2.3 Let D be a bipartite drawing of
1 be two edges which cross in D. Assume that |x D (v) - xD (u)| # |x D (a) - xD (b)|, then either a or
b is covered by e in D. Moreover, if a is covered by e, then
if b is covered by e, then
|x D (a) - xD (v)| # |x D (v) - xD (u)|.Let VH and EH , denote the vertex set and the edge set of a subgraph H, of G. The arboricity of G,
denoted by aG , is maxH #
#, where the maximum is taken over all subgraphs H, with 2.
Note that # G /2 # aG #G , where #G denotes the maximum degree of G. A well-known theorem
of Nash-Williams [21] asserts that aG is the minimum number of edge disjoint acyclic subgraphs that
edges of G can be decomposed to.
Theorem 2.3 Let
L(G).
Proof. Consider a solution (not necessarily optimal) of the linear arrangement of G, realized by a
bijection n}. The mapping f # induces an ordering of vertices of V
y 0 . Lift up the vertices of V 1 into y 1 and draw the edges with respect to the new locations of these
vertices to obtain a bipartite drawing D. Note that
for this drawing D. Let I e to be the set all edges crossing e in
D so that for any ab # I e ,
Observe that if any edge e # /
# I e crosses e, then e # I e # . Hence, in this case the crossing of e and e #
contributes one to |I e # |. We conclude that
|I e |,
and will show that |I e | # aG (4|x D (u) - xD (v)| 1). For ebe the set of all those vertices y of V 0 so that |x D (y) - xD (v)| # |x D (u) - xD (v)|. Similarly, let
ebe the set of all those vertices y of V 1 so that |x D (y) - xD (u)| # |x D (u) - xD (v)|. Note that,
since the coordinates of all vertices are integers. Therefore, we
have
2. Let - observe that by Lemma
2.3, a # V e
1 . Consequently, |I e | # is the edge set of the induced subgraph
of G on the vertex set V e
by the definition of aG , and thus
I e # aG (4L xD +m).
To complete the proof we take f # to be the optimal solution to the linear arrangement problem, that
is,
2.3 Bipartite crossings in trees
We note that if aG is small, then, the gap between the upper bound and the lower bound in Theorems
2.2 and 2.3 is small, and hence, it is natural to investigate the case
In fact, in this case the method in the proof of Theorem 2.3 provides for an optimal bipartite drawing.
Theorem 2.4 Let T be a tree on the vertex set are the partite sets, and
be a bijection utilizing the optimal solution to the linear arrangement problem. Let
D # be a bipartite drawing constructed by the method of Theorem 2.3, that is, by lifting the vertices
in V 1 into the line
Proof. We prove the Theorem by induction on n. The result is true for 2. Let n # 3. Assume
that the Theorem is true for all l-vertex trees, l < n, and let T be a tree on n vertices. We first
show that the RHS of (11) is a lower bound on bcr(T ). We then show that bcr(D # ) equals to RHS of
(11). Consider an optimal bipartite drawing D of T . It is not di#cult to see that one of the leftmost
(rightmost) vertices is a leaf. Denote the left leaf by v 0 , the right leaf by v k , and let
be the path between v 0 and v k . Note that P will cross any edge in T which is not incident to v i ,
path P will generate at least
crossings, where c P counts exactly the number of edges in T (in D) which are not incident to any
vertex on P . Deleting the edges of P we get trees T i , on the vertex set V
rooted in
1. Consider the optimal bipartite drawings of T i , place them
consecutively such that T i does not cross T j , for i #= j. Then draw the path P without self crossings
such that v 0 (v k ) is placed to the left (right) of the drawing of T 1 (T k-1 ). Then clearly the number of
crossings in this new drawings is P k-1
so we conclude that
for otherwise D is not an optimal drawing. For any v # V , let d i
denote the degree of v in T i ; applying
the inductive hypothesis to T i ,
Now observe that for
Consequently,
where the last line is obtained by observing that j dv i -2
follows using (13) that
Now consider the optimal linear arrangements of the trees T i , for place them
consecutively in that order on a line, and the path P . Let g denote the bijection associated with this
arrangement, then L
1. Using this fact (15) implies
since L g # -
To finish the proof we will show that bcr(D # ) equals to the RHS of (11). Consider an optimal
linear arrangement f # of the tree T . It is not di#cult to see that, f #-1 (1) and f #-1 (n) are leaves,
[25, 4]. Let be the path between v
trees defined in the first part of the proof. Note that for the bijection g, described earlier, it holds
thus we conclude that,
and note that the above equation implies that P does not cross itself, in the arrangement associated
with f # . It follows that P does not cross itself in the bipartite drawing D # . Let f #
be the restriction
of f # to V i , and D # i be the subdrawing in D # which is associated with 1. Note that
However, it is easy to see that D #
is obtained from f #
by lifting the
vertex set V i
1 to the line hence we can apply the induction hypothesis to D # i ,
to obtain
Substituting c P its value from (12), and repeating the same steps used in deriving (15), we obtain
To complete the proof use (16) in (18) and obtain,
.Since the optimal linear arrangement of an n-vertex tree can be found in O(n 1.6 computing
D # can also be done in O(n 1.6 ) time.
Applications
It is instructive to provide examples of graphs G for which
L(G)). Consider any
bipartite G with # G # 3 and # regular bipartite graph with # G # 3.
Then, conditions of Corollary 2.1 are met, and thus by Theorem 2.3,
L(G)). Moreover,
consider any connected bipartite G of degree at most a constant k, with
is fixed. Note that, d v - d # v # 1 for any v # V , since G is connected and is not a star, and thus,
n. (Note that the star is excluded by the density condition
, to obtain n # 1
. Hence this graph satisfies the conditions of Corollary 2.1, moreover,
it is easy to see that aG # O(1), and we conclude using Theorem 2.3 that
L(G)).
3.1 Bipartite crossings, bisection, genus, and page number
The appearance of aG in the upper bound of Theorem 2.3 relates bcr(G) to other important topological
properties of G such as genus of G, denoted by g G [32], and page number of G [1], denoted by p G .
Observation 3.1 E), and assume that # G # 2 and m # (1 + #)n, for a fixed # > 0.
L(G)), provided that Consequently, under the given conditions for G,
if either
L(G)).
Proof. Assume that using Corollary 2.1 and Theorem 2.3, and observing that,
O(1), we conclude that
L(G)). (Note that, # G # 2, gives d # v
for all v # V . ) To finish the proof, observe that implies that
Next, we provide another application of our results, by deriving nontrivial upper bounds on the
bipartite crossing number.
Observation 3.2 Let E), with page number p G and genus g G . Then
L(G).
Proof. Since cr(G) # bcr(G) # 5a G
L(G), by Theorem 2.3, we need to bound aG in terms of g G and
G . Let H be a subgraph of G with the vertex set VH , |V H | # 2, and the edge set EH . Note that
which verifies the upper bound involving p G .
To finish the proof observe that
is a lower bound on the genus of H, or g H [32]. Thus,
H is at most (|V H | - 1) 2 /12 [32], it follows that for any subgraph H, p g G /12 # p g H /12 #
, and consequently aG # 2 #
Let 0 < # 1be a constant and denote by b # (G) size of the minimal #-bisection of G. That is,
denotes a cut which partitions V into A and -
A. Leighton [16] proved for any degree
bounded graph G, the inequality
(G)), where cr(G) is the planar crossing number of
G. Another very interesting consequence of Theorem 2.2 is providing a stronger version of Leighton's
result, for bcr(G).
Theorem 3.1
in particular when G is regular, it holds
Proof. The claim follows from the lower bound in Theorem 2.2 and the well-known observation that
(G). (See for instance [12].) 2
Remarks. After proving Theorem 3.1, we discovered that a weaker version of this Theorem for degree
bounded graphs can be obtained by a shorter proof which uses Menger's Theorem [27].
3.2 Approximation algorithms
Given a bipartite graph G, the bipartite arrangement problem is to find a bipartite drawing D of G
with smallest L xD , or smallest length, so that the x coordinate of any vertex is an integer. We denote
this minimum value by -
L(G). Note that coordinate function xD , for a bipartite drawing need not
to be an injection, since we may have xD (a) = xD (b), for a # V 0 , and b # V 1 . Thus, in general
L(G). Our approximation algorithms in this section provide a bipartite drawing in which all
vertices have integer coordinates, so that the number of crossings and at the same time the length of
the drawing is small. We need the following Lemma giving a relation between -
L(G).
Lemma 3.1 For any connected bipartite graph E) it holds
4 .
Proof. Let D be a bipartite drawing of G in which all x coordinates are integers. Let
and note that ND (e) # |x D (a) - xD (b)|, since any vertex in V 0 # V 1 has an integer x coordinate. Let
f # be the bijection in Part (i) in Lemma 2.1, then |f # (a) -f # (b)| # 2|x D (a) -xD (b)| + 1, and hence by
taking the sum over all edges, we obtain L f # 2L xD +m. To prove the lemma, we claim that there
are at least m-1edges so that xD (a) #= xD (b), and consequently L xD # m-1, which implies
the result. To prove our claim, note that there are at most nedges ab, so that xD (a) = xD (b), and
hence at least m- n
m-1edges ab, with xD (a) #= xD (b), since G is connected and therefore has at
least
Even et al. [9] in a breakthrough result came up with polynomial time O(log n log log n) times
optimal approximation algorithms for several NP-hard problems, including the linear arrangement
problem. Combining their result with ours, we obtain the following.
Theorem 3.2 Let E), and consider the drawing D (with integer coordinates) in Theorem
2.3 obtained form an approximate solution to the linear arrangement problem provided in [9]. Then
L(G)). Moreover, if G meets the conditions in Corollary 2.1, then
O(log n log log nbcr(G)), provided that #
Proof. Note that L
log n log log n) and thus the claim regarding L xD follows from
Lemma 3.1. To finish the proof note that, Theorem 2.3 gives
L(G)), and
the claim regarding bcr(D) is verified by the application of Corollary 2.1, since # divide and conquer paradigm has been very popular in solving VLSI layout problems both in
theory and also in practice. Indeed, the only known approximation algorithm for the planar crossing
number is a simple divide and conquer algorithm in which the divide phase consists of approximately
bisecting the graph [2]. This algorithm approximates cr(G)+n to within a factor of O(log 4 n) from the
optimal, when G is degree bounded [17]. A similar algorithm approximates -
L(G) to within a factor of
O(log 2 n) from the optimal. To verify the quality of the approximate solutions, in general, one needs
to show that the error term arising in the recurrence relations associated with the performance of
algorithms are small compared to the value of the optimal solution. A nice algorithmic consequence
of Theorem 3.1 is that the standard divide and conquer algorithm in which the divide phase consists
of approximately bisecting the graph gives a good approximation for bcr(G) in polynomial time. The
divide stage of our algorithm uses an approximation algorithm for bisecting a graph such as those in
[10, 17]. These algorithms have a performance guarantee of O(log n) from the optimal [10, 17]. It
should be noted that the lower bound of # b 23
(G)), although is su#cient to verify the the performance
of the divide and conquer approximation algorithm for the planar crossing number, can not be used to
show the quality of the approximation algorithm for bcr(G), since (as we will see) it does not bound
from above the error term in our recurrence relation. Thus our lower bound of # n#G b 1(G)) is crucial
to show the suboptimality of the solution.
Theorem 3.3 Let A be a polynomial time 1/3-2/3 bisecting algorithm to approximate the bisection
of a graph with a performance guarantee O(log n). Consider a divide and conquer algorithm which (a)
recursively bisects the graph G, using A, (b) obtains the two bipartite drawings, and then (c) inserts
the edges of the bisection between these two drawings. This divide and conquer algorithm generates,
in polynomial time, a bipartite drawing D with integer coordinates, so that L
L(G)).
Moreover, if G meets the conditions in Corollary 2.1, then
Proof. Assume that using A, we partition the graph G to 2 vertex disjoint subgraphs G 1 and G 2
recursively. Let - b(G) denote the number of those edges having one endpoint in the vertex set of G 1 ,
and the other in the vertex set of G 2 . Let DG 1
, and DG 2
be the bipartite drawings already obtained
by the algorithm for G 1 and G 2 , respectively. Let D denote the drawing obtained for G. To show the
claim regarding L xD , note that
Since, we use the approximation algorithm A for bisecting we have - nb 1(G)), hence
the error term in the recurrence relation is O(n log nb 1(G)). Moreover, 3 -
consequently using Lemma 3.1, we obtain, 12 -
1(G)n. Thus the error term is O(log n -
and consequently,
which implies L
L(G)). To verify the claim regarding bcr(D), note that
Now observing that m # aGn, - nb 1(G)), and nb 1(G) # 3 -
L(G), we obtain,
log n)
which implies
Note that by Corollary 2.1,
L(G)), and the claim follows. 2
Remarks. The method of Even et al. that we suggested to use in Theorem 3.2, although a theoretical
breakthrough, requires the usage of specific interior point linear programming methods which
may be computationally expensive or hard to code. Hence, the the divide and conquer approximation
algorithm, although in theory, weaker than the method of Theorem 3.2, it may be easier to implement.
Moreover, one may use very fast and simple heuristics developed by the VLSI and CAD communities
[24] for graph bisection in the divide stage. Although, these heuristics do not produce provably sub-optimal
solutions for bisecting a graph, they work well in practice, and are extremely fast. Therefore,
one may anticipate that certain implementations of the divide and conquer algorithm are very fast
and e#ective in practice.
Note that since aG can be computed in polynomial time, the class of graphs with aG # c# G is
recognizable in polynomial time, when c is a given constant. Hence, those graphs which meet the
required conditions in Theorems 3.2, and 3.3 can be recognized in polynomial time. Also, note that
many important graphs such those introduced in Section 3 meet the conditions, and hence for these
graphs the performance of both approximation algorithms is guaranteed.
Largest biplanar subgraphs in acyclic graphs
be a tree and w ij be a weight assigned to each edge ij . For any B # E T ,
define the weight of B, denoted by w(B), to be the sum of weights for all edges in B. In this section
we present a linear time algorithm to compute a biplanar subgraph of T of largest weight.
A tree on at least 2 vertices is called a caterpillar if it consists of a path to which some vertices of
degree 1 (leaves) are attached. We distinguish four categories of vertices in a caterpillar. First consider
caterpillars which are not stars. They have a unique path connecting two internal vertices to which
all leaves are attached to. We call this path the backbone of the caterpillar. The two endvertices of
the backbone are called endbone vertices, internal vertices of the backbone are called midbone vertices.
Leaves attached to endbones are called endleaves. Leaves attached to midbones are called midleaves.
For a star with at least 3 vertices, the middle vertex is considered as endbone, the backbone path
consists of this single endbone, and the leaves in the star are considered endleaves. If a star has two
vertices, then we treat these vertices as endbones.
be an unrooted tree and r # V T . Then, we view r as the root of T . Then any
vertex will have a unique parent which is the first vertex on the path towards the root.
For , the set of children of x, denoted by N x , are those vertices of T whose parent is x. For any
we denote by T x the component of T , containing x, which is obtained after removing
the parent of x from T . We define T r to be T .
We use the notation B x for a biplanar subgraph of T x , x # V T , and treat B x as an edge set. We say
that B x spans a vertex a, if there is an edge ab # B x . For x # V T , we define
Our goal is to determine W (T r ). To achieve this goal, we define 5 additional related optimization
problems as follows:
x is not spanned by B x } .
It is obvious that
and therefore solving all 5 problems for T x determines W (T x ). For any leaf v set w 1
Finally, for u # N x , x # V T define,
It is well-known and easy to show that a graph is biplanar i# it is a collection of vertex disjoint
caterpillars. This is equivalent to saying that a graph is biplanar i# it does not contain a double
claw which is a star on 3 vertices with all three edges subdivided. Therefore our problem is to find a
maximum weight forest of caterpillars in an edge-weighted acyclic graph. We will use these facts in
the next lemma, sometimes without explicitly referring to them.
Lemma 4.1
y #Nx\{y}
y #Nx\{y}
y #Nx\{y}
Proof Sketch. The basic idea for the recurrence relations is to describe how an optimal solution for
in the trees rooted in N x . Indeed, (21), (22), and (25) are obvious. For (23), note that
if x is an endbone in a maximum weight biplanar B x , then x is an endbone in a caterpillar C # B x .
Consider the case that C is not a star. Since, x is an endbone of C, it has at least two neighbors in
C, and all but one of its neighbors are leaves in C. Then exactly one neighbor y of x is an endbone
or an endleaf in C \ {x}. This justifies the presence of the first two terms in the inner curly bracket.
To justify the presence of the sum on y # , note that, in order to maximize the total weight of B x , we
must attach y # N x \ {y} to C as a leaf, only if f(y # must include
in B x , the maximum biplanar subgraph of T y # which has the total weight f(y # To justify
the term P y#Nx f(y), consider the case that C is a star. Then we must attach any y # N x to C as a
leaf only if we include in B x the maximum biplanar subgraph of T y .
For (24), note that, if x is a midbone in a maximum weight B x , then x is a midbone of C # B x , and
has 2 neighbors y 1 and y 2 in C. By deleting x from C, we obtain exactly two caterpillars C 1 and C 2
so that y i is either an endbone or an endleaf for C i , 2. Now follow an argument similar to (23)
to finish the proof of (24) 2
Theorem 4.1 For an edge-weighted acyclic graph largest weight biplanar subgraph
can be computed in O(|V T |) time.
Proof Sketch. With no loss of generality assume that T is connected, otherwise we apply our
arguments to the components of T . We select a root r for T , and then perform a post order traversal
and show that we can compute w i (T x quantities
are already known for the children of x. This is obvious for (20) and (25). For (21) and (22) the
expressions in curly braces are easy to evaluate in linear time, if a maximizing y is known. So the
issue is to find a maximizing y in linear time. It is easy to see that for (21) we look for y # N x
which maximizes w xy we look for y # N x which maximizes
all these can be computed in O(|N x |) time.
For (23), it su#ces to show that a y # N x can be found in O(|N x |) time which maximizes
To do so find
note that
Thus, to maximize w 4 (T x ), we should find y 1 , y 2 # N x , y 1 #= y 2 which give the largest two values for
It is easy to maintain for every x not just the values w i (T x also the edge-set of B x which
realizes this value, therefore, we can store the edge set of a largest biplanar subgraph as well. 2

Acknowledgment

. The research of the second and fourth author was done while they were visiting
Department of Mathematics and Informatics of University in Passau. They thank Prof. F.-J. Brandenburg
for perfect work conditions and hospitality. A preliminary version of this paper was published
at WADS'97 [26]. That version contained slight inaccuracies like missing error terms which are fixed
in the current version.



--R

The book thickness of a graph
A framework for solving VLSI layout problems
The assignment heuristics for crossing reduction
On optimal linear arrangements of trees
Graph layout problems
Algorithms for drawing graphs: an annotated bibliography
Edge crossings in drawings of bipartite graphs
Drawing graphs in 2 layers

Fast Approximate Graph Partition Algorithms
Crossing number is NP-complete
Approximate algorithms for geometric embeddings in the plane with applications to parallel processing problems
A new crossing number for bipartite graphs
Exact and heuristic algorithm for 2-layer straight line crossing number
Optimal linear labelings and eigenvalues of graphs
Complexity issues in VLSI

Combinatorial algorithms for integrated circuit layouts
On the bipartite crossing number
An alternative method to crossing minimization on hierarchical graphs
Edge disjoint spanning trees of finite graphs
Combinatorial Geometry
Which aesthetic has the greatest e
An introduction to VLSI physical design
The optimal numbering of the vertices of a tree


A minimum linear arrangement algorithm for undirected trees
Discrete Applied Mathematics 19
Methods for visual understanding of hierarchical systems structures
Crossing theory and hierarchy mapping
Topological graph theory
--TR

--CTR
Robert A. Hochberg , Matthias F. Stallmann, Optimal one-page tree embeddings in linear time, Information Processing Letters, v.87 n.2, p.59-66, 31 July
Journal of Discrete Mathematics Staff, Research problems, Discrete Mathematics, v.257 n.2-3, p.599-624, 28 November
Hillclimbing Algorithm for the Optimal Linear Arrangement Problem, Fundamenta Informaticae, v.68 n.4, p.333-356, December 2005
Matthias Stallmann , Franc Brglez , Debabrata Ghosh, Heuristics, Experimental Subjects, and Treatment Evaluation in Bigraph Crossing Minimization, Journal of Experimental Algorithmics (JEA), 6, p.8-es, 2001
Dimitrios M. Thilikos , Maria Serna , Hans L. Bodlaender, Cutwidth II: algorithms for partial w-trees of bounded degree, Journal of Algorithms, v.56 n.1, p.25-49, July 2005
Josep Daz , Jordi Petit , Maria Serna, A survey of graph layout problems, ACM Computing Surveys (CSUR), v.34 n.3, p.313-356, September 2002
approximation algorithms;biplanar graph;bipartite drawing;linear arrangement;bipartite crossing number