Strip Planarity Testing

Angelini, Patrizio and Da Lozzo, Giordano and Di Battista, Giuseppe and Frati, Fabrizio (2013) Strip Planarity Testing. In: 21st International Symposium, GD 2013, September 23-25, 2013, Bordeaux, France , pp. 37-48 (Official URL: http://dx.doi.org/10.1007/978-3-319-03841-4_4).

Full text not available from this repository.

Abstract

In this paper we introduce and study the strip planarity testing problem, which takes as an input a planar graph G(V,E) and a function γ:V → {1,2,…,k} and asks whether a planar drawing of G exists such that each edge is monotone in the y-direction and, for any u,v ∈ V with γ(u) < γ(v), it holds y(u) < y(v). The problem has strong relationships with some of the most deeply studied variants of the planarity testing problem, such as clustered planarity, upward planarity, and level planarity. We show that the problem is polynomial-time solvable if G has a fixed planar embedding.

Item Type:Conference Paper
Classifications:G Algorithms and Complexity > G.770 Planarity Testing
P Styles > P.180 Cluster
P Styles > P.480 Layered
P Styles > P.840 Upward
ID Code:1359

Repository Staff Only: item control page

References

Angelini, P., Di Battista, G., Frati, F., Jelínek, V., Kratochvíl, J., Patrignani, M., Rutter, I.: Testing planarity of partially embedded graphs. In: Charikar, M. (ed.) SODA 2010, pp. 202–221. ACM (2010)

Angelini, P., Frati, F., Kaufmann, M.: Straight-line rectangular drawings of clustered graphs. Discrete & Computational Geometry 45(1), 88–140 (2011)

Angelini, P., Da Lozzo, G., Di Battista, G., Frati, F.: Strip planarity testing of embedded planar graphs. ArXiv e-prints 1309.0683 (September 2013)

Bachmaier, C., Brandenburg, F.J., Forster, M.: Radial level planarity testing and embedding in linear time. JGAA 9(1), 53–97 (2005)

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

Biedl, T.C., Kaufmann, M., Mutzel, P.: Drawing planar partitions II: HH-drawings. In: Hromkovič, J., Sýkora, O. (eds.) WG 1998. LNCS, vol. 1517, pp. 124–136. Springer, Heidelberg (1998)

Booth, K.S., Lueker, G.S.: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comput. Syst. Sci. 13(3), 335–379 (1976)

Cortese, P.F., Di Battista, G., Patrignani, M., Pizzonia, M.: Clustering cycles into cycles of clusters. JGAA 9(3), 391–413 (2005)

Cortese, P.F., Di Battista, G., Patrignani, M., Pizzonia, M.: On embedding a cycle in a plane graph. Discrete Mathematics 309(7), 1856–1869 (2009)

Di Battista, G., Frati, F.: Efficient c-planarity testing for embedded flat clustered graphs with small faces. JGAA 13(3), 349–378 (2009)

Di Battista, G., Tamassia, R.: Algorithms for plane representations of acyclic digraphs. Theor. Comput. Sci. 61, 175–198 (1988)

Eades, P., Feng, Q., Lin, X., Nagamochi, H.: Straight-line drawing algorithms for hierarchical graphs and clustered graphs. Algorithmica 44(1), 1–32 (2006)

Estrella-Balderrama, A., Fowler, J.J., Kobourov, S.G.: On the characterization of level planar trees by minimal patterns. In: Eppstein, D., Gansner, E.R. (eds.) GD 2009. LNCS, vol. 5849, pp. 69–80. Springer, Heidelberg (2010)

Forster, M., Bachmaier, C.: Clustered level planarity. In: Van Emde Boas, P., Pokorný, J., Bieliková, M., Štuller, J. (eds.) SOFSEM 2004. LNCS, vol. 2932, pp. 218–228. Springer, Heidelberg (2004)

Fowler, J.J., Kobourov, S.G.: Minimum level nonplanar patterns for trees. In: Hong, S.-H., Nishizeki, T., Quan, W. (eds.) GD 2007. LNCS, vol. 4875, pp. 69–75. Springer, Heidelberg (2008)

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

Gutwenger, C., Klein, K., Mutzel, P.: Planarity testing and optimal edge insertion with embedding constraints. JGAA 12(1), 73–95 (2008)

Healy, P., Kuusik, A., Leipert, S.: A characterization of level planar graphs. Discrete Mathematics 280(1-3), 51–63 (2004)

Hong, S.H., Nagamochi, H.: Two-page book embedding and clustered graph planarity. Tech. Report 2009-004, Dept. of Applied Mathematics & Physics, Kyoto University (2009)

Hopcroft, J.E., Tarjan, R.E.: Efficient planarity testing. J. ACM 21(4), 549–568 (1974)

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

Jelínek, V., Kratochvíl, J., Rutter, I.: A kuratowski-type theorem for planarity of partially embedded graphs. Comput. Geom. Theory Appl. 46(4), 466–492 (2013)

Jelínková, E., Kára, J., Kratochvíl, J., Pergel, M., Suchý, O., Vyskocil, T.: Clustered planarity: Small clusters in cycles and Eulerian graphs. JGAA 13(3), 379–422 (2009)

Jünger, M., Leipert, S., Mutzel, P.: Level planarity testing in linear time. In: Whitesides, S.H. (ed.) GD 1998. LNCS, vol. 1547, pp. 224–237. Springer, Heidelberg (1999)

Schaefer, M.: Toward a theory of planarity: Hanani-tutte and planarity variants. In: Didimo, W., Patrignani, M. (eds.) GD 2012. LNCS, vol. 7704, pp. 162–173. Springer, Heidelberg (2013)