How Many Ways Can One Draw a Graph?

Pach, János and Tóth, Géza (2004) How Many Ways Can One Draw a Graph? [Conference Paper]

Full text not available from this repository.

Abstract

Using results from extremal graph theory, we determine the asymptotic number of string graphs with n vertices, i.e., graphs that can be obtained as the intersection graph of a system of continuous arcs in the plane. The number becomes much smaller, for any fixed d, if we restrict our attention to systems of arcs, any two of which cross at most d times. As an application, we estimate the number of different drawings of the complete graph K_{n} with n vertices under various side conditions.

Item Type:	Conference Paper
Classifications:	Z Theory > Z.250 Geometry
ID Code:	426
Deposited By:	Maciejak, Agnes
Deposited On:	02 Dec 2004
Last Modified:	18 Sep 2008 13:08
Alternative Locations:	http://www.springerlink.com/openurl.asp?genre=article&issn=0302-9743&volume=2912&spage=47

Repository Staff Only: item control page

References

[B59] S. Benzer, On the topology of the genetic fine structure, Proceedings of the National Academy of Sciences of the United States of America 45 (1959), 1607-1620.

[B78] B. Bollobás, Extremal Graph Theory, London Mathematical Society Monographs 11, Academic Press. [Harcourt Brace Jovanovich, Publishers], London-New York, 1978.

[BT97] B. Bollobás and A. Thomason, Hereditary and monotone properties of graphs, in: The mathematics of Paul Erdös II, (R. L. Graham and J. Nesetril, eds.) Algorithms Combin. 14, Springer, Berlin, 1997, 70-78.

[CGP98a] Z.-Z. Chen, M. Grigni, and C. H. Papadimitriou, Planar map graphs, in: STOC '98, ACM, 1998, 514-523.

[CGP98b] Z.-Z. Chen, M. Grigni, and C. H. Papadimitriou, Planar topological inference, (Japanese) in: Algorithms and Theory of Computing (Kyoto, 1998) Surikaisekikenkyusho Kokyuroku 1041 (1998), 1-8.

[CHK99] Z.-Z. Chen, X. He, and M.-Y. Kao, Nonplanar topological inference and political-map graphs, in: Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms (Baltimore, MD, 1999), ACM, New York, 1999, 195-204.

[Ch34] Ch. Chojnacki (A. Hanani), Über wesentlich unplättbare Kurven im dreidimensionalem Raume, Fund. Math. 23 (1934), 135-142.

[DETT99] G. Di Battista, P. Eades, R. Tamassia, and I. G. Tollis. Graph Drawing. Prentice Hall, Upper Saddle River, NJ, 1999.

[E93] M. Egenhofer, A model for detailed binary topological relationships, Geomatica 47 (1993), 261-273.

[E65] P. Erdös, On some extremal problems in extremal graph theory, Israel J. Math. 3 (1965), 113-116.

[EF91] M. Egenhofer and R. Franzosa, Point-set topological spatial relations, International Journal of Geographical Information Systems 5 (1991), 161-174.

[ES93] M. Egenhofer and J. Sharma, Assessing the consistency of complete and incomplete topological information. Geographical Systems 1 (1993), 47-68.

[EET76] G. Ehrlich, S. Even, and R. E. Tarjan, Intersection graphs of curves in the plane, Journal of Combinatorial Theory, Series B 21 (1976), 8-20.

[EFR86] P. Erdös, P. Frankl, and V. Rödl, The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent, Graphs and Combinatorics 2 (1986), 113-121.

[ES66] P. Erdös and M. Simonovits, A limit theorem in graph theory, Studia Sci. Math. Hungar. 1 (1966), 51-57.

[ES46] P. Erdös and A. H. Stone, On the structure of linear graphs, Bulletin Amer. Math. Soc. 52 (1946), 1087-1091.

[EPL72] S. Even, A. Pnueli, and A. Lempel, Permutation graphs and transitive graphs, Journal of Association for Computing Machinery 19 (1972), 400-411.

[G80] M. C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York, 1980.

[GP86] J. E. Goodman and R. Pollack, Upper bounds for configurations and polytopes in R^{d}, Discrete Comput. Geom. 1 (1986), 219-227.

[G78] R. L. Graham, Problem, in: Combinatorics, Vol. II (A. Hajnal and V. T. Sós, eds), North-Holland Publishing Company, Amsterdam, 1978, 1195.

[HT74] J. Hopcroft and R. E. Tarjan. Efficient planarity testing. J. ACM, 21 (1974), 549-568.

[K83] J. Kratochvíl, String graphs, in: Graphs and Other Combinatorial Topics (Prague, 1982), Teubner-Texte Math. 59, Teubner, Leipzig, 1983, 168-172.

[K91a] J. Kratochvíl, String graphs I: The number of critical nonstring graphs is infinite, Journal of Combinatorial Theory, Series B 52 (1991), 53-66.

[K91b] J. Kratochvíl, String graphs II: Recognizing string graphs is NP-hard, Journal of Combinatorial Theory, Series B 52 (1991), 67-78.

[K98] J. Kratochvíl, Crossing number of abstract topological graphs, in: Graph drawing (Montreal, QC, 1998), Lecture Notes in Comput. Sci. 1547, Springer, Berlin, 1998, 238-245.

[PA95] J. Pach and P. K. Agarwal, Combinatorial Geometry, Wiley Interscience, New York, 1995.

[PS01] J. Pach and J. Solymosi, Crossing patterns of segments, Journal of Combinatorial Theory, Ser. A, 96 (2001), 316-325.

[PT02] J. Pach and G. Tóth, Recognizing string graphs is decidable, Lecture Notes in Computer Science 2265, Springer-Verlag, Berlin, 2001, 247-260. Also in: Discrete and Computational Geometry 28 (2002), 593-606.

[PS92] H. J. Prömel and A. Steger, Excluding induced subgraphs III: A general asymptotic, Random Structures and Algorithms 3 (1992), 19-31.

[SS01a] M. Schaefer and D. Stefankovic, Decidability of string graphs, Proceedings of the 33rd Annual Symposium on the Theory of Computing, 2001, 241-246.

[SS01b] M. Schaefer, E. Sedgwick and D. Stefankovic, Recognizing string graphs in NP, Proceedings of the 34rd Annual Symposium on the Theory of Computing, 2002, 1-6.

[S66] F. W. Sinden, Topology of thin film RC circuits, Bell System Technological Journal (1966), 1639-1662.

[SP92] T. R. Smith and K. K. Park, Algebraic approach to spatial reasoning, International Journal of Geographical Information Systems 6 (1992), 177-192.

[T70] W. T. Tutte, Toward a theory of crossing numbers, J. Combinatorial Theory 8 (1970), 45-53.