Crossing and intersecting families of geometric graphs on point sets
Let S be a set of n points in the plane in general position. Two line segments connecting pairs of points of S cross if they have an interior point in common. Two vertex-disjoint geometric graphs with vertices in S cross if there are two edges, one from each graph, which cross. A set of vertex-disjo...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Springer Japan
2024
|
| Online Access: | https://hdl.handle.net/1721.1/153415 |
| _version_ | 1811081999329263616 |
|---|---|
| author | Álvarez-Rebollar, J. L. Cravioto-Lagos, J. Marín, N. Solé-Pi, O. Urrutia, J. |
| author_facet | Álvarez-Rebollar, J. L. Cravioto-Lagos, J. Marín, N. Solé-Pi, O. Urrutia, J. |
| author_sort | Álvarez-Rebollar, J. L. |
| collection | MIT |
| description | Let S be a set of n points in the plane in general position. Two line segments connecting pairs of points of S cross if they have an interior point in common. Two vertex-disjoint geometric graphs with vertices in S cross if there are two edges, one from each graph, which cross. A set of vertex-disjoint geometric graphs with vertices in S is called mutually crossing if any two of them cross. We show that there exists a constant c such that from any family of n mutually-crossing triangles, one can always obtain a family of at least
$$n^c$$
n
c
mutually-crossing 2-paths (each of which is the result of deleting an edge from one of the triangles) and provide an example that implies that c cannot be taken to be larger than 2/3. Then, for every n we determine the maximum number of crossings that a Hamiltonian cycle on a set of n points might have, and give examples achieving this bound. Next, we construct a point set whose longest perfect matching contains no crossings. We also consider edges consisting of a horizontal and a vertical line segment joining pairs of points of S, which we call elbows, and prove that in any point set S there exists a family of
$$\lfloor n/4 \rfloor $$
⌊
n
/
4
⌋
vertex-disjoint mutually-crossing elbows. Additionally, we show a point set that admits no more than n/3 mutually-crossing elbows. Finally we study intersecting families of graphs, which are not necessarily vertex disjoint. A set of edge-disjoint graphs with vertices in S is called an intersecting family if for any two graphs in the set we can choose an edge in each of them such that they cross. We prove a conjecture by Lara and Rubio-Montiel (Acta Math Hung 15(2):301–311, 2019,
https://doi.org/10.1007/s10474-018-0880-1
), namely, that any set S of n points in general position admits a family of intersecting triangles with a quadratic number of elements. For points in convex position we prove that any set of 3n points in convex position contains a family with at least
$$n^2$$
n
2
intersecting triangles. |
| first_indexed | 2024-09-23T11:55:46Z |
| format | Article |
| id | mit-1721.1/153415 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T11:55:46Z |
| publishDate | 2024 |
| publisher | Springer Japan |
| record_format | dspace |
| spelling | mit-1721.1/1534152024-01-30T03:37:30Z Crossing and intersecting families of geometric graphs on point sets Álvarez-Rebollar, J. L. Cravioto-Lagos, J. Marín, N. Solé-Pi, O. Urrutia, J. Let S be a set of n points in the plane in general position. Two line segments connecting pairs of points of S cross if they have an interior point in common. Two vertex-disjoint geometric graphs with vertices in S cross if there are two edges, one from each graph, which cross. A set of vertex-disjoint geometric graphs with vertices in S is called mutually crossing if any two of them cross. We show that there exists a constant c such that from any family of n mutually-crossing triangles, one can always obtain a family of at least $$n^c$$ n c mutually-crossing 2-paths (each of which is the result of deleting an edge from one of the triangles) and provide an example that implies that c cannot be taken to be larger than 2/3. Then, for every n we determine the maximum number of crossings that a Hamiltonian cycle on a set of n points might have, and give examples achieving this bound. Next, we construct a point set whose longest perfect matching contains no crossings. We also consider edges consisting of a horizontal and a vertical line segment joining pairs of points of S, which we call elbows, and prove that in any point set S there exists a family of $$\lfloor n/4 \rfloor $$ ⌊ n / 4 ⌋ vertex-disjoint mutually-crossing elbows. Additionally, we show a point set that admits no more than n/3 mutually-crossing elbows. Finally we study intersecting families of graphs, which are not necessarily vertex disjoint. A set of edge-disjoint graphs with vertices in S is called an intersecting family if for any two graphs in the set we can choose an edge in each of them such that they cross. We prove a conjecture by Lara and Rubio-Montiel (Acta Math Hung 15(2):301–311, 2019, https://doi.org/10.1007/s10474-018-0880-1 ), namely, that any set S of n points in general position admits a family of intersecting triangles with a quadratic number of elements. For points in convex position we prove that any set of 3n points in convex position contains a family with at least $$n^2$$ n 2 intersecting triangles. 2024-01-29T19:37:06Z 2024-01-29T19:37:06Z 2024-01-25 2024-01-28T04:21:26Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/153415 Graphs and Combinatorics. 2024 Jan 25;40(1):17 PUBLISHER_CC en https://doi.org/10.1007/s00373-023-02734-9 Creative Commons Attribution https://creativecommons.org/licenses/by/4.0/ The Author(s) application/pdf Springer Japan Springer Japan |
| spellingShingle | Álvarez-Rebollar, J. L. Cravioto-Lagos, J. Marín, N. Solé-Pi, O. Urrutia, J. Crossing and intersecting families of geometric graphs on point sets |
| title | Crossing and intersecting families of geometric graphs on point sets |
| title_full | Crossing and intersecting families of geometric graphs on point sets |
| title_fullStr | Crossing and intersecting families of geometric graphs on point sets |
| title_full_unstemmed | Crossing and intersecting families of geometric graphs on point sets |
| title_short | Crossing and intersecting families of geometric graphs on point sets |
| title_sort | crossing and intersecting families of geometric graphs on point sets |
| url | https://hdl.handle.net/1721.1/153415 |
| work_keys_str_mv | AT alvarezrebollarjl crossingandintersectingfamiliesofgeometricgraphsonpointsets AT craviotolagosj crossingandintersectingfamiliesofgeometricgraphsonpointsets AT marinn crossingandintersectingfamiliesofgeometricgraphsonpointsets AT solepio crossingandintersectingfamiliesofgeometricgraphsonpointsets AT urrutiaj crossingandintersectingfamiliesofgeometricgraphsonpointsets |