Anzeige
Erschienen in:
2006 | OriginalPaper | Buchkapitel
Simultaneous Graph Embeddings with Fixed Edges
verfasst von : Elisabeth Gassner, Michael Jünger, Merijam Percan, Marcus Schaefer, Michael Schulz
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 simultaneously embedding several graphs on the same vertex set in such a way that edges common to two or more graphs are represented by the same curve. This problem is known as
simultaneously embedding graphs with fixed edges
. We show that this problem is closely related to the
weak realizability
problem: Can a graph be drawn such that all edge crossings occur in a given set of edge pairs? By exploiting this relationship we can explain why the simultaneous embedding problem is challenging, both from a computational and a combinatorial point of view.
More precisely, we prove that simultaneously embedding graphs with fixed edges is NP-complete even for three planar graphs. For two planar graphs the complexity status is still open.