Circular Drawings of Biconnected Graphs

Many applications which would benefit from an accompanying circular graph drawing include tools which manipulate telecommunication, computer, and social networks. Previous research has produced solutions which are visually complex with respect to the number of crossings. In this paper we focus our attention on developing better and more efficient circular drawing algorithms. In particular we present an O(m2) algorithm which lays out a biconnected graph onto a single embedding circle. Furthermore, we can guarantee that if a zero crossing circular embedding exists for an input graph, then our algorithm will find it. Also, the results of extensive experiments conducted over a set of 10,328 biconnected graphs and show our technique to perform significantly better than the current technology.