Name
Abstract | ||
|---|---|---|
Answering a question of Rosenstiehl and Tarjan, we show that every plane graph with n vertices has a Fary embedding (i.e., straight-line embedding) on the 2n-4 by n-2 grid and provide an O(n) space, O(n log n) time algorithm to effect this embedding. The grid size is asymptotically optimal and it had been previously unknown whether one can always find a polynomial sized grid to support such an embedding. On the other hand we show that any set F, which can support a Fary embedding of every planar graph of size n, has cardinality at least n+(1-o(1)) square-root n which settles a problem of Mohar. |
Year | DOI | Venue |
|---|---|---|
1990 | 10.1007/BF02122694 | COMBINATORICA |
Keywords | Field | DocType |
planar graph,plane graph | Graph theory,Discrete mathematics,Combinatorics,Embedding,Slope number,Graph embedding,Planar straight-line graph,Linkless embedding,Dominance drawing,Planar graph,Mathematics | Journal |
Volume | Issue | ISSN |
10 | 1 | 0209-9683 |
Citations | PageRank | References |
331 | 23.55 | 3 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hubert de Fraysseix | 1 | 672 | 70.60 |
| János Pach | 2 | 2366 | 292.28 |
| Richard Pollack | 3 | 912 | 203.75 |