Eyal Ackerman
ABSTRACT
A topological graph is a graph drawn in the plane with vertices represented by points and edges as arcs connecting its vertices. 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 for a fixed constant k, every n-vertex topological graph with no k-grid has O(n) edges.
We conjecture that this statement remains true (1) for topological graphs in which only k-grids consisting of 2k vertex-disjoint edges are forbidden, and (2) for graphs drawn by straight-line edges, with no k-element sets of edges such that every edge in the first set crosses every edge in the other set and each pair of edges within the same set is disjoint.
These conjectures are shown to be true apart from log* n and log2 n factors, respectively. We also settle the conjectures for some special cases.
- P. K. Agarwal, M. van Kreveld, and S. Suri,Label placement by maximum independent set in rectangles, Comput. Geom. Theory Appl. 11 (1998), 209--218. Google Scholar
Digital Library
- P. Brass, G. Károlyi, and P. Valtr,A Turán-type extremal theory for convex geometric graphs, Discrete and Computational Geometry--the Goodman-Pollack Festschrift (B. Aronov et al., eds.),Springer 2003, 275--300.Google Scholar
- G. Cairns and Y. Nikolayevsky,Bounds for generalized thrackles, Discrete and Computational Geometry 23 (2000), 191--206.Google ScholarCross Ref
- V. Capoyleas and J. Pach,A Turán-type problem on chords of a convex polygon, J. Comb. Theory Ser. B. 56 (1992), 9--15. Google ScholarDigital Library
- J. Fox and J. Pach, String graphs and incomparability graphs,manuscript, 2008.Google Scholar
- J. Fox and J. Pach, Coloring Kk-free intersection graphs ofgeometric objects in the plane, 24th ACM Symp. on Computational Geometry,College Park, MD, USA, June 2008, 346--354. Google ScholarDigital Library
- J. Fox and J. Pach, A separator theorem for string graphs and its applications, WALCOM '09: Proc. 3rd Int. Workshop on Algorithms and Computation,(S. Das, R. Uehara, eds.), Lecture Notes in Computer Science 5431,Springer-Verlag, Berlin, 2009, 1--14. Google ScholarDigital Library
- J. Fox, J. Pach, and Cs. D. Tóth, A bipartite strengthening of the Crossing Lemma, Graph Drawing '08 (S.-H. Hong, T. Nishizeki, eds.), Lecture Notes in Computer Science 4875, Springer-Verlag, Berlin, 2008, 13--24. Google ScholarDigital Library
- D. S. Hochbaum and W. Maass,Approximation schemes for covering and packing problems in image processing and VLSI, J. ACM 32 (1985), 130--136. Google ScholarDigital Library
- M. Klazar and A. Marcus,Extensions of the linear bound in the Füredi-Hajnal conjecture, Adv. in Appl. Math. 38 (2006), 258--266.Google Scholar
- P. Kolman and J. Matousek,Crossing number, pair-crossing number, and expansion, J. Combin. Theory Ser. B. 92 (2004), 99--113. Google ScholarDigital Library
- E. Malesinska,Graph-theoretical models for frequency assignment problems,Ph.D. Thesis, Technische Universitat Berlin, 1997.Google Scholar
- A. Marcus and G. Tardos,Excluded permutation matrices and the Stanley-Wilf conjecture, J. Comb. Theory Ser. A. 107 (2004), 153--160. Google ScholarDigital Library
- J. Pach, F. Shahrokhi, and M. Szegedy, Applications of the crossing number, Algorithmica 16 1996, 111--117.Google ScholarCross Ref
- J. Pach, R. Pinchasi, M. Sharir, and G. Tóth,Topological graphs with no large grids, Graphs and Combinatorics 21 (2005), 355--364. Google ScholarDigital Library
- J. Pach and G. Tóth,Disjoint edges in topological graphs,in: Combinatorial Geometry and Graph Theory (J. Akiyama et al., eds.),Lecture Notes in Computer Science 3330,Springer-Verlag, Berlin, 2005, 133--140. Google ScholarDigital Library
- J. Pach and J. Törocsik,Some geometric applications of Dilworth's theorem, Discrete and Computational Geometry 12 (1994), 1--7.Google ScholarDigital Library
- R. Pinchasi, personal communication, October 2006.Google Scholar
- G. Tardos and G. Tóth,Crossing stars in topological graphs, SIAM Journal on Discrete Mathematics 21 (2007), 737--749. Google ScholarDigital Library
- G. Tóth,Note on geometric graphs, J. Comb. Theory Ser. A. 89 (2000), 126--132. Google ScholarDigital Library
- W. T. Tutte, Toward a theory of crossing numbers, J. Comb. Theory 8 (1970), 45--53.Google ScholarCross Ref
Index Terms
- On grids in topological graphs
Recommendations
On the Maximum Number of Edges in Topological Graphs with no Four Pairwise Crossing Edges
A topological graph is called k-quasi-planar if it does not contain k pairwise crossing edges. It is conjectured that for every fixed k, the maximum number of edges in a k-quasi-planar graph on n vertices is O(n). We provide an affirmative answer to the ...
Topological graphs: empty triangles and disjoint matchings
SoCG '13: Proceedings of the twenty-ninth annual symposium on Computational geometryA simple topological graph is a graph drawn in the plane so that its edges are represented by continuous arcs with the property that any two of them meet at most once. We present a novel tool for finding crossing free subgraphs in simple topological ...
On the maximum number of edges in quasi-planar graphs
A topological graph is quasi-planar, if it does not contain three pairwise crossing edges. Agarwal et al. [P.K. Agarwal, B. Aronov, J. Pach, R. Pollack, M. Sharir, Quasi-planar graphs have a linear number of edges, Combinatorica 17 (1) (1997) 1-9] ...
Comments