Multi-Dimensional Orthogonal Graph Drawing with Small Boxes

    Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

    12 Citations (Scopus)


    In this paper we investigate the general position model for the drawing of arbitrary degree graphs in the D-dimensional (D ≥ 2) orthogonal grid. In this model no two vertices lie in the same grid hyperplane. We show that for D ≥ 3, given an arbitrary layout and initial edge routing a crossing-free orthogonal drawing can be determined. We distinguish two types of algorithms. Our layout-based algorithm, given an arbitrary fixed layout, determines a degree-restricted orthogonal drawing with each vertex having aspect ratio two. Using a balanced lay-out this algorithm establishes improved bounds on the size of vertices for 2-D and 3-D drawings. Our routing-based algorithm produces 2-degree-restricted 3-D orthogonal drawings. One advantage of our approach in 3-D is that edges are typically routed on each face of a vertex; hence the produced drawings are more truly three-dimensional than those produced by some existing algorithms.
    Original languageEnglish
    Title of host publicationGraph drawing (v Stiv ri n Castle, 1999)
    Number of pages12
    Publication statusPublished - 1999
    EventGraph Drawing 1999 - Prague, Czechia
    Duration: 15 Sept 199919 Sept 1999
    Conference number: 7th (Proceedings)

    Publication series

    NameLecture Notes in Computer Science
    ISSN (Print)0302-9743


    ConferenceGraph Drawing 1999
    Abbreviated titleGD 1999
    Internet address

    Cite this