Clustered Planarity with Pipes

Authors Patrizio Angelini, Giordano Da Lozzo



PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2016.13.pdf
  • Filesize: 0.66 MB
  • 13 pages

Document Identifiers

Author Details

Patrizio Angelini
Giordano Da Lozzo

Cite AsGet BibTex

Patrizio Angelini and Giordano Da Lozzo. Clustered Planarity with Pipes. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 13:1-13:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.ISAAC.2016.13

Abstract

We study the version of the C-Planarity problem in which edges connecting the same pair of clusters must be grouped into pipes, which generalizes the Strip Planarity problem. We give algorithms to decide several families of instances for the two variants in which the order of the pipes around each cluster is given as part of the input or can be chosen by the algorithm.
Keywords
  • Clustered Planarity
  • FPT
  • SEFE
  • Graph Drawing

Metrics

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

References

  1. Patrizio Angelini and Giordano Da Lozzo. Clustered Planarity with Pipes. ArXiv e-prints, 2016. URL: http://arxiv.org/abs/1609.09679.
  2. Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista, and Fabrizio Frati. Strip planarity testing for embedded planar graphs. Algorithmica, 2016. To appear. Google Scholar
  3. Paola Bertolazzi, Giuseppe Di Battista, Carlo Mannino, and Roberto Tamassia. Optimal upward planarity testing of single-source digraphs. SIAM J. Comput., 27(1):132-169, 1998. URL: http://dx.doi.org/10.1137/S0097539794279626.
  4. Thomas Bläsius, Stephen G. Kobourov, and Ignaz Rutter. Simultaneous embedding of planar graphs. In Handbook of Graph Drawing and Visualization. CRC Press, 2013. Google Scholar
  5. Thomas Bläsius and Ignaz Rutter. A new perspective on clustered planarity as a combinatorial embedding problem. Theor. Comput. Sci., 609:306-315, 2016. URL: http://dx.doi.org/10.1016/j.tcs.2015.10.011.
  6. Thomas Bläsius and Ignaz Rutter. Simultaneous PQ-ordering with applications to constrained embedding problems. ACM Trans. Algorithms, 12(2):16, 2016. URL: http://dx.doi.org/10.1145/2738054.
  7. K. S. Booth and G. S. Lueker. Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. of Computer and System Sciences, 13(3):335-379, 1976. Google Scholar
  8. Hsien-Chih Chang, Jeff Erickson, and Chao Xu. Detecting weakly simple polygons. In SODA'15, pages 1655-1670. SIAM, 2015. URL: http://dx.doi.org/10.1137/1.9781611973730.
  9. Pier Francesco Cortese, Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani, and Maurizio Pizzonia. C-planarity of c-connected clustered graphs. J. Graph Algorithms Appl., 12(2):225-262, 2008. Google Scholar
  10. Pier Francesco Cortese, Giuseppe Di Battista, Maurizio Patrignani, and Maurizio Pizzonia. On embedding a cycle in a plane graph. Discrete Mathematics, 309(7):1856-1869, 2009. URL: http://dx.doi.org/10.1016/j.disc.2007.12.090.
  11. Giuseppe Di Battista, Peter Eades, Roberto Tamassia, and Ioannis G. Tollis. Graph Drawing: Algorithms for the Visualization of Graphs. Prentice-Hall, 1999. Google Scholar
  12. Qing-Wen Feng, Robert F. Cohen, and Peter Eades. Planarity for clustered graphs. In Algorithms - ESA'95, Third Annual European Symposium, Proc., pages 213-226, 1995. URL: http://dx.doi.org/10.1007/3-540-60313-1_145.
  13. Radoslav Fulek. Toward the Hanani-Tutte Theorem for Clustered Graphs. ArXiv e-prints, 2014. URL: http://arxiv.org/abs/1410.3022.
  14. Vít Jelínek, Eva Jelínková, Jan Kratochvíl, and Bernard Lidický. Clustered planarity: Embedded clustered graphs with two-component clusters. In GD'08, pages 121-132, 2008. URL: http://dx.doi.org/10.1007/978-3-642-00219-9_13.
  15. Marcus Schaefer. Toward a theory of planarity: Hanani-tutte and planarity variants. J. of Graph Algorithms and Applications, 17(4):367-440, 2013. 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