On grids in topological graphs
A topological graph G is a graph drawn in the plane with vertices represented by points and edges represented by continuous arcs connecting the vertices. If every edge is drawn as a straight-line segment, then G is called a geometric graph. A k-grid in a topological graph is a pair of subsets of the...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Elsevier
2017
|
| Online Access: | http://hdl.handle.net/1721.1/110635 |
| _version_ | 1811091473424187392 |
|---|---|
| author | Ackerman, Eyal Fox, Jacob Pach, János Suk, Andrew |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Ackerman, Eyal Fox, Jacob Pach, János Suk, Andrew |
| author_sort | Ackerman, Eyal |
| collection | MIT |
| description | A topological graph G is a graph drawn in the plane with vertices represented by points and edges represented by continuous arcs connecting the vertices. If every edge is drawn as a straight-line segment, then G is called a geometric graph. A k-grid in a topological graph is a pair of subsets of the edge set, each of size k, such that every edge in one subset crosses every edge in the other subset. It is known that every n-vertex topological graph with no k-grid has O[subscript k](n) edges. We conjecture that the number of edges of every n-vertex topological graph with no k-grid such that all of its 2k edges have distinct endpoints is O[subscript k(n). This conjecture is shown to be true apart from an iterated logarithmic factor ⁎. A k-grid is natural if its edges have distinct endpoints, and the arcs representing each of its edge subsets are pairwise disjoint. We also conjecture that every n-vertex geometric graph with no natural k-grid has edges, but we can establish only an O[subscript k](nlog[superscript 2] n) upper bound. We verify the above conjectures in several special cases. |
| first_indexed | 2024-09-23T15:02:59Z |
| format | Article |
| id | mit-1721.1/110635 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T15:02:59Z |
| publishDate | 2017 |
| publisher | Elsevier |
| record_format | dspace |
| spelling | mit-1721.1/1106352022-09-29T12:19:09Z On grids in topological graphs Ackerman, Eyal Fox, Jacob Pach, János Suk, Andrew Massachusetts Institute of Technology. Department of Mathematics Fox, Jacob Suk, Andrew A topological graph G is a graph drawn in the plane with vertices represented by points and edges represented by continuous arcs connecting the vertices. If every edge is drawn as a straight-line segment, then G is called a geometric graph. A k-grid in a topological graph is a pair of subsets of the edge set, each of size k, such that every edge in one subset crosses every edge in the other subset. It is known that every n-vertex topological graph with no k-grid has O[subscript k](n) edges. We conjecture that the number of edges of every n-vertex topological graph with no k-grid such that all of its 2k edges have distinct endpoints is O[subscript k(n). This conjecture is shown to be true apart from an iterated logarithmic factor ⁎. A k-grid is natural if its edges have distinct endpoints, and the arcs representing each of its edge subsets are pairwise disjoint. We also conjecture that every n-vertex geometric graph with no natural k-grid has edges, but we can establish only an O[subscript k](nlog[superscript 2] n) upper bound. We verify the above conjectures in several special cases. 2017-07-11T17:22:57Z 2017-07-11T17:22:57Z 2014-02 2009-12 Article http://purl.org/eprint/type/JournalArticle 09257721 http://hdl.handle.net/1721.1/110635 Ackerman, Eyal, Jacob Fox, János Pach, and Andrew Suk. “On Grids in Topological Graphs.” Computational Geometry 47, no. 7 (August 2014): 710–723. en_US http://dx.doi.org/10.1016/j.comgeo.2014.02.003 Computational Geometry Creative Commons Attribution-NonCommercial-NoDerivs License http://creativecommons.org/licenses/by-nc-nd/4.0/ application/pdf Elsevier Other univ. web domain |
| spellingShingle | Ackerman, Eyal Fox, Jacob Pach, János Suk, Andrew On grids in topological graphs |
| title | On grids in topological graphs |
| title_full | On grids in topological graphs |
| title_fullStr | On grids in topological graphs |
| title_full_unstemmed | On grids in topological graphs |
| title_short | On grids in topological graphs |
| title_sort | on grids in topological graphs |
| url | http://hdl.handle.net/1721.1/110635 |
| work_keys_str_mv | AT ackermaneyal ongridsintopologicalgraphs AT foxjacob ongridsintopologicalgraphs AT pachjanos ongridsintopologicalgraphs AT sukandrew ongridsintopologicalgraphs |