Name
Abstract | ||
|---|---|---|
Simple curves on surfaces are often represented as sequences of intersections with a trian- gulation. However, there are much more succinct ways of representing simple curves used in topology such as normal coordinates. In these representations, the length of a curve can be exponential in the size of its representation. Nevertheless, we show that the following two basic tasks of computational topology, namely • performing a Dehn-twist of a curve along another curve, and • computing the geometric intersection number of two curves, can be solved in polynomial time even in the succinct normal coordinate representation. These are the first algorithms for these two problems that solve these problems in time polynomial in the succinct representations. As a consequence we can show that a generalized notion of crossing number can be decided in NP, even though the drawings can have exponential complexity. |
Year | Venue | Keywords |
|---|---|---|
2008 | canadian conference on computational geometry | computational topology,polynomial time,intersection number,crossing number,dehn twist |
Field | DocType | Citations |
Discrete mathematics,Combinatorics,Crossing number (graph theory),Intersection number,Polynomial,Triangulation (social science),Normal coordinates,Time complexity,Mathematics,Computational topology,Exponential growth | Conference | 6 |
PageRank | References | Authors |
0.52 | 17 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Marcus Schaefer | 1 | 123 | 12.63 |
| Eric Sedgwick | 2 | 142 | 14.38 |
| Daniel Stefankovic | 3 | 243 | 28.65 |