On the Upward Planarity of Mixed Plane GraphsFrati, Fabrizio and Kaufmann, Michael and Pach, János and Tóth, Csaba D. and Wood, David R. (2013) On the Upward Planarity of Mixed Plane Graphs. In: 21st International Symposium, GD 2013 , September 2325, 2013 , pp. 112(Official URL: http://dx.doi.org/10.1007/9783319038414_1). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783319038414_1
AbstractA 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 TeX . 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 ydirection 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 lineartime testing algorithms for two classes of mixed plane triangulations, namely mixed plane 3trees and mixed plane triangulations in which the undirected edges induce a forest.
Actions (login required)
