[go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

On the Planar Split Thickness of Graphs

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

Motivated by applications in graph drawing and information visualization, we examine the planar split thickness of a graph, that is, the smallest k such that the graph is k-splittable into a planar graph. A k-split operation substitutes a vertex v by at most k new vertices such that each neighbor of v is connected to at least one of the new vertices. We first examine the planar split thickness of complete graphs, complete bipartite graphs, multipartite graphs, bounded degree graphs, and genus-1 graphs. We then prove that it is NP-hard to recognize graphs that are 2-splittable into a planar graph, and show that one can approximate the planar split thickness of a graph within a constant factor. If the treewidth is bounded, then we can even verify k-splittability in linear time, for a constant k.

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. A graph G is k-degenerate if every subgraph of G contains a vertex of degree at most k.

References

  1. Beineke, L.W., Harary, F.: The thickness of the complete graph. Can. J. Math. 14(17), 850–859 (1965)

    Article  MathSciNet  MATH  Google Scholar 

  2. Beineke, L.W., Harary, F.: A simplified NP-complete satisfiability problem. Craig A. Tovey 8, 85–89 (1984)

    MathSciNet  Google Scholar 

  3. Borradaile, G., Eppstein, D., Zhu, P.: Planar induced subgraphs of sparse graphs. In: Duncan, C.A., Symvonis, A. (eds.) Proceedings of the 22nd International Symposium on Graph Drawing (GD). Lecture Notes Comput. Sci., vol. 8871, pp. 1–12. Springer (2014)

  4. Chimani, M., Derka, M., Hliněnỳ, P., Klusáček, M.: How not to characterize planar-emulable graphs. Adv. Appl. Math. 50(1), 46–68 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  5. Courcelle, B.: The monadic second-order logic of graphs. I. recognizable sets of finite graphs. Inf. Comput. 85(1), 12–75 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  6. Courcelle, B.: On the expression of graph properties in some fragments of monadic second-order logic. In: Immerman, N., Kolaitis, P.G. (eds.) Proceedings of the DIMACS Workshop on Descriptive Complexity and Finite Models. DIMACS Ser. Discrete Math. Theor. Comput. Sci., vol. 31, pp. 33–62. American Math. Soc. (1996)

  7. de Mendonça Neto, C.F.X., Schaffer, K., Xavier, E.F., Stolfi, J., Faria, L., de Figueiredo, C.M.H.: The splitting number and skewness of \({C}_n\times {C}_m\). Ars Comb. 63 (2002)

  8. Dujmovic, V., Wood, D.R.: Graph treewidth and geometric thickness parameters. Discret. Comput. Geom. 37(4), 641–670 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  9. Duncan, C.A., Eppstein, D., Kobourov, S.G.: The geometric thickness of low degree graphs. In: Snoeyink, J., Boissonnat, J. (eds.) Proceedings of the 20th ACM Symposium on Computational Geometry (SoCG), pp. 340–346. ACM (2004)

  10. Eppstein, D., Kindermann, P., Kobourov, S.G., Liotta, G., Lubiw, A., Maignan, A., Mondal, D., Vosoughpour, H., Whitesides, S., Wismath, S.K.: On the planar split thickness of graphs. In: Kranakis, E., Navarro, G., Chávez, E. (eds.) Proceedings of the 12th Latin American Theoretical Informatics Symposium (LATIN). Lecture Notes Comput. Sci., vol. 9644, pp. 403–415. Springer (2016)

  11. Faria, L., de Figueiredo, C.M.H., de Mendonça Neto, C.F.X.: Splitting number is NP-complete. Discret. Appl. Math. 108(1–2), 65–83 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  12. Fellows, M.R.: Encoding graphs in graphs. Ph.D. thesis, Univ. of California, San Diego (1985)

  13. Gabow, H.N., Westermann, H.H.: Forests, frames, and games: algorithms for matroid sums and applications. Algorithmica 7(1), 465–497 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  14. Gansner, E.R., Hu, Y., Kobourov, S.G.: Gmap: Visualizing graphs and clusters as maps. In: Proceedings of the IEEE Pacific Visualization Symposium (PacificVis), pp. 201–208 (2010)

  15. Hartsfield, N.: The toroidal splitting number of the complete graph \({K}_n\). Discrete Math. (1986)

  16. Hartsfield, N.: The splitting number of the complete graph in the projective plane. Graphs Comb. 3(1), 349–356 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  17. Hartsfield, N., Jackson, B., Ringel, G.: The splitting number of the complete graph. Graphs Comb. 1(1), 311–329 (1985)

    Article  MathSciNet  MATH  Google Scholar 

  18. Heawood, P.J.: Map colour theorem. Q. J. Math. 24, 332–338 (1890)

    MATH  Google Scholar 

  19. Huneke, J.P.: A conjecture in topological graph theory. In: Robertson, N., Seymour, P.D. (eds.) Graph Structure Theory, Proceedings of a AMS-IMS-SIAM Joint Summer Research Conference on Graph Minors held June 22 to July 5, 1991, at the University of Washington, Seattle. Contemp. Math., vol. 147, pp. 387–389. American Math. Soc. (1991)

  20. Hutchinson, J.P.: Coloring ordinary maps, maps of empires, and maps of the moon. Math. Mag. 66(4), 211–226 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  21. Jackson, B., Ringel, G.: The splitting number of complete bipartite graphs. Arch. Math. 42, 178–184 (1984)

    Article  MathSciNet  MATH  Google Scholar 

  22. Jackson, B., Ringel, G.: Splittings of graphs on surfaces. In: Harary, F., Maybee, J.S. (eds.) Proceedings of the 1st Colorado Symposium on Graph Theory, pp. 203–219 (1985)

  23. Knauer, K., Ueckerdt, T.: Three ways to cover a graph. Discret. Math. 339(2), 745–758 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  24. Kratochvíl, J., Lubiw, A., Nesetril, J.: Noncrossing subgraphs in topological layouts. SIAM J. Discret. Math. 4(2), 223–244 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  25. Liebers, A.: Planarizing graphs—a survey and annotated bibliography. J. Graph Algorithms Appl. 5(1), 1–74 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  26. Morgenstern, M.: Existence and explicit constructions of \(q+1\) regular Ramanujan graphs for every prime power \(q\). J. Comb. Theory Ser. B 62(1), 44–62 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  27. Nash-Williams, C.S.J.A.: Decomposition of finite graphs into forests. J. Lond. Math. Soc. 39(1), 12 (1964)

    Article  MathSciNet  MATH  Google Scholar 

  28. Negami, S.: Enumeration of projective-planar embeddings of graphs. Discret. Math. 63(3), 299–306 (1986)

    Article  MathSciNet  MATH  Google Scholar 

  29. Negami, S.: The spherical genus and virtually planar graphs. Discret. Math. 70(2), 159–168 (1988)

    Article  MathSciNet  MATH  Google Scholar 

  30. Picard, J.C., Queyranne, M.: A network flow solution to some nonlinear 0–1 programming problems, with applications to graph theory. Networks 12(2), 141–159 (1982)

    Article  MathSciNet  MATH  Google Scholar 

  31. Riche, N.H., Dwyer, T.: Untangling euler diagrams. Proc. IEEE Trans. Vis. Comput. Graph. 16(6), 1090–1099 (2010)

    Article  Google Scholar 

  32. Ringel, G., Jackson, B.: Solution of Heawood’s empire problem in the plane. J. Reine Angew. Math. 347, 146–153 (1984)

    MathSciNet  MATH  Google Scholar 

  33. Scheinerman, E.R., West, D.B.: The interval number of a planar graph: three intervals suffice. J. Comb. Theory Ser. B 35(3), 224–239 (1983)

    Article  MathSciNet  MATH  Google Scholar 

  34. Thomason, A.: The extremal function for complete minors. J. Comb. Theory Ser. B 81(2), 318–338 (2001)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

Most of the results of this paper were obtained at the McGill-INRIA-UVictoria Workshop on Computational Geometry, Barbados, February 2015. We would like to thank the organizers of these events, as well as many participants for fruitful discussions and suggestions. The first, fourth, sixth and eighth authors acknowledge the support from NSF Grant 1228639, 2012C4E3KT PRIN Italian National Research Project, PEPS egalite project and NSERC, respectively.

Author information

Authors and Affiliations

  1. University of California, Irvine, CA, USA

    David Eppstein

  2. FernUniversität Hagen, Hagen, Germany

    Philipp Kindermann

  3. University of Arizona, Tucson, AZ, USA

    Stephen Kobourov

  4. Università degli Studi di Perugia, Perugia, Italy

    Giuseppe Liotta

  5. University of Waterloo, Waterloo, Canada

    Anna Lubiw, Debajyoti Mondal & Hamideh Vosoughpour

  6. Universit. Grenoble Alpes, Grenoble, France

    Aude Maignan

  7. University of Victoria, Victoria, Canada

    Sue Whitesides

  8. University of Lethbridge, Lethbridge, Canada

    Stephen Wismath

Authors
  1. David Eppstein
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Philipp Kindermann
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Stephen Kobourov
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Giuseppe Liotta
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Anna Lubiw
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Aude Maignan
    View author publications

    You can also search for this author in PubMed Google Scholar

  7. Debajyoti Mondal
    View author publications

    You can also search for this author in PubMed Google Scholar

  8. Hamideh Vosoughpour
    View author publications

    You can also search for this author in PubMed Google Scholar

  9. Sue Whitesides
    View author publications

    You can also search for this author in PubMed Google Scholar

  10. Stephen Wismath
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Philipp Kindermann.

Additional information

A preliminary version of this work appeared at the 12th Latin American Theoretical Informatics Symposium (LATIN’16) [10].

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Eppstein, D., Kindermann, P., Kobourov, S. et al. On the Planar Split Thickness of Graphs. Algorithmica 80, 977–994 (2018). https://doi.org/10.1007/s00453-017-0328-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-017-0328-y

Keywords

Search

Navigation