Document Open Access Logo

Efficiently Partitioning the Edges of a 1-Planar Graph into a Planar Graph and a Forest

Authors Sam Barr, Therese Biedl

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2021.16.pdf
  • Filesize: 0.85 MB
  • 15 pages

Document Identifiers

Author Details

Sam Barr
  • University of Waterloo, Canada
Therese Biedl
  • University of Waterloo, Canada

Funding

  • Biedl, Therese: Research supported by NSERC; FRN RGPIN-2020-03958.

Cite As Get BibTex

Sam Barr and Therese Biedl. Efficiently Partitioning the Edges of a 1-Planar Graph into a Planar Graph and a Forest. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 16:1-16:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ISAAC.2021.16

Abstract

1-planar graphs are graphs that can be drawn in the plane such that any edge intersects with at most one other edge. Ackerman showed that the edges of a 1-planar graph can be partitioned into a planar graph and a forest, and claims that the proof leads to a linear time algorithm. However, it is not clear how one would obtain such an algorithm from his proof. In this paper, we first reprove Ackerman’s result (in fact, we prove a slightly more general statement) and then show that the split can be found in linear time by using an edge-contraction data structure by Holm, Italiano, Karczmarz, Łącki, Rotenberg and Sankowski.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
  • Theory of computation → Dynamic graph algorithms
Keywords
  • 1-planar graphs
  • edge partitions
  • algorithms
  • data structures

Metrics

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

References

  1. Eyal Ackerman. A note on 1-planar graphs. Discrete Appl. Math., 175:104-108, 2014. URL: http://dx.doi.org/10.1016/j.dam.2014.05.025.
  2. Md. Jawaherul Alam, Franz J. Brandenburg, and Stephen G. Kobourov. Straight-line grid drawings of 3-connected 1-planar graphs. In Stephen Wismath and Alexander Wolff, editors, Graph Drawing, volume 8242 of Lecture Notes in Computer Science, pages 83-94. Springer, 2013. URL: http://dx.doi.org/10.1007/978-3-319-03841-4_8.
  3. Patrizio Angelini, Henry Förster, Michael Hoffmann, Michael Kaufmann, Stephen Kobourov, Giuseppe Liotta, and Maurizio Patrignani. The QuaSEFE problem. In International Symposium on Graph Drawing and Network Visualization, volume 11904 of Lecture Notes in Computer Science, pages 268-275. Springer, 2019. URL: http://dx.doi.org/10.1007/978-3-030-35802-0_21.
  4. Michael A. Bekos, Emilio Di Giacomo, Walter Didimo, Giuseppe Liotta, Fabrizio Montecchiani, and Chrysanthi Raftopoulou. Edge partitions of optimal 2-plane and 3-plane graphs. Discrete Mathematics, 342(4):1038-1047, 2019. URL: http://dx.doi.org/10.1016/j.disc.2018.12.002.
  5. Therese Biedl, Anna Lubiw, and Owen Merkel. List coloring bipartite graphs embedded on a surface. Unpublished Manuscript, 2019. Google Scholar
  6. R. Bodendiek, H. Schumacher, and K. Wagner. Bemerkungen zu einem sechsfarbenproblem von g. ringel. Abh. Math. Semin. Univ. Hambg., pages 41-52, 1983. URL: http://dx.doi.org/10.1007/BF02941309.
  7. Franz J. Brandenburg. Recognizing optimal 1-planar graphs in linear time. Algorithmica, 80(1):1-28, 2018. URL: http://dx.doi.org/10.1007/s00453-016-0226-8.
  8. Július Czap and Dávid Hudák. On drawings and decompositions of 1-planar graphs. Electron. J. Combin., 20(2):Paper 54, 8, 2013. URL: http://dx.doi.org/10.37236/2392.
  9. Emilio Di Giacomo, Walter Didimo, William S. Evans, Giuseppe Liotta, Henk Meijer, Fabrizio Montecchiani, and Stephen K. Wismath. New results on edge partitions of 1-plane graphs. Theoretical Computer Science, 713:78-84, 2018. URL: http://dx.doi.org/10.1016/j.tcs.2017.12.024.
  10. Reinhard Diestel. Graph theory, volume 173 of Graduate Texts in Mathematics. Springer, Berlin, fifth edition, 2018. URL: http://dx.doi.org/10.1007/978-3-662-53622-3.
  11. Harold N. Gabow and Herbert H. Westermann. Forests, frames, and games: algorithms for matroid sums and applications. Algorithmica, 7(5-6):465-497, 1992. URL: http://dx.doi.org/10.1007/BF01758774.
  12. Alexander Grigoriev and Hans L. Bodlaender. Algorithms for graphs embeddable with few crossings per edge. Algorithmica, 49(1):1-11, 2007. URL: http://dx.doi.org/10.1007/s00453-007-0010-x.
  13. Shai Gutner and Michael Tarsi. Some results on (a:b)-choosability. Discrete Mathematics, 309(8):2260-2270, 2009. URL: http://dx.doi.org/10.1016/j.disc.2008.04.061.
  14. Jacob Holm, Giuseppe F. Italiano, Adam Karczmarz, Jakub Łącki Łącki, Eva Rotenberg, and Piotr Sankowski. Contracting a planar graph efficiently. In 25th European Symposium on Algorithms, volume 87 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 50, 15. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2017. Google Scholar
  15. Seok-Hee Hong and Takeshi Tokuyama. Beyond Planar Graphs. Springer Nature, Singapore, 2020. Google Scholar
  16. Dmitri V. Karpov. An upper bound on the number of edges in an almost planar bipartite graph. J. Math Sci., 196:737-746, 2014. URL: http://dx.doi.org/10.1007/s10958-014-1690-9.
  17. Jon Kleinberg and Éva Tardos. Algorithm Design. Addison-Wesley Longman Publishing Co., Inc., USA, 2005. Google Scholar
  18. Stephen G. Kobourov, Giuseppe Liotta, and Fabrizio Montecchiani. An annotated bibliography on 1-planarity. Comput. Sci. Rev., 25:49-67, 2017. URL: http://dx.doi.org/10.1016/j.cosrev.2017.06.002.
  19. William J. Lenhart, Giuseppe Liotta, and Fabrizio Montecchiani. On partitioning the edges of 1-plane graphs. Theor. Comput. Sci., 662:59-65, 2017. URL: http://dx.doi.org/10.1016/j.tcs.2016.12.004.
  20. C. St. J. A. Nash-Williams. Decomposition of finite graphs into forests. J. London Math. Soc., 39:12, 1964. URL: http://dx.doi.org/10.1112/jlms/s1-39.1.12.
  21. Gerhard Ringel. Ein Sechsfarbenproblem auf der Kugel. Abh. Math. Sem. Univ. Hamburg, 29:107-117, 1965. URL: http://dx.doi.org/10.1007/BF02996313.
  22. Gerhard Ringel. Two trees in maximal planar bipartite graphs. J. Graph Theory, 17(6):755-758, 1993. URL: http://dx.doi.org/10.1002/jgt.3190170610.
  23. Marcus Schaefer. The graph crossing number and its variants: A survey. The Electronic Journal of Combinatorics [electronic only], 20, April 2013. URL: http://dx.doi.org/10.37236/2713.
  24. Walter Schnyder. Embedding planar graphs on the grid. In Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '90, pages 138-148, USA, 1990. Society for Industrial and Applied Mathematics. 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