Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
h-Quasi Planar Drawings of Bounded Treewidth Graphs in Linear Area
verfasst von : Emilio Di Giacomo, Walter Didimo, Giuseppe Liotta, Fabrizio Montecchiani
Erschienen in: Graph-Theoretic Concepts in Computer Science
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.