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 Kn with n vertices under various side conditions. |
Year | DOI | Venue |
---|---|---|
2006 | 10.1007/s00493-006-0032-z | Lecture Notes in Computer Science |
Keywords | Field | DocType |
various side condition,n vertex,continuous arc,asymptotic number,extremal graph theory,complete graph kn,string graph,draw a graph,different drawing,intersection graph,character string,complete graph,number theory,graph theory,numerical method,data visualization | Discrete mathematics,Combinatorics,Line graph,Graph power,Graph homomorphism,Cycle graph,Null graph,Symmetric graph,Mathematics,Topological graph,Complement graph | Journal |
Volume | Issue | ISSN |
26 | 5 | 0209-9683 |
Citations | PageRank | References |
11 | 0.81 | 15 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
János Pach | 1 | 2366 | 292.28 |
Géza Tóth | 2 | 581 | 55.60 |