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

Optimal-Area Visibility Representations of Outer-1-Plane Graphs

  • Conference paper
  • First Online:
Graph Drawing and Network Visualization (GD 2021)

Part of the book series: Lecture Notes in Computer Science ((LNISA,volume 12868))

Included in the following conference series:

  • 653 Accesses

Abstract

This paper studies optimal-area visibility representations of n-vertex outer-1-plane graphs, i.e. graphs with a given embedding where all vertices are on the boundary of the outer face and each edge is crossed at most once. We show that any graph of this family admits an embedding-preserving visibility representation whose area is \(O(n^{1.5})\) and prove that this area bound is worst-case optimal. We also show that \(O(n^{1.48})\) area can be achieved if we represent the vertices as L-shaped orthogonal polygons or if we do not respect the embedding but still have at most one crossing per edge. We also extend the study to other representation models and, among other results, construct asymptotically optimal \(O(n\, pw(G))\) area bar-1-visibility representations, where \(pw(G)\in O(\log n)\) is the pathwidth of the outer-1-planar graph G.

Work of TB supported by NSERC; FRN RGPIN-2020-03958. Work of GL supported by MIUR, grant 20174LF3T8 “AHeAD: efficient Algorithms for HArnessing networked Data”. Work of FM supported by Dipartimento di Ingegneria, Università degli Studi di Perugia, grant RICBA19FM.

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

Access this chapter

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

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 69.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 89.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    We do not propose actually drawing graphs in this model (its readability would not be good), but it is convenient as a name for “all drawing models that we study here”.

  2. 2.

    Readers familiar with LR-drawings [11, 18, 31] may notice the similarity of constructing the path-drawing with the (rotated) LR-drawing of \(\pi \), except that we draw the outer-1-planar graph rather than its dual tree.

