Topological graphs with no self-intersecting cycle of length 4

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Topological graphs with no self-intersecting cycle of length 4

Full text

Pdf (255 KB)

Source

Annual Symposium on Computational Geometry archive
Proceedings of the nineteenth annual symposium on Computational geometry table of contents

San Diego, California, USA

SESSION: Combinatorial geometry table of contents

Pages: 98 - 103

Year of Publication: 2003

ISBN:1-58113-663-3

Authors

Rom Pinchasi	Massachusetts Institute of Technology, Cambridge, MA
Radoa Radoicic	Massachusetts Institute of Technology, Cambridge, MA

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques
ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 26, Citation Count: 5

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/777792.777807 What is a DOI?

ABSTRACT

Let G be a topological graph on n vertices in the plane, i.e., a graph drawn in the plane with its vertices represented as points and its edges represented as Jordan arcs connecting pairs of points. It is shown that if no two edges of any cycle of length 4 in G cross an odd number of times, then |E(G)|=O(n^8/5).

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Eran Nevo , János Pach , Rom Pinchasi , Micha Sharir , Shakhar Smorodinsky, Lenses in arrangements of pseudo-circles and their applications, Proceedings of the eighteenth annual symposium on Computational geometry, p.123-132, June 05-07, 2002, Barcelona, Spain [doi>10.1145/513400.513417]
	2	S. Avital and H. Hanani. Graphs. Gilyonot Lematematika, 3:2--8, 1966.
	3	Bela Bollobas, Extremal Graph Theory, Dover Publications, Incorporated, 2004
	4	P. Braay, G. Karolyi, and P. Valtr. A turan-type extremal theory for convex geometric graphs. Discrete and Computational Geometry, to appear, 2003.
	5	P. Erdos and M. Simonovits. Some extremal problems in graph theory. In Combinatorial theory and its applications, I, pages 377--390. Balatonfured, 1969.
	6	P. Erdos and M. Simonovits. Cube-supersaturated graphs and related problems. In Progress in graph theory (Waterloo, Ontario, 1982), pages 203--218. Academic Press, Toronto, 1984.
	7	A. Hanani. Uber wesentlich unplattbare kurven im dreidimensionalen raume. Fund. Math., 23:135--142, 1934.
	8	T. Kovari, V. Sas, and P. Turan. On a problem of k. zarankiewicz. Colloquium Mathematicum, 3:50--57, 1954.
	9	Y. Kupitz. Extremal problems in combinatorial geometry. Aarhus University Lecture Notes Series, 53, 1979.
	10	J. Pach, R. Radoicic, and G. Tath. Relaxating planarity for topological graphs. page to appear.
	11	János Pach , Rom Pinchasi , Gábor Tardos , Géza Tóth, Geometric Graphs with No Self-intersecting Path of Length Three, Revised Papers from the 10th International Symposium on Graph Drawing, p.295-311, August 26-28, 2002
	12	H. Tamaki and T. Tokuyama. How to cut pseudo-parabolas into segments. Discrete and Computational Geometry, 19:265--290, 1998.
	13	G. Tardos. On the number of edges in a geometric graph with no short self-intersecting paths. page in preperation.
	14	W. T. Tutte. Toward a theory of crossing numbers. Journal of Combinatorial Theory, 8:45--53, 1970.

CITED BY 5

	Pankaj K. Agarwal , Eran Nevo , János Pach , Rom Pinchasi , Micha Sharir , Shakhar Smorodinsky, Lenses in arrangements of pseudo-circles and their applications, Journal of the ACM (JACM), v.51 n.2, p.139-186, March 2004
	Rom Pinchasi , Shakhar Smorodinsky, On locally Delaunay geometric graphs, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA
	János Pach , Rom Pinchasi , Gábor Tardos , Géza Tóth, Geometric graphs with no self-intersecting path of length three, European Journal of Combinatorics, v.25 n.6, p.793-811, August 2004
	Jakub erný , Zdenk Dvořák , Vít Jelínek , Jan Kára, Noncrossing Hamiltonian paths in geometric graphs, Discrete Applied Mathematics, v.155 n.9, p.1096-1105, May, 2007
	Timothy M. Chan, On levels in arrangements of curves, iii: further improvements, Proceedings of the twenty-fourth annual symposium on Computational geometry, June 09-11, 2008, College Park, MD, USA