Skip to main content
Springer Nature Link
Log in

The Edge Rotation Graph

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

    We’re sorry, something doesn't seem to be working properly.

    Please try refreshing the page. If that doesn't work, please contact support so we can address the problem.

Abstract

Let P be a set of n points on the plane in general position, n ≥  3. The edge rotation graph \({\mathcal{E} \mathcal{R} \mathcal{G}(P,k)}\) of P is the graph whose vertices are the plane geometric graphs on P with exactly k edges, two of which are adjacent if one can be obtained from the other by an edge rotation. In this paper we study some structural properties of \({\mathcal{E} \mathcal{R} \mathcal{G}(P,k)}\) , such as its connectivity and diameter. We show that if the vertices of \({\mathcal{E} \mathcal{R} \mathcal{G}(P,k)}\) are not triangulations of P, then it is connected and has diameter O(n 2). We also show that the chromatic number of \({\mathcal{E} \mathcal{R} \mathcal{G}(P,k)}\) is O(n), and show how to compute an implicit coloring of its vertices. We also study edge rotations in edge-labelled geometric graphs.

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
€32.70 /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 includes VAT (France)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Aichholzer O., Reinhardt K.: A quadratic distance bound on sliding between crossing-free spanning trees. Comput. Geom. Theory Appl. 37(3), 155–161 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  2. Bose P., Hurtado F.: Flips in planar graphs. Comput. Geom. Theory Appl. 42(1), 60–80 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  3. Estivill-Castro V., Noy M., Urrutia J.: On the chromatic number of tree graphs. Discret. Math. 223(1–3), 363–366 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  4. Goddard W., Swart H.C.: Distances between graphs under edge operations. Discret. Math. 161, 121–132 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  5. Hernando, C., Hurtado, F., Mora, M., Rivera-Campo, E.: Grafos de árboles etiquetados y grafos de árboles geométricos etiquetados. In: Proc. X Encuentros de Geometría Computacional, pp. 13–19 (2003)

  6. Hurtado F., Noy M., Urrutia J.: Flipping edges on triangulations. Discret. Comput. Geom. 22, 333–346 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  7. Lawson C.L.: Transforming triangulations. Discret. Math. 3, 365–372 (1972)

    Article  MATH  Google Scholar 

  8. Lawson, C.L.: Software for C 1 surface interpolation. In: Mathematical Software III, pp. 161–194 (1977)

  9. Lucas J.: Untangling binary trees via rotations. Comput. J. 47(2), 259–269 (2004)

    Article  Google Scholar 

  10. Lucas J.: An improved kernel size for rotation distance in binary trees. Inf. Process. Lett. 110, 481–484 (2010)

    Article  MATH  Google Scholar 

  11. Pallo J.: An efficient upper bound of the rotation distance of binary trees. Inf. Process. Lett. 73(3-4), 87–92 (2000)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Posgrado en Ciencia e Ingeniería de la Computación, Universidad Nacional Autónoma de México, Mexico, Mexico

    Javier Cano

  2. Departamento de Matemática Aplicada II, Universidad de Sevilla, Seville, Spain

    José-Miguel Díaz-Báñez

  3. Departament de Matemàtica Aplicada IV, Universitat Politècnica de Catalunya, Barcelona, Spain

    Clemens Huemer

  4. Instituto de Matemáticas, Universidad Nacional Autónoma de México, Mexico, Mexico

    Jorge Urrutia

Authors
  1. Javier Cano
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. José-Miguel Díaz-Báñez
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Clemens Huemer
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Jorge Urrutia
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Javier Cano.

Additional information

J.M. Díaz-Báñez is partially supported by Project FEDER MEC MTM2009-08652, and the ESF EUROCORES programme EuroGIGA-ComPoSe IP04-MICINN Project EUI-EURC-2011-4306. C. Huemer partially supported by Projects MEC MTM2009-07242 and Gen. Cat. DGR 2009SGR1040 and the ESF EUROCORES programme EuroGIGA, CRP ComPoSe, MICINN Project EUI-EURC-2011-4306. J. Cano and J. Urrutia partially supported by grants CONACyT CB-2007/80268, and by Project MEC MTM2009-08652.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Cano, J., Díaz-Báñez, JM., Huemer, C. et al. The Edge Rotation Graph. Graphs and Combinatorics 29, 1207–1219 (2013). https://doi.org/10.1007/s00373-012-1201-z

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00373-012-1201-z

Keywords

Search

Navigation