Papex

Open problem · Computer science · Open

Simultaneous embedding with fixed edges

Can it be tested in polynomial time whether two graphs on the same vertices can be drawn together so that each is crossing-free and shared edges coincide?

Summary

Simultaneous embedding draws several graphs on a shared vertex set, allowing crossings only between edges of different graphs. With fixed edges, an edge present in both graphs must be drawn as the same curve; for three or more graphs the test is NP-complete, and for two graphs it is open.

Source

Open, as listed by Wikipedia · Unsolved problems in computer science. Checked 18 Nov 2026.

The status is the source’s. Papex does not decide whether a problem is solved.

Records on this problem

No public record addresses this problem yet.

More in Computing