Document Open Access Logo

The Planar Tree Packing Theorem

Authors Markus Geyer, Michael Hoffmann, Michael Kaufmann, Vincent Kusters, Csaba Tóth

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2016.41.pdf
  • Filesize: 0.62 MB
  • 15 pages

Document Identifiers

Author Details

Markus Geyer
Michael Hoffmann
Michael Kaufmann
Vincent Kusters
Csaba Tóth

Cite As Get BibTex

Markus Geyer, Michael Hoffmann, Michael Kaufmann, Vincent Kusters, and Csaba Tóth. The Planar Tree Packing Theorem. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 41:1-41:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.SoCG.2016.41

Abstract

Packing graphs is a combinatorial problem where several given graphs are being mapped into a common host graph such that every edge is used at most once. In the planar tree packing problem we are given two trees T1 and T2 on n vertices and have to find a planar graph on n vertices that is the edge-disjoint union of T1 and T2. A clear exception that must be made is the star which cannot be packed together with any other tree. But according to a conjecture of Garcia et al. from 1997 this is the only exception, and all other pairs of trees admit a planar packing. Previous results addressed various special cases, such as a tree and a spider tree, a tree and a caterpillar, two trees of diameter four, two isomorphic trees, and trees of maximum degree three. Here we settle the conjecture in the affirmative and prove its general form, thus making it the planar tree packing theorem. The proof is constructive and provides a polynomial time algorithm to obtain a packing for two given nonstar trees.

Subject Classification

Keywords
  • graph drawing
  • simultaneous embedding
  • planar graph
  • graph packin

Metrics

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

References

  1. J. Akiyama and V. Chvátal. Packing paths perfectly. Discrete Math., 85(3):247-255, 1990. Google Scholar
  2. P. Braß, E. Cenek, C. A. Duncan, A. Efrat, C. Erten, D. Ismailescu, S. G. Kobourov, A. Lubiw, and J. S. B. Mitchell. On simultaneous planar graph embeddings. Comput. Geom., 36(2):117-130, 2007. Google Scholar
  3. Y. Caro and R. Yuster. Packing graphs: The packing problem solved. Electr. J. Combin., 4(1), 1997. Google Scholar
  4. D. Eppstein. Arboricity and bipartite subgraph listing algorithms. Inform. Process. Lett., 51(4):207-211, 1994. Google Scholar
  5. P. Erdős. Extremal problems in graph theory. In M. Fiedler, editor, Theory of Graphs and its Applications, pages 29-36. Academic Press, 1965. Google Scholar
  6. A. Frank and Z. Szigeti. A note on packing paths in planar graphs. Math. Program., 70(2):201-209, 1995. Google Scholar
  7. F. Frati. Planar packing of diameter-four trees. In Proc. 21st Canad. Conf. Comput. Geom., pages 95-98, 2009. Google Scholar
  8. F. Frati, M. Geyer, and M. Kaufmann. Planar packings of trees and spider trees. Inform. Process. Lett., 109(6):301-307, 2009. Google Scholar
  9. A. García, C. Hernando, F. Hurtado, M. Noy, and J. Tejel. Packing trees into planar graphs. J. Graph Theory, pages 172-181, 2002. Google Scholar
  10. M. Geyer, M. Hoffmann, M. Kaufmann, V. Kusters, and Cs. D. Tóth. Planar packing of binary trees. In Proc. 13th Algorithms and Data Struct. Sympos., volume 8037 of Lecture Notes Comput. Sci., pages 353-364. Springer, 2013. Google Scholar
  11. D. Gonçalves. Edge partition of planar graphs into two outerplanar graphs. In Proc. 37th Annu. ACM Sympos. Theory Comput., pages 504-512. ACM Press, 2005. Google Scholar
  12. A. Gyárfás and J. Lehel. Packing trees of different order into K_n. In Combinatorics, volume 18 of Colloq. Math. Soc. János Bolyai, pages 463-469. North Holland, 1978. Google Scholar
  13. S. M. Hedetniemi, S. T. Hedetniemi, and P. J. Slater. A note on packing two trees into K_N. Ars Combin., 11:149-153, 1981. Google Scholar
  14. M. Maheo, J.-F. Saclé, and M. Woźniak. Edge-disjoint placement of three trees. European J. Combin., 17(6):543-563, 1996. Google Scholar
  15. P. Mutzel, T. Odenthal, and M. Scharbrodt. The thickness of graphs: A survey. Graphs and Combinatorics, 14(1):59-73, 1998. Google Scholar
  16. C. St. J. A. Nash-Williams. Edge-disjoint spanning trees of finite graphs. Journal of The London Mathematical Society, s1-36:445-450, 1961. Google Scholar
  17. Y. Oda and K. Ota. Tight planar packings of two trees. In European Workshop on Computational Geometry, pages 215-216, 2006. Google Scholar
  18. W. Schnyder. Planar graphs and poset dimension. Order, 5:323-343, 1989. Google Scholar
  19. S.K. Teo and H.P. Yap. Packing two graphs of order n having total size at most 2n-2. Graphs and Combinatorics, 6(2):197-205, 1990. Google Scholar
  20. W. T. Tutte. On the problem of decomposing a graph into n connected factors. Journal of the London Mathematical Society, s1-36(1):221-230, 1961. 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