ALBERT

All Library Books, journals and Electronic Records Telegrafenberg

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
    The complexity of detecting crossingfree configurations in the plane (1993)
    Springer
    BIT 33 (1993), S. 580-595 
    Details
    ISSN: 1572-9125
    Keywords: 05C05 ; 68Q25 ; 68R10 ; algorithmic complexity ; planar layouts ; geometry
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract The computational complexity of the following type of problem is studied. Given a geometric graphG=(P, S) whereP is a set of points in the Euclidean plane andS a set of straight (closed) line segments between pairs of points inP, we want to know whetherG possesses a crossingfree subgraph of a special type. We analyze the problem of detecting crossingfree spanning trees, one factors and two factors in the plane. We also consider special restrictions on the slopes and on the lengths of the edges in the subgraphs.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01990536
    Location Call Number Expected 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...