Document Open Access Logo

On Visibility Representations of Non-Planar Graphs

Authors Therese Biedl, Giuseppe Liotta, Fabrizio Montecchiani

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2016.19.pdf
  • Filesize: 0.55 MB
  • 16 pages

Document Identifiers

Author Details

Therese Biedl
Giuseppe Liotta
Fabrizio Montecchiani

Cite As Get BibTex

Therese Biedl, Giuseppe Liotta, and Fabrizio Montecchiani. On Visibility Representations of Non-Planar Graphs. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 19:1-19:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.SoCG.2016.19

Abstract

A rectangle visibility representation (RVR) of a graph consists of an assignment of axis-aligned rectangles to vertices such that for every edge there exists a horizontal or vertical line of sight between the rectangles assigned to its endpoints. Testing whether a graph has an RVR is known to be NP-hard. In this paper, we study the problem of finding an RVR under the assumption that an embedding in the plane of the input graph is fixed and we are looking for an RVR that reflects this embedding. We show that in this case the problem can be solved in polynomial time for general embedded graphs and in linear time for 1-plane graphs (i.e., embedded graphs having at most one crossing per edge). The linear time algorithm uses a precise list of forbidden configurations, which extends the set known for straight-line drawings of 1-plane graphs. These forbidden configurations can be tested for in linear time, and so in linear time we can test whether a 1-plane graph has an RVR and either compute such a representation or report a negative witness. Finally, we discuss some extensions of our study to the case when the embedding is not fixed but the RVR can have at most one crossing per edge.

Subject Classification

Keywords
  • Visibility Representations
  • 1-Planarity
  • Recognition Algorithm
  • Forbidden Configuration

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Md. Jawaherul Alam, Franz J. Brandenburg, and Stephen G. Kobourov. Straight-line grid drawings of 3-connected 1-planar graphs. In GD 2013, volume 8242 of LNCS, pages 83-94. Springer, 2013. Google Scholar
  2. Therese Biedl, Giuseppe Liotta, and Fabrizio Montecchiani. On visibility representations of non-planar graphs. CoRR, abs/1511.08592, 2015. URL: http://arxiv.org/abs/1511.08592.
  3. Therese Biedl, Anna Lubiw, Mark Petrick, and Michael J. Spriggs. Morphing orthogonal planar graph drawings. ACM Trans. Algorithms, 9(4):29, 2013. URL: http://dx.doi.org/10.1145/2500118.
  4. Prosenjit Bose, Alice M. Dean, Joan P. Hutchinson, and Thomas C. Shermer. On rectangle visibility graphs. In GD 1996, volume 1190 of LNCS, pages 25-44. Springer, 1997. Google Scholar
  5. Franz J. Brandenburg. 1-Visibility representations of 1-planar graphs. J. Graph Algorithms Appl., 18(3):421-438, 2014. Google Scholar
  6. Norishige Chiba and Takao Nishizeki. Arboricity and subgraph listing algorithms. SIAM J. Comput., 14(1):210-223, 1985. Google Scholar
  7. Sabine Cornelsen and Andreas Karrenbauer. Accelerated bend minimization. J. Graph Algorithms Appl., 16(3):635-650, 2012. Google Scholar
  8. Alice M. Dean, William S. Evans, Ellen Gethner, Joshua D. Laison, Mohammad Ali Safari, and William T. Trotter. Bar k-visibility graphs. J. Graph Algorithms Appl., 11(1):45-59, 2007. Google Scholar
  9. Giuseppe Di Battista, Peter Eades, Roberto Tamassia, and Ioannis G. Tollis. Graph Drawing: Algorithms for the Visualization of Graphs. Prentice-Hall, 1999. Google Scholar
  10. Pierre Duchet, Yahya Ould Hamidoune, Michel Las Vergnas, and Henry Meyniel. Representing a planar graph by vertical lines joining different levels. Discrete Math., 46(3):319-321, 1983. Google Scholar
  11. William S. Evans, Michael Kaufmann, William Lenhart, Tamara Mchedlidze, and Stephen K. Wismath. Bar 1-visibility graphs vs. other nearly planar graphs. J. Graph Algorithms Appl., 18(5):721-739, 2014. Google Scholar
  12. Éric Fusy. Transversal structures on triangulations: A combinatorial study and straight-line drawings. Discrete Math., 309(7):1870-1894, 2009. Google Scholar
  13. Seok-Hee Hong, Peter Eades, Giuseppe Liotta, and Sheung-Hung Poon. Fáry’s theorem for 1-planar graphs. In COCOON 2012, volume 7434 of LNCS, pages 335-346. Springer, 2012. Google Scholar
  14. Goos Kant. A more compact visibility representation. Int. J. Comput. Geometry Appl., 7(3):197-210, 1997. Google Scholar
  15. Goos Kant and Xin He. Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems. Theor. Comput. Sci., 172(1-2):175-193, 1997. Google Scholar
  16. Goos Kant, Giuseppe Liotta, Roberto Tamassia, and Ioannis G. Tollis. Area requirement of visibility representations of trees. Inf. Process. Lett., 62(2):81-88, 1997. Google Scholar
  17. Ralph H. J. M. Otten and J. G. Van Wijk. Graph representations in interactive layout design. In IEEE ISCSS, pages 914-918. IEEE, 1978. Google Scholar
  18. János Pach and Gáza Tóth. Graphs drawn with few crossings per edge. Combinatorica, 17(3):427-439, 1997. Google Scholar
  19. Pierre Rosenstiehl and Robert Endre Tarjan. Rectilinear planar layouts and bipolar orientations of planar graphs. Discr. & Comput. Geom., 1:343-353, 1986. Google Scholar
  20. Thomas C. Shermer. On rectangle visibility graphs. III. External visibility and complexity. In CCCG 1996, pages 234-239. Carleton University Press, 1996. Google Scholar
  21. Ileana Streinu and Sue Whitesides. Rectangle visibility graphs: Characterization, construction, and compaction. In STACS 2003, volume 2607 of LNCS, pages 26-37. Springer, 2003. Google Scholar
  22. Roberto Tamassia. On embedding a graph in the grid with the minimum number of bends. SIAM J. Computing, 16(3):421-444, 1987. Google Scholar
  23. Roberto Tamassia and Ioannis G. Tollis. A unified approach to visibility representations of planar graphs. Discr. &Comput. Geom., 1(1):321-341, 1986. Google Scholar
  24. Carsten Thomassen. Plane representations of graphs. In Progress in Graph Theory, pages 43-69. AP, 1984. Google Scholar
  25. Carsten Thomassen. Rectilinear drawings of graphs. J. Graph Theory, 12(3):335-341, 1988. Google Scholar
  26. Stephen K. Wismath. Characterizing bar line-of-sight graphs. In SoCG 1985, pages 147-152. ACM, 1985. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact