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

A Note on the Crossing Number of the Cone of a Graph

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

Abstract

The crossing number of a graph G, denoted by cr(G), is defined as the smallest possible number of edge-crossings in a drawing of G in the plane. The cone CG, obtained from G by adding a new vertex adjacent to all the vertices in G. Let \(\phi _\mathrm {s}(k)=\min \{cr(CG)-cr(G)\}\), where the minimum is taken over all the simple graphs G with crossing number k. Alfaro et al. (SIAM J Discrete Math, 32: 2080–2093, 2018) determined \(\phi _\mathrm {s}(k)\le k\) for \(k\ge 3\), and proved \(\phi _\mathrm {s}(3)=3\), \(\phi _\mathrm {s}(4)=4\) and \(\phi _\mathrm {s}(5)=5\). In this work, we improve the upper bound for \(\phi _\mathrm {s}(k)\) and our main result includes the following, slightly surprising, fact: \(\phi _\mathrm {s}(6)=5\) and \(\phi _\mathrm {s}(7)=6\).

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

References

  1. Alfaro, C.A., Arroyo, A., Derňár, M., Mohar, B.: The crossing number of the cone of a graph. SIAM J. Discrete Math. 32, 2080–2093 (2018)

    Article  MathSciNet  Google Scholar 

  2. Bondy, J.A., Murty, U.S.R.: Graph Theory, GTM 244. Springer, Berlin (2008)

    Book  Google Scholar 

  3. Bannister, M.J., Eppstein, D.: Crossing minimization for 1-page and 2-page drawings of graphs with bounded treewidth. In: Duncan, C., Symvonis, A. (eds.) Graph Drawing, pp. 210–221. Springer, Berlin (2014)

    Google Scholar 

  4. Bhatt, S.N., Leighton, F.T.: A framework for solving VLSI graph layout problems. J. Comput. Syst. Sci. 28, 300–343 (1984)

    Article  MathSciNet  Google Scholar 

  5. Chimani, M., Gutwenger, C.: Non-planar core reduction of graphs. Discrete Math. 309, 1838–1855 (2009)

    Article  MathSciNet  Google Scholar 

  6. Didimo, W., Liotta, G., Montecchiani, F.: A survey on graph drawing beyond planarity. ACM Comput. Sur. 52(1), 37 (2019). (Article 4)

    Google Scholar 

  7. de Klerk, E., Pasechnik, D.V., Salazar, G.: Improved lower bounds on book crossing numbers of complete graphs. SIAM J. Discrete Math. 27, 619–633 (2013)

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  9. Schaefer, M.: Crossing Numbers of Graphs. CRC Press, Boca Roton (2017)

    MATH  Google Scholar 

Download references

Acknowledgements

The authors are very grateful to the anonymous referees for many comments and suggestions, which are very helpful to improve the presentation of this paper.

Author information

Authors and Affiliations

  1. School of mathematics and Computational Sciences, Hunan First Normal University, Changsha, 410205, People’s Republic of China

    Zongpeng Ding

  2. Department of Mathematics, Hunan Normal University, Changsha, 410081, People’s Republic of China

    Yuanqiu Huang

Authors
  1. Zongpeng Ding
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yuanqiu Huang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Zongpeng Ding.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

The work was supported by the National Natural Science Foundation of China (No. 11871206), Hunan Provincial Natural Science Foundation of China (No. 2020JJ5095) and Scientific Research Fund of Hunan Provincial Education Department (No. 19B116).

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Ding, Z., Huang, Y. A Note on the Crossing Number of the Cone of a Graph. Graphs and Combinatorics 37, 2351–2363 (2021). https://doi.org/10.1007/s00373-021-02361-2

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00373-021-02361-2

Keywords

Mathematics Subject Classification

Search

Navigation