Nothing Special   »   [go: up one dir, main page]
Skip to main content
SpringerLink
Log in

Large Induced Acyclic and Outerplanar Subgraphs of 2-Outerplanar Graph

  • Original Paper
  • Published:
Graphs and Combinatorics Aims and scope Submit manuscript

Abstract

Albertson and Berman conjectured that every planar graph has an induced forest on half of its vertices. The best known lower bound, due to Borodin, is that every planar graph has an induced forest on two fifths of its vertices. In a related result, Chartran and Kronk, proved that the vertices of every planar graph can be partitioned into three sets, each of which induce a forest. We show tighter results for 2-outerplanar graphs. We show that every 2-outerplanar graph has an induced forest on at least half the vertices by showing that its vertices can be partitioned into two sets, each of which induces a forest. We also show that every 2-outerplanar graph has an induced outerplanar graph on at least two-thirds of its vertices.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6

Similar content being viewed by others

Notes

  1. Formal definitions of graph theoretic terms will be given at the end of this section.

References

  1. Aifeng, Y., Jinjiang, Y.: On the vertex arboricity of planar graphs of diameter two. Discret. Math. 307(19–20), 2438–2447 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  2. Albertson, M.O., Berman, D.M.: A conjecture on planar graphs. In: Bondy, J.A., Murty, U.S.R. (eds.) Graph Theory and Related Topics, p. 357. Academic Press (1979)

  3. Angelini, P., Evans, W., Frati, F., Gudmundsson, J.: SEFE with no mapping via large induced outerplane graphs in plane graphs. J. Graph Theory 82(1), 45–64 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  4. Baker, B.S.: Approximation algorithms for NP-complete problems on planar graphs. J. ACM (JACM) 41(1), 153–180 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  5. Battista, G.D., Eades, P., Tollis, I.G., Tamassia, R.: Graph Drawing: Algorithms for the Visualization of Graphs, 1st edn. Prentice Hall, Englewood Cliffs (1998)

    MATH  Google Scholar 

  6. Borodin, O.V.: On acyclic colorings of planar graphs. Discret. Math. 25(3), 211–236 (1979)

    Article  MathSciNet  MATH  Google Scholar 

  7. Chartrand, G., Kronk, H.V.: The point-arboricity of planar graphs. J. Lond. Math. Soc. 44, 612–616 (1969)

    Article  MathSciNet  MATH  Google Scholar 

  8. Demaine, E.D., Hajiaghayi, M., Mohar, B.: Approximation algorithms via contraction decomposition. In: Proc. of 18th SODA, pp. 278–287 (2007)

  9. Diestel, R.: Graph Theory, Graduate Texts in Mathematics, vol. 173, 3rd edn. Springer, Heidelberg (2005)

    Google Scholar 

  10. Dross, F., Montassier, M., Pinlou, A.: Large induced forests in planar graphs with girth 4 or 5. arXiv:1409.1348 (2014) (preprint)

  11. Eppstein, D.: Diameter and treewidth in minor-closed graph families. Algorithmica 27(3), 275–291 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  12. Gilbert, J.R., Hutchinson, J.P., Tarjan, R.E.: A separator theorem for graphs of bounded genus. J. Algorithm 5(3), 391–407 (1984)

    Article  MathSciNet  MATH  Google Scholar 

  13. Gritzmann, P., Mohar, B., Pach, J., Pollack, R.: Embedding a planar triangulation with vertices at specified points. Am. Math. Mon. 98(2), 165–166 (1991)

    Article  Google Scholar 

  14. Hosono, K.: Induced forests in trees and outerplanar graphs. Proc. Fac. Sci. Tokai Univ. 25, 27–29 (1990)

    MathSciNet  MATH  Google Scholar 

  15. Kawarabayashi, K., Reed, B.: A separator theorem in minor-closed classes. In: In Proc. of 51st FOCS, pp. 153–162 (2010)

  16. Le, H.: A better bound on the largest induced forests in triangle-free planar graphs (2016) (Preprint)

  17. Lipton, R., Tarjan, R.: A separator theorem for planar graphs. SIAM J. Appl. Math. 36(2), 177–189 (1979)

    Article  MathSciNet  MATH  Google Scholar 

  18. Lipton, R.J., Tarjan, R.E.: Applications of a planar separator theorem. SIAM J. Comput. 9(3), 615–627 (1980)

    Article  MathSciNet  MATH  Google Scholar 

  19. Raspaud, A., Wang, W.: On the vertex-arboricity of planar graphs. Eur. J. Comb. 29, 1064–1075 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  20. Salavatipour, M.R.: Large induced forests in triangle-free planar graphs. Graphs Comb. 22, 113–126 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  21. Shi, L., Xu, H.: Large induced forests in graphs. J. Graph Theory 85(4), 759–779 (2017)

  22. Wang, Y., Xie, Q., Yu, X.: Induced forests in bipartite planar graphs (2016) (Preprint)

  23. Whitney, H.: Non-separable and planar graphs. Trans. Am. Math. Soc. 34(2), 339–362 (1932)

    Article  MathSciNet  MATH  Google Scholar 

  24. Whitney, H.: Planar graphs. Fundam. Math. 21(1), 73–84 (1933)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

The authors thank conversations with Bigong Zheng and Kai Lei. We thank anonymous reviewers for comments that help improving the presentation of this paper.

Author information

Authors and Affiliations

  1. Oregon State University, Oregon, USA

    Glencora Borradaile & Hung Le

  2. University of California, Berkeley, USA

    Melissa Sherman-Bennett

Authors
  1. Glencora Borradaile
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Hung Le
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Melissa Sherman-Bennett
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Hung Le.

Additional information

This material is based upon work supported by the National Science Foundation under Grant Nos. CCF-1252833 and DMS-1359173. Melissa Sherman-Bennett performed this work while participating in the Summer 2015 REU program in Mathematics and Computer Science at Oregon State University.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Borradaile, G., Le, H. & Sherman-Bennett, M. Large Induced Acyclic and Outerplanar Subgraphs of 2-Outerplanar Graph. Graphs and Combinatorics 33, 1621–1634 (2017). https://doi.org/10.1007/s00373-017-1859-3

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00373-017-1859-3

Keywords

Search

Navigation