The maximum number of edges in a three-dimensional grid-drawing

Prosenjit Bose, Jurek Czyzowicz, Pat Morin, David R. Wood

    Research output: Chapter in Book/Report/Conference proceedingChapter (Book)Researchpeer-review

    Abstract

    An exact formula is given for the maximum number of edges in a graph that admits a three-dimensional grid-drawing contained in a given bounding box. The first universal lower bound on the volume of threedimensional grid-drawings is obtained as a corollary. Our results generalise to the setting of multi-dimensional polyline grid-drawings.

    Original languageEnglish
    Title of host publicationGraph Algorithms and Applications 5
    PublisherWorld Scientific Publishing
    Pages21-26
    Number of pages6
    ISBN (Electronic)9789812773289
    ISBN (Print)981256845X, 9789812568458
    DOIs
    Publication statusPublished - 1 Jan 2006

    Cite this