Advertisement
Published in:
2006 | OriginalPaper | Chapter
Simultaneous Graph Embeddings with Fixed Edges
Authors : Elisabeth Gassner, Michael Jünger, Merijam Percan, Marcus Schaefer, Michael Schulz
Published in: Graph-Theoretic Concepts in Computer Science
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. 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.