Nothing Special   »   [go: up one dir, main page]
Skip to main content
SpringerLink
Log in

Strip Planarity Testing for Embedded Planar Graphs

  • Published:
Algorithmica Aims and scope Submit manuscript

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 \(\gamma :V \rightarrow \{1,2,\dots ,k\}\) and asks whether a planar drawing of G exists such that each edge is represented by a curve that is monotone in the y-direction and, for any \(u,v\in V\) with \(\gamma (u)<\gamma (v)\), it holds that \(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. Most notably, we provide a polynomial-time reduction from strip planarity testing to clustered planarity. We show that the strip planarity testing problem is polynomial-time solvable if G has a prescribed combinatorial embedding.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16
Fig. 17
Fig. 18
Fig. 19
Fig. 20
Fig. 21

Similar content being viewed by others

References

  1. Abbasi, S., Healy, P., Rextin, A.: Improving the running time of embedded upward planarity testing. Inf. Process. Lett. 110(7), 274–278 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  2. Aloupis, G., Barba, L., Carmi, P., Dujmovic, V., Frati, F., Morin, P.: Compatible connectivity-augmentation of planar disconnected graphs. In: Indyk, P. (ed.) Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium Discrete Algorithms (SODA ’15), pp. 1602–1615. SIAM, San Diego, CA (2015). doi:10.1137/1.9781611973730.106

  3. 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.) ACM-SIAM Symposium on Discrete Algorithms (SODA ’10). pp. 202–221 (2010)

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

    Article  MathSciNet  MATH  Google Scholar 

  5. Angelini, P., Da Lozzo, G., Di Battista, G., Frati, F., Roselli, V.: The importance of being proper (in clustered-level planarity and t-level planarity). Theor. Comput. Sci. 571, 1–9 (2015)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  9. Chambers, E.W., Eppstein, D., Goodrich, M.T., Löffler, M.: Drawing graphs in the plane with a prescribed outer face and polynomial area. J. Graph Algorithms Appl. 16(2), 243–259 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  10. Chiba, N., Yamanouchi, T., Nishizeki, T.: Linear algorithms for convex drawings of planar graphs. In: Bondy, J.A., Murty, U.S.R. (eds.) Progress in Graph Theory, pp. 153–173. Academic Press, New York, NY (1984)

    Google Scholar 

  11. Chimani, M., Di Battista, G., Frati, F., Klein, K.: Advances on testing c-planarity of embedded flat clustered graphs. In: Duncan, C.A., Symvonis, A. (eds.) Graph Drawing (GD ’14). LNCS, vol. 8871, pp. 416–427. Springer, Berlin (2014)

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  18. 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’09. LNCS, vol. 5849, pp. 69–80 (2010)

  19. Feng, Q., Cohen, R.F., Eades, P.: Planarity for clustered graphs. In: Spirakis (ed.) European Symposium on Algorithms (ESA ’95). LNCS, vol. 979, pp. 213–226 (1995)

  20. Forster, M., Bachmaier, C.: Clustered level planarity. In: van Emde Boas, P., Pokorný, J., Bieliková, M., Stuller, J. (eds.) SOFSEM ’04. LNCS, vol. 2932, pp. 218–228 (2004)

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

  22. Fulek, R.: Toward the Hanani-Tutte theorem for clustered graphs. CoRR abs/1410.3022 (2014). http://arxiv.org/abs/1410.3022

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  28. Jelínek, V., Jelínková, E., Kratochvíl, J., Lidický, B.: Clustered planarity: Embedded clustered graphs with two-component clusters. In: GD ’08. LNCS, vol. 5417, pp. 121–132 (2009)

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

  32. Kowalik, L., Kurowski, M.: Short path queries in planar graphs in constant time. In: Larmore, L.L., Goemans, M.X. (eds.) Symposium on Theory of Computing. pp. 143–148. ACM, New York (2003)

  33. Pach, J., Toth, G.: Monotone drawings of planar graphs. CoRR abs/1101.0967 (2011). http://arxiv.org/abs/1101.0967

  34. Schaefer, M.: Toward a theory of planarity: Hanani–Tutte and planarity variants. J. Graph Algorithms Appl. 17(4), 367–440 (2013)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  36. Tamassia, R.: On embedding a graph in the grid with the minimum number of bends. SIAM J. Comput. 16(3), 421–444 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  37. Tamassia, R. (ed.): Handbook of Graph Drawing and Visualization. Discrete Mathematics and Its Applications. CRC Press, Boca Raton, FL (2013)

    Google Scholar 

  38. Tarjan, R.E.: Depth first search and linear graph algorithms. SIAM J. Comput. 2, 146–160 (1972)

    Article  MathSciNet  MATH  Google Scholar 

  39. Whitney, H.: 2-Isomorphic graphs. Am. J. Math. 55(1), 245–254 (1933)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Wilhelm-Schickard-Institut für Informatik, Tübingen University, Tübingen, Germany

    Patrizio Angelini

  2. Department of Engineering, Roma Tre University, Rome, Italy

    Giordano Da Lozzo, Giuseppe Di Battista & Fabrizio Frati

Authors
  1. Patrizio Angelini
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Giordano Da Lozzo
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Giuseppe Di Battista
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Fabrizio Frati
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Giordano Da Lozzo.

Additional information

Angelini was partially supported by DFG Grant Ka812/17-1. Da Lozzo, Di Battista, and Frati were partially supported by MIUR Project AMANDA “Algorithmics for MAssive and Networked DAta”, prot. 2012C4E3KT_001.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Angelini, P., Da Lozzo, G., Di Battista, G. et al. Strip Planarity Testing for Embedded Planar Graphs. Algorithmica 77, 1022–1059 (2017). https://doi.org/10.1007/s00453-016-0128-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-016-0128-9

Keywords

Search

Navigation