2006 | OriginalPaper | Buchkapitel
Morphing Planar Graphs While Preserving Edge Directions
verfasst von : Therese Biedl, Anna Lubiw, Michael J. Spriggs
Erschienen in: Graph Drawing
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
Two straight-line drawings
P
,
Q
of a graph (
V
,
E
) are called
parallel
if, for every edge (
u
,
v
) ∈
E
, the vector from
u
to
v
has the same direction in both
P
and
Q
. We study problems of the form: given simple, parallel drawings
P
,
Q
does there exist a continuous transformation between them such that intermediate drawings of the transformation remain simple and parallel with
P
(and
Q
)? We prove that a transformation can always be found in the case of orthogonal drawings; however, when edges are allowed to be in one of three or more slopes the problem becomes NP-hard.