Orthogonal drawings with few layers

Therese Biedl, John R. Johansen, Thomas Shermer, David R. Wood

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

6 Citations (Scopus)

Abstract

In this paper, we study 3-dimensional orthogonal graph drawings. Motivated by the fact that only a limited number of layers is possible in VLSI technology, and also noting that a small number of layers is easier to parse for humans, we study drawings where one dimension is restricted to be very small. We give algorithms to obtain point-drawings with 3 layers and 4 bends per edge, and algorithms to obtain box-drawings with 2 layers and 2 bends per edge. Several other related results are included as well. Our constructions have optimal volume, which we prove by providing lower bounds.

Original languageEnglish
Title of host publicationGraph Drawing - 9th International Symposium, GD 2001, Revised Papers
PublisherSpringer
Pages297-311
Number of pages15
Volume2265 LNCS
ISBN (Print)3540433090, 9783540433095
DOIs
Publication statusPublished - 2002
Externally publishedYes
EventGraph Drawing 2001 - Vienna, Austria
Duration: 23 Sep 200126 Sep 2001
Conference number: 9th
https://link.springer.com/book/10.1007/3-540-45848-4 (Proceedings)

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2265 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceGraph Drawing 2001
Abbreviated titleGD 2001
CountryAustria
CityVienna
Period23/09/0126/09/01
Internet address

Cite this