Transforming spanning trees: A lower bound

K. Buchin, A. Razen, T. Uno, U. Wagner

    Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

    5 Citaten (Scopus)

    Samenvatting

    For a planar point set we consider the graph whose vertices are the crossing-free straight-line spanning trees of the point set, and two such spanning trees are adjacent if their union is crossing-free. An upper bound on the diameter of this graph implies an upper bound on the diameter of the flip graph of pseudo-triangulations of the underlying point set. We prove a lower bound of O(logn/loglogn) for the diameter of the transformation graph of spanning trees on a set of n points in the plane. This nearly matches the known upper bound of O(logn). If we measure the diameter in terms of the number of convex layers k of the point set, our lower bound construction is tight, i.e., the diameter is in O(logk) which matches the known upper bound of O(logk). So far only constant lower bounds were known.
    Originele taal-2Engels
    Pagina's (van-tot)724-730
    TijdschriftComputational Geometry
    Volume42
    Nummer van het tijdschrift8
    DOI's
    StatusGepubliceerd - 2009

    Vingerafdruk Duik in de onderzoeksthema's van 'Transforming spanning trees: A lower bound'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit