A new lower bound on the maximum number of plane graphs using production matrices

被引：3
|
作者：
Huemer, Clemens [1 ]
Pilz, Alexander [2 ]
Silveira, Rodrigo, I [1 ]
机构：
[1] Univ Politecn Cataluna, Dept Matemat, Barcelona, Spain
[2] Graz Univ Technol, Inst Software Technol, Graz, Austria
来源：
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS | 2019年 / 84卷
基金：
奥地利科学基金会;
关键词：
Plane graphs; Graphs counting; Production matrix; Lower bounds; TRIANGULATIONS; TREE;
D O I：
10.1016/j.comgeo.2019.07.005
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
We use the concept of production matrices to show that there exist sets of n points in the plane that admit Omega(42.11(n)) crossing-free geometric graphs. This improves the previously best known bound of Omega(41.18(n)) by Aichholzer et al. (2007). (C) 2019 Elsevier B.V. All rights reserved.
引用
收藏
页码：36 / 49
页数：14
相关论文
共 50 条
  • [1] A new lower bound on the independence number of graphs
    Angel, Eric
    Campigotto, Romain
    Laforest, Christian
    DISCRETE APPLIED MATHEMATICS, 2013, 161 (06) : 847 - 852
  • [2] A LOWER BOUND ON THE k-CONVERSION NUMBER OF GRAPHS OF MAXIMUM DEGREE k
    Mynhardt, Christina M.
    Wodlinger, Jane L.
    TRANSACTIONS ON COMBINATORICS, 2019, 8 (03) : 1 - 12
  • [3] An Improvement of the Lower Bound on the Maximum Number of Halving Lines for Sets in the Plane with an Odd Number of Points
    Rodrigo, Javier
    Lopez, Marilo
    Magistrali, Danilo
    Alonso, Estrella
    AXIOMS, 2025, 14 (01)
  • [4] A NEW LOWER BOUND ON THE NUMBER OF PERFECT MATCHINGS IN CUBIC GRAPHS
    Kral', Daniel
    Sereni, Jean-Sebastien
    Stiebitz, Michael
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2009, 23 (03) : 1465 - 1483
  • [5] A New Lower Bound for the Eternal Vertex Cover Number of Graphs
    Babu, Jasine
    Prabhakaran, Veena
    COMPUTING AND COMBINATORICS (COCOON 2020), 2020, 12273 : 27 - 39
  • [6] A NEW LOWER BOUND FOR THE NUMBER OF ROOTS OF MAPS BETWEEN GRAPHS
    Zhao, Xuezhi
    TOPOLOGICAL METHODS IN NONLINEAR ANALYSIS, 2009, 33 (01) : 17 - 29
  • [7] A new lower bound for the eternal vertex cover number of graphs
    Jasine Babu
    Veena Prabhakaran
    Journal of Combinatorial Optimization, 2022, 44 : 2482 - 2498
  • [8] A new lower bound for the eternal vertex cover number of graphs
    Babu, Jasine
    Prabhakaran, Veena
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2022, 44 (04) : 2482 - 2498
  • [9] New Lower Bound on the Number of Perfect Matchings in Fullerene Graphs
    Heping Zhang
    Fuji Zhang
    Journal of Mathematical Chemistry, 2001, 30 : 343 - 347
  • [10] New lower bound on the number of perfect matchings in fullerene graphs
    Zhang, HP
    Zhang, FJ
    JOURNAL OF MATHEMATICAL CHEMISTRY, 2001, 30 (03) : 343 - 347
12345