Name
Abstract | ||
|---|---|---|
Abstract. A graph is called a string graph if its vertices can be represented by continuous curves (``strings'') in the plane so that two of them cross each other
if and only if the corresponding vertices are adjacent. It is shown that there exists a recursive function f(n) with the property that every string graph of n vertices has a representation in which any two curves cross at most f(n) times. We obtain as a corollary that there is an algorithm for deciding whether a given graph is a string graph. This solves
an old problem of Benzer (1959), Sinden (1966), and Graham (1971).
|
Year | DOI | Venue |
|---|---|---|
2001 | https://doi.org/10.1007/s00454-002-2891-4 | Discrete & Computational Geometry |
Keywords | Field | DocType |
recognizing string graphs | Wheel graph,Discrete mathematics,Combinatorics,Vertex-transitive graph,Graph power,Graph homomorphism,Cycle graph,String graph,Distance-regular graph,Mathematics,Complement graph | Conference |
Volume | Issue | ISSN |
28 | 4 | 0179-5376 |
ISBN | Citations | PageRank |
3-540-43309-0 | 20 | 1.18 |
References | Authors | |
19 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| János Pach | 1 | 2366 | 292.28 |
| Géza Tóth | 2 | 581 | 55.60 |