ZIB

Hits per page

hit 1 - 1 | 1 hit

Sorting

Electronic Resource

How to draw a planar graph on a grid (1990)

Fraysseix, H. ; Pach, J. ; Pollack, R.

Springer

Combinatorica 10 (1990), S. 41-51

add to mindlist on the mindlist

Details

ISSN: 1439-6912

Keywords: 05C10 ; 05C35 ; 68E10

Source: Springer Online Journal Archives 1860-2000

Topics: Mathematics

Notes: Abstract Answering a question of Rosenstiehl and Tarjan, we show that every plane graph withn vertices has a Fáry embedding (i.e., straight-line embedding) on the 2n−4 byn−2 grid and provide anO(n) space,O(n logn) 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 setF, which can support a Fáry embedding of every planar graph of sizen, has cardinality at leastn+(1−o(1))√n which settles a problem of Mohar.

Type of Medium: Electronic Resource

URL: http://dx.doi.org/10.1007/BF02122694

Permalink

Library	Location	Call Number	Volume/Issue/Year	Availability

Others were also interested in ...

Paper (German National Licenses)

Fulltext

hit 1 - 1 | 1 hit