References

  1. Angelini, P., Bekos, M.A., Kaufmann, M., Montecchiani, F.: On 3D visibility representations of graphs with few crossings per edge. Theor. Comput. Sci. 784, 11–20 (2019)

    Article  MathSciNet  Google Scholar 

  2. Arleo, A., et al.: Visibility representations of boxes in 2.5 dimensions. Comput. Geom. 72, 19–33 (2018)

    Google Scholar 

  3. Auer, C., et al.: Outer 1-planar graphs. Algorithmica 74(4), 1293–1320 (2016)

    Article  MathSciNet  Google Scholar 

  4. Biedl, T.: Small drawings of outerplanar graphs, series-parallel graphs, and other planar graphs. Discrete Comput. Geom. 45(1), 141–160 (2011)

    Article  MathSciNet  Google Scholar 

  5. Biedl, T.: A 4-approximation for the height of drawing 2-connected outer-planar graphs. In: Erlebach, T., Persiano, G. (eds.) WAOA 2012. LNCS, vol. 7846, pp. 272–285. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38016-7_22

    Chapter  MATH  Google Scholar 

  6. Biedl, T.: Height-preserving transformations of planar graph drawings. In: Duncan, C., Symvonis, A. (eds.) GD 2014. LNCS, vol. 8871, pp. 380–391. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-45803-7_32

    Chapter  MATH  Google Scholar 

  7. Biedl, T.: Drawing outer-1-planar graphs revisited. In: Auber, D., Valtr, P. (eds.) GD. LNCS, vol. 12590, pp. 526–527. Springer (2020), CoRR 2009.07106

    Google Scholar 

  8. Biedl, T.: Horton-Strahler number, rooted pathwidth and upward drawings of tree, accepted pending revisions at Information Processing Letters. CoRR 1506.02096 (2021)

    Google Scholar 

  9. Biedl, T., Chaplick, S., Kaufmann, M., Montecchiani, F., Nöllenburg, M., Raftopoulou, C.: On layered fan-planar graph drawings. In: Esparza, J., Král’, D. (eds.) MFCS 2020. LIPIcs, vol. 170, pp. 14:1–14:13. LZI (2020)

    Google Scholar 

  10. Biedl, T.C., Kaufmann, M.: Area-efficient static and incremental graph drawings. In: Burkard, R., Woeginger, G. (eds.) ESA 1997. LNCS, vol. 1284, pp. 37–52. Springer, Heidelberg (1997). https://doi.org/10.1007/3-540-63397-9_4

    Chapter  Google Scholar 

  11. Biedl, T., Liotta, G., Lynch, J., Montecchiani, F.: Generalized LR-drawings of trees. In: Canadian Conference on Computational Geometry (CCCG), pp. 78–88 (2021)

    Google Scholar 

  12. Biedl, T.C., Liotta, G., Lynch, J., Montecchiani, F.: Optimal-area visibility representations of outer-1-plane graphs. CoRR abs/2108.11768 (2021)

    Google Scholar 

  13. Bläsius, T., Brückner, G., Rutter, I.: Complexity of higher-degree orthogonal graph embedding in the kandinsky model. In: Schulz, A.S., Wagner, D. (eds.) ESA 2014. LNCS, vol. 8737, pp. 161–172. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-44777-2_14

    Chapter  Google Scholar 

  14. Bose, P., et al.: A visibility representation for graphs in three dimensions. J. Graph Algorithms Appl. 2(3), 1–16 (1998)

    Article  MathSciNet  Google Scholar 

  15. Brandenburg, F.J.: 1-visibility representations of 1-planar graphs. J. Graph Algorithms Appl. 18(3), 421–438 (2014)

    Article  MathSciNet  Google Scholar 

  16. Brandenburg, F.J.: T-shape visibility representations of 1-planar graphs. Comput. Geom. 69, 16–30 (2018)

    Article  MathSciNet  Google Scholar 

  17. Brandenburg, F.J., Heinsohn, N., Kaufmann, M., Neuwirth, D.: On bar (1,j)-visibility graphs. In: Rahman, M.S., Tomita, E. (eds.) WALCOM 2015. LNCS, vol. 8973, pp. 246–257. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-15612-5_22

    Chapter  Google Scholar 

  18. Chan, T.M.: A near-linear area bound for drawing binary trees. Algorithmica 34(1), 1–13 (2002)

    Article  MathSciNet  Google Scholar 

  19. Dean, A.M., Evans, W.S., Gethner, E., Laison, J.D., Safari, M.A., Trotter, W.T.: Bar \(k\)-visibility graphs. J. Graph Algorithms Appl. 11(1), 45–59 (2007)

    Article  MathSciNet  Google Scholar 

  20. Dehkordi, H.R., Eades, P.: Every outer-1-plane graph has a right angle crossing drawing. Int. J. Comput. Geom. Appl. 22(6), 543–558 (2012)

    Article  MathSciNet  Google Scholar 

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

    MATH  Google Scholar 

  22. Di Giacomo, E., et al.: Ortho-polygon visibility representations of embedded graphs. Algorithmica 80(8), 2345–2383 (2018)

    Article  MathSciNet  Google Scholar 

  23. Didimo, W., Liotta, G., Montecchiani, F.: A survey on graph drawing beyond planarity. ACM Comput. Surv. 52(1), 4:1–4:37 (2019)

    Google Scholar 

  24. Duchet, P., Hamidoune, Y.O., Vergnas, M.L., Meyniel, H.: Representing a planar graph by vertical lines joining different levels. Discret. Math. 46(3), 319–321 (1983)

    Article  MathSciNet  Google Scholar 

  25. Eggleton, R.: Rectilinear drawings of graphs. Util. Math. 29, 149–172 (1986)

    MathSciNet  MATH  Google Scholar 

  26. Evans, W.S., Kaufmann, M., Lenhart, W., Mchedlidze, T., Wismath, S.K.: Bar 1-visibility graphs vs. other nearly planar graphs. J. Graph Algorithms Appl. 18(5), 721–739 (2014)

    Google Scholar 

  27. Evans, W.S., Liotta, G., Montecchiani, F.: Simultaneous visibility representations of plane \(st\)-graphs using L-shapes. Theor. Comput. Sci. 645, 100–111 (2016)

    Article  MathSciNet  Google Scholar 

  28. Fan, J.H., Lin, C.C., Lu, H.I., Yen, H.C.: Width-optimal visibility representations of plane graphs. In: Tokuyama, T. (ed.) ISAAC, pp. 160–171. Springer, LNCS (2007)

    Google Scholar 

  29. Felsner, S., Liotta, G., Wismath, S.: Straight-line drawings on restricted integer grids in two and three dimensions. J. Graph Algorithms Appl. 7(4), 335–362 (2003)

    Article  MathSciNet  Google Scholar 

  30. Fößmeier, U., Kant, G., Kaufmann, M.: 2-Visibility drawings of planar graphs. In: North, S. (ed.) GD 1996. LNCS, vol. 1190, pp. 155–168. Springer, Heidelberg (1997). https://doi.org/10.1007/3-540-62495-3_45

    Chapter  Google Scholar 

  31. Frati, F., Patrignani, M., Roselli, V.: LR-drawings of ordered rooted binary trees and near-linear area drawings of outerplanar graphs. J. Comput. Syst. Sci. 107, 28–53 (2020)

    Article  MathSciNet  Google Scholar 

  32. He, X., Zhang, H.: Nearly optimal visibility representations of plane graphs. SIAM J. Discrete Math. 22(4), 1364–1380 (2008)

    Article  MathSciNet  Google Scholar 

  33. Hong, S., Eades, P., Katoh, N., Liotta, G., Schweitzer, P., Suzuki, Y.: A linear-time algorithm for testing outer-1-planarity. Algorithmica 72(4), 1033–1054 (2015)

    Article  MathSciNet  Google Scholar 

  34. Hong, S., Tokuyama, T. (eds.): Beyond Planar Graphs. Springer, Singapore (2020). https://doi.org/10.1007/978-981-15-6533-5

    Book  MATH  Google Scholar 

  35. Kobourov, S., Liotta, G., Montecchiani, F.: An annotated bibliography on 1-planarity. Comput. Sci. Rev. 25, 49–67 (2017)

    Article  MathSciNet  Google Scholar 

  36. Liotta, G., Montecchiani, F.: L-visibility drawings of IC-planar graphs. Inf. Process. Lett. 116(3), 217–222 (2016)

    Article  MathSciNet  Google Scholar 

  37. Liotta, G., Montecchiani, F., Tappini, A.: Ortho-polygon visibility representations of 3-connected 1-plane graphs. Theor. Comput. Sci. 863, 40–52 (2021)

    Article  MathSciNet  Google Scholar 

  38. Otten, R., van Wijk, J.: Graph representations in interactive layout design. In: IEEE ISCS, pp. 914–918 (1978)

    Google Scholar 

  39. Rosenstiehl, P., Tarjan, R.E.: Rectilinear planar layouts and bipolar orientation of planar graphs. Discrete Comput. Geom. 1, 343–353 (1986)

    Article  MathSciNet  Google Scholar 

  40. Shermer, T.: Block visibility representations III: external visibility and complexity. In: CCCG. International Informatics Series, vol. 5, pp. 234–239. Carleton University Press (1996)

    Google Scholar 

  41. Tamassia, R., Tollis, I.G.: A unified approach to visibility representations of planar graphs. Discrete Comput. Geom. 1(4), 321–341 (1986). https://doi.org/10.1007/BF02187705

    Article  MathSciNet  MATH  Google Scholar 

  42. Wismath, S.: Characterizing bar line-of-sight graphs. In: Snoeyink, J. (ed.) SoCG, pp. 147–152. ACM (1985)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. David R. Cheriton School of Computer Science, University of Waterloo, Waterloo, Canada

    Therese Biedl & Jayson Lynch

  2. Department of Engineering, University of Perugia, Perugia, Italy

    Giuseppe Liotta & Fabrizio Montecchiani

Authors
  1. Therese Biedl
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Giuseppe Liotta
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jayson Lynch
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Fabrizio Montecchiani
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Therese Biedl .

Editor information

Editors and Affiliations

  1. University of Glasgow, Glasgow, UK

    Helen C. Purchase

  2. University of Passau, Passau, Germany

    Ignaz Rutter

Rights and permissions

Reprints and permissions

Copyright information

© 2021 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Biedl, T., Liotta, G., Lynch, J., Montecchiani, F. (2021). Optimal-Area Visibility Representations of Outer-1-Plane Graphs. In: Purchase, H.C., Rutter, I. (eds) Graph Drawing and Network Visualization. GD 2021. Lecture Notes in Computer Science(), vol 12868. Springer, Cham. https://doi.org/10.1007/978-3-030-92931-2_21

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-92931-2_21

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-92930-5

  • Online ISBN: 978-3-030-92931-2

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation