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

Box Representations of Embedded Graphs

  • Published:
Discrete & Computational Geometry Aims and scope Submit manuscript

Abstract

A d -box is the Cartesian product of d intervals of \(\mathbb {R}\) and a d -box representation of a graph G is a representation of G as the intersection graph of a set of d-boxes in \(\mathbb {R}^d\). It was proved by Thomassen in 1986 that every planar graph has a 3-box representation. In this paper we prove that every graph embedded in a fixed orientable surface, without short non-contractible cycles, has a 5-box representation. This directly implies that there is a function f, such that in every graph of genus g, a set of at most f(g) vertices can be removed so that the resulting graph has a 5-box representation. We show that such a function f can be made linear in g. Finally, we prove that for any proper minor-closed class \(\mathcal {F}\), there is a constant \(c(\mathcal {F})\) such that every graph of \(\mathcal {F}\) without cycles of length less than \(c(\mathcal {F})\) has a 3-box representation, which is best possible.

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

References

  1. Adiga, A., Chandran, L.S., Sivadasan, N.: Lower bounds for boxicity. Combinatorica 34(6), 631–655 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  2. Esperet, L.: Boxicity and topological invariants. Eur. J. Comb. 51, 495–499 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  3. Esperet, L., Joret, G.: Boxicity of graphs on surfaces. Graphs Comb. 29(3), 417–427 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  4. Esperet, L., Ochem, P.: On circle graphs with girth at least five. Discrete Math. 309(8), 2217–2222 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  5. Galluccio, A., Goddyn, L.A., Hell, P.: High-girth graphs avoiding a minor are nearly bipartite. J. Comb. Theory Ser. B 83(1), 1–14 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  6. Kawarabayashi, K., Mohar, B.: Star coloring and acyclic coloring of locally planar graphs. SIAM J. Discrete Math. 24, 56–71 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  7. Kawarabayashi, K., Thomassen, C.: From the plane to higher surfaces. J. Comb. Theory Ser. B 102, 852–868 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  8. Lubotzky, A., Phillips, R., Sarnak, P.: Ramanujan graphs. Combinatorica 8(3), 261–277 (1988)

    Article  MathSciNet  MATH  Google Scholar 

  9. Mohar, B., Thomassen, C.: Graphs on Surfaces. Johns Hopkins University Press, Baltimore (2001)

    MATH  Google Scholar 

  10. Nešetřil, J., Ossona de Mendez, P.: A note on circular chromatic number of graphs with large girth and similar problems. J. Graph Theory 80(4), 268–276 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  11. Roberts, F.S.: On the boxicity and cubicity of a graph. Recent Progresses in Combinatorics, pp. 301–310. Academic Press, New York (1969)

    Google Scholar 

  12. Schrijver, A.: Graphs on the torus and geometry of numbers. J. Comb. Theory Ser. B 58(1), 147–158 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  13. Thomassen, C.: Interval representations of planar graphs. J. Comb. Theory Ser. B 40, 9–20 (1986)

    Article  MathSciNet  MATH  Google Scholar 

  14. Thomassen, C.: Five-coloring maps on surfaces. J. Comb. Theory Ser. B 59, 89–105 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  15. Yu, X.: Disjoint paths, planarizing cycles, and spanning walks. Trans. Am. Math. Soc. 349(4), 1333–1358 (1997)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

The author is partially supported by ANR Project STINT (anr-13-bs02-0007), and LabEx PERSYVAL-Lab (anr-11-labx-0025).

Author information

Authors and Affiliations

  1. Laboratoire G-SCOP, CNRS, Univ. Grenoble Alpes, Grenoble, France

    Louis Esperet

Authors
  1. Louis Esperet
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Louis Esperet.

Additional information

Editor in Charge: János Pach

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Esperet, L. Box Representations of Embedded Graphs. Discrete Comput Geom 57, 590–606 (2017). https://doi.org/10.1007/s00454-016-9837-8

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00454-016-9837-8

Keywords

Search

Navigation