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? In: Graph Drawing 11th International Symposium, GD 2003, September 21-24, 2003 , pp. 47-58(Official URL:

Full text not available from this repository.


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
Additional Information: 10.1007/978-3-540-24595-7_5
Classifications: Z Theory > Z.250 Geometry

Actions (login required)

View Item View Item