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

Geometric Biplane Graphs II: Graph Augmentation

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

Abstract

We study biplane graphs drawn on a finite point set \(S\) in the plane in general position. This is the family of geometric graphs whose vertex set is \(S\) and which can be decomposed into two plane graphs. We show that every sufficiently large point set admits a 5-connected biplane graph and that there are arbitrarily large point sets that do not admit any 6-connected biplane graph. Furthermore, we show that every plane graph (other than a wheel or a fan) can be augmented into a 4-connected biplane graph. However, there are arbitrarily large plane graphs that cannot be augmented to a 5-connected biplane graph by adding pairwise noncrossing edges.

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
Fig. 7
Fig. 8
Fig. 9

Similar content being viewed by others

Notes

  1. The companion paper [18] contains a larger introduction to the concept of biplane graphs, comparing it with other related concepts such as the geometric thickness and others. Ideally, both papers will appear in the same journal issue. Preliminary versions of both papers have been presented at the Mexican Conference on Discrete Mathematics and Computational Geometry (Oaxaca, 2013) [18, 19]. To avoid repetition, a complete introduction is presented in the companion paper, and here we include only a brief self-contained introduction.

References

  1. Abellanas, M., García, A., Hurtado, F., Tejel, J., Urrutia, J.: Augmenting the connectivity of geometric graphs. Comput. Geom. Theory Appl. 40(3), 220–230 (2008)

    Article  MATH  Google Scholar 

  2. Al-Jubeh, M., Barequet, G., Ishaque, M., Souvaine, D.L., Tóth, C.D., Winslow, A.: Constrained tri-connected planar straight line graphs. In: Pach, J. (ed.) Thirty Essays on Geometric Graph Theory, pp. 49–70. Springer, New York (2013)

    Chapter  Google Scholar 

  3. Al-Jubeh, M., Ishaque, M., Rédei, K., Souvaine, D.L., Tóth, C.D., Valtr, P.: Augmenting the edge connectivity of planar straight line graphs to three. Algorithmica 61(4), 971–999 (2011)

    Article  MATH  MathSciNet  Google Scholar 

  4. Barnette, D.: On generating planar graphs. Discrete Math. 7, 199–208 (1974)

    Article  MATH  MathSciNet  Google Scholar 

  5. Bender, M.A., Farach-Colton, M.: The LCA problem revisited. In: Proc. LATIN 2000, LNCS, vol. 1776, pp. 88–94. Springer, Berlin (2000)

  6. Bernhart, F., Kainen, P.C.: The book thickness of a graph. J. Combin. Theory Ser. B 27, 320–331 (1979)

    Article  MATH  MathSciNet  Google Scholar 

  7. Brinkmann, G., McKay, B.D.: Construction of planar triangulations with minimum degree 5. Discrete Math. 301(2–3), 147–163 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  8. Butler, J.W.: A generation procedure for the simple 3-polytopes with cyclically 5-connected graphs. Can. J. Math. XXV I(3), 686–708 (1974)

    Article  Google Scholar 

  9. Chvátal, V.: Hamiltonian cycles. In: Lawler, E.L., et al. (eds.) The Traveling Salesman Problem, pp. 403–429. Wiley, Chichester (1985)

    Google Scholar 

  10. Dey, T.K., Dillencourt, M.B., Ghosh, S.K., Cahill, J.M.: Triangulating with high connectivity. Comput. Geom. Theory Appl. 8, 39–56 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  11. Diwan, A.A., Ghosh, S.K., Roy, B.: Four-connected triangulations of planar point sets (manuscript, arXiv:1310.1726) (2013)

  12. Dobrev, S., Kranakis, E., Krizanc, D., Morales Ponce, O., Stacho, L.: Approximating the edge length of 2-edge connected planar geometric graphs on a set of points. In: Proc. LATIN 2012, LNCS 7256, pp. 255–266. Springer, Berlin (2012)

  13. Eswaran, K.P., Tarjan, R.E.: Augmentation problems. SIAM J. Comput. 5, 653–665 (1976)

    Article  MATH  MathSciNet  Google Scholar 

  14. Fáry, I.: On straight-line representation of planar graphs. Acta Sci. Math. (Szeged) 11, 229–233 (1948)

    MATH  Google Scholar 

  15. García, A., Huemer, C., Hurtado, F., Tejel, J., Valtr, P.: On triconnected and cubic plane graphs on given point sets. Comput. Geom. Theory Appl. 42(9), 913–922 (2009)

    Article  MATH  Google Scholar 

  16. García, A., Huemer, C., Tejel, J., Valtr, P.: On 4-connected geometric graphs. In: Proc. XV Spanish Meeting on Computational Geometry, Sevilla, pp. 123–126 (2013)

  17. García, A., Huemer, C., Tejel, J., Valtr, P.: Personal communication (manuscript in preparation) (2014)

  18. García, A., Hurtado, F., Korman, M., Matos, I., Saumell, M., Silveira, R.I., Tejel, J., Tóth, C.D.: Geometric biplane graphs I: Maximal graphs. Extended abstract. In: Proc. Mexican Conference on Discrete Mathematics and Computational Geometry, Oaxaca, pp. 123–134 (2013)

  19. García, A., Hurtado, F., Korman, M., Matos, I., Saumell, M., Silveira, R.I., Tejel, J., Tóth, C.D.: Geometric biplane graphs II: graph augmentation. Extended abstract. In: Proc. Mexican Conference on Discrete Mathematics and Computational Geometry, Oaxaca, pp. 223–234 (2013)

  20. Harel, D., Tarjan, R.E.: Fast algorithms for finding nearest common ancestors. SIAM J. Comput. 13(2), 338–355 (1984)

    Article  MATH  MathSciNet  Google Scholar 

  21. Hershberger, J., Suri, S.: Applications of a semi-dynamic convex hull algorithm. BIT 32(2), 249–267 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  22. Hurtado, F., Tóth, C.D.: Plane geometric graph augmentation: a generic perspective. In: Pach, J. (ed.) Thirty Essays on Geometric Graph Theory, pp. 327–354. Springer, New York (2013)

  23. Hutchinson, J.P., Shermer, T.C., Vince, A.: On representations of some thickness-two graphs. Comput. Geom. Theory Appl. 13, 161–171 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  24. Kranakis, E., Krizanc, D., Morales Ponce, O., Stacho, L.: Bounded length, 2-edge augmantation of geometric planar graphs. Discrete Math. Algebra Appl. 4, 385–397 (2012)

  25. Rutter, I., Wolff, A.: Augmenting the connectivity of planar and geometric graphs. J. Graph Algorithms Appl. 16(2), 599–628 (2012)

    Article  MATH  MathSciNet  Google Scholar 

  26. Schieber, B., Vishkin, U.: On finding lowest common ancestors: simplification and parallelization. SIAM J. Comput. 17(6), 1253–1262 (1988)

    Article  MATH  MathSciNet  Google Scholar 

  27. Tóth, C.D.: Connectivity augmentation in planar straight line graphs. Eur. J. Combin. 33(3), 408–425 (2012)

    Article  MATH  Google Scholar 

  28. Tóth, G., Valtr, P.: The Erdős-Szekeres theorem: upper bounds and related results. In: Combinatorial and Computational Geometry, vol. 52. MSRI Publications, pp. 557–568 (2005)

  29. Tutte, W.T.: A theorem on planar graphs. Trans. Am. Math. Soc. 82, 99–116 (1956)

    Article  MATH  MathSciNet  Google Scholar 

  30. Wigderson, A.: The complexity of the Hamiltonian circuit problem for maximal planar graphs. Technical Report 298, Princeton University, EECS Department (1982)

