Special Issue on Selected Papers from the Seventh International Workshop on Algorithms and Data Structures, WADS 2001
An Approach for Mixed Upward Planarization
Markus Eiglsperger, Michael Kaufmann, and Frank Eppinger
Vol. 7, no. 2, pp. 203-220, 2003. Regular paper.
Abstract In this paper, we consider the problem of finding a mixed upward planarization of a mixed graph, i.e., a graph with directed and undirected edges. The problem is a generalization of the planarization problem for undirected graphs and is motivated by several applications in graph drawing. We present a heuristic approach for this problem which provides good quality and reasonable running time in practice, even for large graphs. This planarization method combined with a graph drawing algorithm for upward planar graphs can be seen as a real alternative to the well known Sugiyama algorithm.
Submitted: October 2001.
Revised: December 2002.
Communicated by Giuseppe Liotta and Ioannis G. Tollis
article (PDF)