Bipartite Drawing with Minimum Edge Crossings of Binary Trees and 3-Cayley Trees. - Albacea, Eliezer A. (Philippine Computing Journal)
In this paper, we present a simple algorithm for bipartite drawing with minimum edge crossings of binary trees that has a running time of O(n). Together with the drawing, the algorithm also computes the bipartite crossing numbers of binary trees using the same amount of time. The algorithm for binary trees were used to produce a bipartite drawing and used to compute the bipartite crossing numbers of 3-Cayley trees. The algorithm produced also runs in O(n). For the case of trees, the computation of bipartite crossing numbers has been shown by Shahrokhi, et al. to be computable in O(n1.6) time. Hence, our result improves that of Shahrokhi et al. for the case of binary trees.