Akademska digitalna zbirka SLovenije - logo
(UL)
  • Planar embeddings of graphs with specified edge lengths
    Cabello, Sergio ; Demaine, Erik D. ; Rote, Günter
    We consider the problem of finding a planar embedding of a (planar) graph with a prescribed Euclidean length on every edge. There has been substantial previous work on the problem without the ... planarity restrictions, which has close connections to rigidity theory, and where it is easy to see that the problem is NP-hard. In contrast, we show that the problem is tractable - indeed, solvable in linear time on a real RAM - for planar embeddings of planar 3-connected triangulations, even if the outer face is not a triangle. This result is essentially tight: the problem becomes NP-hard if we consider instead planar embeddings of planar 3-connected infinitesimally rigid graphs, a natural relaxation of triangulations in this context.
    Vir: Preprint series. - ISSN 1318-4865 (Vol. 43, št. 986, 2005, str. 1-16)
    Vrsta gradiva - članek, sestavni del
    Leto - 2005
    Jezik - angleški
    COBISS.SI-ID - 13780057

    Povezava(-e):

    http://www.imfm.si/preprinti/PDF/00986.pdf

vir: Preprint series. - ISSN 1318-4865 (Vol. 43, št. 986, 2005, str. 1-16)

loading ...
loading ...
loading ...

Vnos na polico