On the Upward Planarity of Mixed Plane Graphs

Frati, 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 23-25, 2013, Bordeaux, France , pp. 1-12 (Official URL: http://dx.doi.org/10.1007/978-3-319-03841-4_1).

Full text not available from this repository.

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 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 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.

Item Type:Conference Paper
Classifications:G Algorithms and Complexity > G.770 Planarity Testing
G Algorithms and Complexity > G.840 Planarization
ID Code:1356

Repository Staff Only: item control page

References

Bertolazzi, P., Di Battista, G., Didimo, W.: Quasi-upward planarity. Algorithmica 32(3), 474–506 (2002)

Bertolazzi, P., Di Battista, G., Liotta, G., Mannino, C.: Upward drawings of triconnected digraphs. Algorithmica 12(6), 476–497 (1994)

Bertolazzi, P., Di Battista, G., Mannino, C., Tamassia, R.: Optimal upward planarity testing of single-source digraphs. SIAM J. Comput. 27(1), 132–169 (1998)

Binucci, C., Didimo, W.: Upward planarity testing of embedded mixed graphs. In: Speckmann, B. (ed.) GD 2011. LNCS, vol. 7034, pp. 427–432. Springer, Heidelberg (2011)

Boesch, F., Tindell, R.: Robbins’s theorem for mixed multigraphs. Amer. Math. Monthly 87(9), 716–719 (1980)

Chung, F., Garey, M., Tarjan, R.: Strongly connected orientations of mixed multigraphs. Networks 15(4), 477–484 (1985)

Didimo, W., Giordano, F., Liotta, G.: Upward spirality and upward planarity testing. SIAM J. Discrete Math. 23(4), 1842–1899 (2009)

Eiglsperger, M., Kaufmann, M., Eppinger, F.: An approach for mixed upward planarization. J. Graph Algorithms Appl. 7(2), 203–220 (2003)

Garg, A., Tamassia, R.: On the computational complexity of upward and rectilinear planarity testing. SIAM J. Comput. 31(2), 601–625 (2001)

Gutwenger, C., Jünger, M., Klein, K., Kupke, J., Leipert, S., Mutzel, P.: A new approach for visualizing uml class diagrams. In: Diehl, S., Stasko, J., Spencer, S. (eds.) SOFTVIS, pp. 179–188. ACM (2003)

Hansen, P., Kuplinsky, J., de Werra, D.: Mixed graph colorings. Math. Meth. Oper. Res. 45(1), 145–160 (1997)

Healy, P., Lynch, K.: Two fixed-parameter tractable algorithms for testing upward planarity. Int. J. Found. Comput. Sci. 17(5), 1095–1114 (2006)

Hutton, M.D., Lubiw, A.: Upward planarity testing of single-source acyclic digraphs. SIAM J. Comput. 25(2), 291–311 (1996)

Pach, J., Tóth, G.: Monotone drawings of planar graphs. J. Graph Theory 46(1), 39–47 (2004)

Papakostas, A.: Upward planarity testing of outerplanar dags. In: Tamassia, R., Tollis, I.G. (eds.) GD 1994. LNCS, vol. 894, pp. 298–306. Springer, Heidelberg (1995)

Patrignani, M.: Finding bimodal and acyclic orientations of mixed planar graphs is NP-complete. Tech. Rep. RT-DIA-188-2011, Dept. Comp. Sci. Autom., Roma Tre Univ. (2011)

Sotskov, J.N., Tanaev, V.S.: Chromatic polynomial of a mixed graph. Vestsi Akademii Navuk BSSR. Ser. Fiz. Mat. Navuk 6, 20–23 (1976)