On the Upward Planarity of Mixed Plane Graphs
Vol. 18, no. 2, pp. 253-279, 2014. Regular paper.
Abstract A mixed plane graph is a plane graph whose edge set is partitioned into a set of directed edges and a set of undirected edges. An orientation of a mixed plane graph G is an assignment of directions to the undirected edges of G resulting in a directed plane graph G. In this paper, we study the computational complexity of testing whether a given mixed plane graph G is upward planar, i.e., whether it can be oriented to obtain a directed plane graph G such that G admits a planar drawing in which each edge is represented by a y-monotone curve. Our contribution is threefold. First, we show that upward planarity can be tested in cubic time for mixed outerplane graphs. Second, we show that the problem of testing the upward planarity of mixed plane graphs reduces in quadratic time to the problem of testing the upward planarity of mixed plane triangulations. Third, we design linear-time testing algorithms for two classes of mixed plane triangulations, namely mixed plane 3-trees and mixed plane triangulations in which the undirected edges induce a forest.
Submitted: December 2013.
Reviewed: February 2014.
Revised: March 2014.
Accepted: March 2014.
Final: April 2014.
Published: May 2014.
Communicated by Stephen K. Wismath and Alexander Wolff
article (PDF)