Geodesic
On the Upward Planarity of Mixed Plane Graphs
Journal of Graph Algorithms and Applications, Special Issue on Selected Papers from the Twenty-first International Symposium on Graph Drawing, GD 2013 , Tome 18 (2014) no. 2, pp. 253-279.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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.
DOI : 10.7155/jgaa.00322
Keywords: Graph Drawing, Upward Planarity Testing, Outerplanar Graphs, Mixed Graphs 
@article{JGAA_2014_18_2_a4,
     author = {Fabrizio Frati and Michael Kaufmann and J\'anos Pach and Csaba T\'oth and David Wood},
     title = {On the {Upward} {Planarity} of {Mixed} {Plane} {Graphs}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {253--279},
     publisher = {mathdoc},
     volume = {18},
     number = {2},
     year = {2014},
     doi = {10.7155/jgaa.00322},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00322/}
}
TY  - JOUR
AU  - Fabrizio Frati
AU  - Michael Kaufmann
AU  - János Pach
AU  - Csaba Tóth
AU  - David Wood
TI  - On the Upward Planarity of Mixed Plane Graphs
JO  - Journal of Graph Algorithms and Applications
PY  - 2014
SP  - 253
EP  - 279
VL  - 18
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00322/
DO  - 10.7155/jgaa.00322
LA  - en
ID  - JGAA_2014_18_2_a4
ER  - 
%0 Journal Article
%A Fabrizio Frati
%A Michael Kaufmann
%A János Pach
%A Csaba Tóth
%A David Wood
%T On the Upward Planarity of Mixed Plane Graphs
%J Journal of Graph Algorithms and Applications
%D 2014
%P 253-279
%V 18
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00322/
%R 10.7155/jgaa.00322
%G en
%F JGAA_2014_18_2_a4
Fabrizio Frati; Michael Kaufmann; János Pach; Csaba Tóth; David Wood. On the Upward Planarity of Mixed Plane Graphs. Journal of Graph Algorithms and Applications, 
							Special Issue on Selected Papers from the Twenty-first International Symposium on Graph Drawing, GD 2013
					, Tome 18 (2014) no. 2, pp. 253-279. doi : 10.7155/jgaa.00322. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00322/

Cité par Sources :