On the Upward Planarity of Mixed Plane Graphs

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

$\vec 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 admits an orientation resulting in a directed plane graph

G

such that

G

admits a planar drawing in which each edge is represented by a curve monotonically increasing in the

y

-direction according to its orientation.

Our contribution is threefold. First, we show that the upward planarity testing problem is solvable 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 exhibit 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

.