Library

X
feed icon rss

Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
  • 1
    Electronic Resource
    Electronic Resource
    How to draw a planar graph on a grid (1990)
    Springer
    Combinatorica 10 (1990), S. 41-51 
    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
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Crossing families (1994)
    Springer
    Combinatorica 14 (1994), S. 127-134 
    Details
    ISSN: 1439-6912
    Keywords: 52 C 10 ; 68 Q 20
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract Given a set of points in the plane, a crossing family is a collection of line segments, each joining two of the points, such that any two line segments intersect internally. Two setsA andB of points in the plane are mutually avoiding if no line subtended by a pair of points inA intersects the convex hull ofB, and vice versa. We show that any set ofn points in general position contains a pair of mutually avoiding subsets each of size at least $$\sqrt {n/12} $$ . As a consequence we show that such a set possesses a crossing family of size at least $$\sqrt {n/12} $$ , and describe a fast algorithm for finding such a family.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01215345
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...