We study the problem of computing h-quasi planar drawings in linear area; in an h-quasi planar drawing the number of mutually crossing edges is at most h − 1. We prove that every n-vertex partial k-tree admits a straight-line h-quasi planar drawing in O(n) area, where h depends on k but not on n. For specific sub-families of partial k-trees, we present ad-hoc algorithms that compute h-quasi planar drawings in linear area, such that h is significantly reduced with respect to the general result. Finally, we compare the notion of h-quasi planarity with the notion of h-planarity, where each edge is allowed to be crossed at most h times.
h-quasi planar Drawings of Bounded Treewidth Graphs in Linear Area
DI GIACOMO, Emilio;DIDIMO, WALTER;LIOTTA, Giuseppe;MONTECCHIANI, FABRIZIO
2012
Abstract
We study the problem of computing h-quasi planar drawings in linear area; in an h-quasi planar drawing the number of mutually crossing edges is at most h − 1. We prove that every n-vertex partial k-tree admits a straight-line h-quasi planar drawing in O(n) area, where h depends on k but not on n. For specific sub-families of partial k-trees, we present ad-hoc algorithms that compute h-quasi planar drawings in linear area, such that h is significantly reduced with respect to the general result. Finally, we compare the notion of h-quasi planarity with the notion of h-planarity, where each edge is allowed to be crossed at most h times.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
