Multi-Dimensional Orthogonal Graph Drawing with Small Boxes

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

    11 Citations (Scopus)

    Abstract

    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)
    PublisherSpringer
    Pages311-322
    Number of pages12
    Volume1731
    DOIs
    Publication statusPublished - 1999
    EventGraph Drawing 1999 - Prague, Czech Republic
    Duration: 15 Sep 199919 Sep 1999
    Conference number: 7th
    https://link.springer.com/book/10.1007/3-540-46648-7 (Proceedings)

    Publication series

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

    Conference

    ConferenceGraph Drawing 1999
    Abbreviated titleGD 1999
    CountryCzech Republic
    CityPrague
    Period15/09/9919/09/99
    Internet address

    Cite this