Download references

Acknowledgments

A. G., F. H., M. K., R.I. S. and J. T. were partially supported by ESF EUROCORES programme EuroGIGA, CRP ComPoSe: grant EUI-EURC-2011-4306, and by project MINECO MTM2012-30951/FEDER. F. H., and R.I. S. were also supported by project Gen. Cat. DGR 2009SGR1040. A. G. and J. T. were also supported by project E58(ESF)-DGA. M. K. was supported by the Secretary for Universities and Research of the Ministry of Economy and Knowledge of the Government of Catalonia and the European Union. I. M. was supported by FEDER funds through COMPETE-Operational Programme Factors of Competitiveness, CIDMA and FCT within project PEst-C/MAT/UI4106/2011 with COMPETE number FCOMP-01-0124-FEDER-022690. M. S. was supported by the project NEXLIZ - CZ.1.07/2.3.00/30.0038, which is co-financed by the European Social Fund and the state budget of the Czech Republic, and by ESF EuroGIGA project ComPoSe as F.R.S.-FNRS-EUROGIGA NR 13604. R. S. was funded by Portuguese funds through CIDMA (Center for Research and Development in Mathematics and Applications) and FCT (Fundação para a Ciência e a Tecnologia), within project PEst-OE/MAT/UI4106/2014, and by FCT grant SFRH/BPD/88455/2012. C. T. was supported in part by NSERC (RGPIN 35586) and NSF (CCF-0830734).

Author information

Authors and Affiliations

  1. Departamento de Métodos Estadísticos, IUMA, Universidad de Zaragoza, Zaragoza, Spain

    Alfredo García & Javier Tejel

  2. Departament de Matemàtica Aplicada II, UPC, Barcelona, Spain

    Ferran Hurtado & Rodrigo I. Silveira

  3. Erato Kawarabayashi Large Graph Project, JST, National Institute of Informatics (NII), Tokyo, Japan

    Matias Korman

  4. Departamento de Matemática and CIDMA, Universidade de Aveiro, Aveiro, Portugal

    Inês Matos

  5. Department of Mathematics and European Centre of Excellence NTIS (New Technologies for the Information Society), University of West Bohemia, Pilsen, Czech Republic

    Maria Saumell

  6. Department of Mathematics, California State University Northridge, Los Angeles, USA

    Csaba D. Tóth

Authors
  1. Alfredo García
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ferran Hurtado
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Matias Korman
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Inês Matos
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Maria Saumell
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Rodrigo I. Silveira
    View author publications

    You can also search for this author in PubMed Google Scholar

  7. Javier Tejel
    View author publications

    You can also search for this author in PubMed Google Scholar

  8. Csaba D. Tóth
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Javier Tejel.

Additional information

A preliminary version of this paper has been presented at the Mexican Conference on Discrete Mathematics and Computational Geometry, Oaxaca, México, November 2013 [19].

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

García, A., Hurtado, F., Korman, M. et al. Geometric Biplane Graphs II: Graph Augmentation. Graphs and Combinatorics 31, 427–452 (2015). https://doi.org/10.1007/s00373-015-1547-0

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00373-015-1547-0

Keywords

Search

Navigation