Document Open Access Logo

1-String B_2-VPG Representation of Planar Graphs

Authors Therese Biedl, Martin Derka

PDF
Thumbnail PDF

File

LIPIcs.SOCG.2015.141.pdf
  • Filesize: 0.66 MB
  • 15 pages

Document Identifiers

Author Details

Therese Biedl
Martin Derka

Cite As Get BibTex

Therese Biedl and Martin Derka. 1-String B_2-VPG Representation of Planar Graphs. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 141-155, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.SOCG.2015.141

Abstract

In this paper, we prove that every planar graph has a 1-string B_2-VPG representation - a string representation using paths in a rectangular grid that contain at most two bends. Furthermore, two paths representing vertices u, v intersect precisely once whenever there is an edge between u and v.

Subject Classification

Keywords
  • Graph drawing
  • string graphs
  • VPG graphs
  • planar graphs

Metrics

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

References

  1. Takao Asano, Shunji Kikuchi, and Nobuji Saito. A linear algorithm for finding Hamiltonian cycles in 4-connected maximal planar graphs. Discr. Applied Mathematics, 7(1):1 - 15, 1984. Google Scholar
  2. Therese C. Biedl and Martin Derka. 1-string B₂-VPG representation of planar graphs. CoRR, abs/1411.7277, 2014. Google Scholar
  3. Jérémie Chalopin and Daniel Gonçalves. Every planar graph is the intersection graph of segments in the plane: extended abstract. In ACM Symposium on Theory of Computing, STOC 2009, pages 631-638. ACM, 2009. Google Scholar
  4. Jérémie Chalopin, Daniel Gonçalves, and Pascal Ochem. Planar graphs are in 1-string. In ACM-SIAM Symposium on Discrete Algorithms, SODA '07, pages 609-617. SIAM, 2007. Google Scholar
  5. Jérémie Chalopin, Daniel Gonçalves, and Pascal Ochem. Planar graphs have 1-string representations. Discrete & Computational Geometry, 43(3):626-647, 2010. Google Scholar
  6. Steven Chaplick and Torsten Ueckerdt. Planar graphs as VPG-graphs. J. Graph Algorithms Appl., 17(4):475-494, 2013. Google Scholar
  7. Natalia de Castro, Francisco Javier Cobos, Juan Carlos Dana, Alberto Márquez, and Marc Noy. Triangle-free planar graphs and segment intersection graphs. J. Graph Algorithms Appl., 6(1):7-26, 2002. Google Scholar
  8. Hubert de Fraysseix, Patrice Ossona de Mendez, and János Pach. Representation of planar graphs by segments. Intuitive Geometry, 63:109-117, 1991. Google Scholar
  9. Gideon Ehrlich, Shimon Even, and Robert Endre Tarjan. Intersection graphs of curves in the plane. J. Comb. Theory, Ser. B, 21(1):8-20, 1976. Google Scholar
  10. Stefan Felsner, Kolja B. Knauer, George B. Mertzios, and Torsten Ueckerdt. Intersection graphs of L-shapes and segments in the plane. In Mathematical Foundations of Computer Science (MFCS'14), Part II, volume 8635 of Lecture Notes in Computer Science, pages 299-310. Springer, 2014. Google Scholar
  11. Irith Ben-Arroyo Hartman, Ilan Newman, and Ran Ziv. On grid intersection graphs. Discrete Mathematics, 87(1):41-52, 1991. Google Scholar
  12. Edward R. Scheinerman. Intersection Classes and Multiple Intersection Parameters of Graphs. PhD thesis, Princeton University, 1984. Google Scholar
  13. Hassler Whitney. A theorem on graphs. The Annals of Mathematics, 32(2):387-390, 1931. 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