An Improvement of the Lower Bound on the Minimum Number of ≤<i>k</i>-Edges
In this paper, we improve the lower bound on the minimum number of <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo> </mo><mo>≤</mo><mi>k</mi></mrow></semant...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2021-03-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/9/5/525 |
| _version_ | 1797415460432510976 |
|---|---|
| author | Javier Rodrigo Susana Merchán Danilo Magistrali Mariló López |
| author_facet | Javier Rodrigo Susana Merchán Danilo Magistrali Mariló López |
| author_sort | Javier Rodrigo |
| collection | DOAJ |
| description | In this paper, we improve the lower bound on the minimum number of <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo> </mo><mo>≤</mo><mi>k</mi></mrow></semantics></math></inline-formula>-edges in sets of <i>n</i> points in general position in the plane when <i>k</i> is close to <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mfrac><mi>n</mi><mn>2</mn></mfrac></semantics></math></inline-formula>. As a consequence, we improve the current best lower bound of the rectilinear crossing number of the complete graph <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>K</mi><mi>n</mi></msub></semantics></math></inline-formula> for some values of <i>n</i>. |
| first_indexed | 2024-03-09T05:47:56Z |
| format | Article |
| id | doaj.art-2f78f3c2b6304f8fbb7d2681f8f8eb78 |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-03-09T05:47:56Z |
| publishDate | 2021-03-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-2f78f3c2b6304f8fbb7d2681f8f8eb782023-12-03T12:19:12ZengMDPI AGMathematics2227-73902021-03-019552510.3390/math9050525An Improvement of the Lower Bound on the Minimum Number of ≤<i>k</i>-EdgesJavier Rodrigo0Susana Merchán1Danilo Magistrali2Mariló López3Departamento de Matemática Aplicada, E.T.S.I. Universidad Pontificia Comillas, Alberto Aguilera 25, 28015 Madrid, SpainDepartamento de Matemática e Informática Aplicadas a las Ingenierías Civil y Naval, Escuela de Caminos, Canales y Puertos, Universidad Politécnica de Madrid, Profesor Aranguren, 3, 28040 Madrid, SpainDepartamento de Matemática Aplicada, E.T.S.I. Universidad Pontificia Comillas, Alberto Aguilera 25, 28015 Madrid, SpainDepartamento de Matemática e Informática Aplicadas a las Ingenierías Civil y Naval, Escuela de Caminos, Canales y Puertos, Universidad Politécnica de Madrid, Profesor Aranguren, 3, 28040 Madrid, SpainIn this paper, we improve the lower bound on the minimum number of <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo> </mo><mo>≤</mo><mi>k</mi></mrow></semantics></math></inline-formula>-edges in sets of <i>n</i> points in general position in the plane when <i>k</i> is close to <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mfrac><mi>n</mi><mn>2</mn></mfrac></semantics></math></inline-formula>. As a consequence, we improve the current best lower bound of the rectilinear crossing number of the complete graph <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>K</mi><mi>n</mi></msub></semantics></math></inline-formula> for some values of <i>n</i>.https://www.mdpi.com/2227-7390/9/5/525combinatorial geometry≤k-edgesrectilinear crossing numberoptimizationcomplete graphs |
| spellingShingle | Javier Rodrigo Susana Merchán Danilo Magistrali Mariló López An Improvement of the Lower Bound on the Minimum Number of ≤<i>k</i>-Edges Mathematics combinatorial geometry ≤k-edges rectilinear crossing number optimization complete graphs |
| title | An Improvement of the Lower Bound on the Minimum Number of ≤<i>k</i>-Edges |
| title_full | An Improvement of the Lower Bound on the Minimum Number of ≤<i>k</i>-Edges |
| title_fullStr | An Improvement of the Lower Bound on the Minimum Number of ≤<i>k</i>-Edges |
| title_full_unstemmed | An Improvement of the Lower Bound on the Minimum Number of ≤<i>k</i>-Edges |
| title_short | An Improvement of the Lower Bound on the Minimum Number of ≤<i>k</i>-Edges |
| title_sort | improvement of the lower bound on the minimum number of ≤ i k i edges |
| topic | combinatorial geometry ≤k-edges rectilinear crossing number optimization complete graphs |
| url | https://www.mdpi.com/2227-7390/9/5/525 |
| work_keys_str_mv | AT javierrodrigo animprovementofthelowerboundontheminimumnumberofikiedges AT susanamerchan animprovementofthelowerboundontheminimumnumberofikiedges AT danilomagistrali animprovementofthelowerboundontheminimumnumberofikiedges AT marilolopez animprovementofthelowerboundontheminimumnumberofikiedges AT javierrodrigo improvementofthelowerboundontheminimumnumberofikiedges AT susanamerchan improvementofthelowerboundontheminimumnumberofikiedges AT danilomagistrali improvementofthelowerboundontheminimumnumberofikiedges AT marilolopez improvementofthelowerboundontheminimumnumberofikiedges |