An Approach for Mixed Upward Planarization

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.