Classification of Planar Upward Embedding

Auer, Christopher and Bachmaier, Christian and Brandenburg, Franz Josef and Gleißner, Andreas (2012) Classification of Planar Upward Embedding. In: Graph Drawing 19th International Symposium, GD 2011, September 21-23, 2011, Eindhoven, The Netherlands , pp. 415-426 (Official URL: http://dx.doi.org/10.1007/978-3-642-25878-7_39).

Full text not available from this repository.

Abstract

We consider planar upward drawings of directed graphs on arbitrary surfaces where the upward direction is defined by a vector field. This generalizes earlier approaches using surfaces with a fixed embedding in R3 and introduces new classes of planar upward drawable graphs, where some of them even allow cycles. Our approach leads to a classifi- cation of planar upward embeddability. In particular, we show the coincidence of the classes of planar upward drawable graphs on the sphere and on the standing cylinder. These classes coincide with the classes of planar upward drawable graphs with a homogeneous field on a cylinder and with a radial field in the plane. A cyclic field in the plane introduces the new class RUP of upward drawable graphs, which can be embedded on a rolling cylinder. We establish strict inclusions for planar upward drawability on the plane, the sphere, the rolling cylinder, and the torus, even for acyclic graphs. Finally, upward drawability remains NP-hard for the standing cylinder and the torus; for the cylinder this was left as an open problem by Limaye et al.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-25878-7_39
Classifications:G Algorithms and Complexity > G.490 Embeddings
P Styles > P.840 Upward
ID Code:1274

Repository Staff Only: item control page

References

Auer, C., Bachmaier, C., Brandenburg, F.J., Brunner, W., Gleißner, A.: Plane Drawings of Queue and Deque Graphs. In: Brandes, U., Cornelsen, S. (eds.) GD 2010. LNCS, vol. 6502, pp. 68–79. Springer, Heidelberg (2011)

Auer, C., Brandenburg, F.J., Bachmaier, C., Gleißner, A.: Classification of planar upward embedding. Technical Report MIP-1106, Fakultät für Informatik und Mathematik, Universität Passau (2011), http://www.fim.uni-passau.de/wissenschaftler/forschungsberichte/mip-1106.html

Bachmaier, C.: A radial adaption of the Sugiyama framework for visualizing hierarchical information. IEEE Trans. Vis. Comput. Graphics 13(3), 583–594 (2007)

Bachmaier, C., Brandenburg, F.J., Brunner, W., Fülöp, R.: Coordinate Assignment for Cyclic Level Graphs. In: Ngo, H.Q. (ed.) COCOON 2009. LNCS, vol. 5609, pp.66–75. Springer, Heidelberg (2009)

Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice-Hall (1999)

Dolati, A.: Digraph embedding on th . In: Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2008, pp. 11–14 (2008)

Dolati, A., Hashemi, S.M.: On the sphericity testing of single source digraphs. Discrete Math. 308(11), 2175–2181 (2008)

Dolati, A., Hashemi, S.M., Kosravani, M.: On the upward embedding on the torus. Rocky Mt. J. Math. 38(1), 107–121 (2008)

Foldes, S., Rival, I., Urrutia, J.: Light sources, obstructions and spherical orders. Discrete Math. 102(1), 13–23 (1992)

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

Hansen, K.A.: Constant width planar computation characterizes ACC0 . Theor. Comput. Sci. 39(1), 79–92 (2006)

Hashemi, S.M.: Digraph embedding. Discrete Math. 233(1-3), 321–328 (2001)

Hashemi, S.M., Rival, I., Kisielewicz, A.: The complexity of upward drawings on spheres. Order 14, 327–363 (1998)

Lee, J.M.: Introduction to Smooth Manifolds. Springer, Heidelberg (2002)

Limaye, N., Mahajan, M., Sarma, J.M.N.: Evaluating Monotone Circuits on Cylinders, Planes and Tori. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol. 3884, pp. 660–671. Springer, Heidelberg (2006)

Limaye, N., Mahajan, M., Sarma, J.M.N.: Upper bounds for monotone planar circuit value and variants. Comput. Complex 18(3), 377–412 (2009)

Marsen, J.E., Ratiu, T., Abraham, R.: Manifolds, Tensor Analysis, and Applications, 3rd edn. Springer, Heidelberg (2001)

Massey, W.S.: Algebraic Topology: An Introduction. Springer, Heidelberg (1967)

Mohar, B., Rosenstiel, P.: Tessellation and visibility representations of maps on the torus. Discrete Comput. Geom. 19, 249–263 (1998)

Mohar, B., Thomassen, C.: Graphs on Surfaces. John Hopkins University Press (2001)

Snyder, J.P.: Map projections – a working manual. US Geological Survey, 1395 (1987)

Sugiyama, K., Tagawa, S., Toda, M.: Methods for visual understanding of hierarchical system structures. IEEE Trans. Syst., Man, Cybern. 11(2), 109–125 (1981)

Thomassen, C.: Planar acyclic oriented graphs. Order 5(1), 349–361 (1989)

Wegener, I.: Complexity Theory - Exploring the Limits of Efficient Algorithms. Springer, Heidelberg (2005)