Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. On grids in topological graphs
 
research article

On grids in topological graphs

Ackerman, Eyal
•
Fox, Jacob
•
Pach, Janos  
Show more
2014
Computational Geometry-Theory And Applications

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-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 0 k(n). This conjecture is shown to be true apart from an iterated logarithmic factor log* n. 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 Ok(n) edges, but we can establish only an O-k(n log(2) n) upper bound. We verify the above conjectures in several special cases. (C) 2014 Elsevier B.V. All rights reserved.

  • Details
  • Metrics
Type
research article
DOI
10.1016/j.comgeo.2014.02.003
Web of Science ID

WOS:000336186100002

Author(s)
Ackerman, Eyal
Fox, Jacob
Pach, Janos  
Suk, Andrew  
Date Issued

2014

Publisher

Elsevier Science Bv

Published in
Computational Geometry-Theory And Applications
Volume

47

Issue

7

Start page

710

End page

723

Subjects

Topological graphs

•

Geometric graphs

•

Turan-type problems

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DCG  
Available on Infoscience
June 23, 2014
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/104569
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés