Research Part of the Seminar

Research Part of the Seminar

by Alexander Wolff -
Number of replies: 0

Dear students,

thanks for the open problems that you presented today.

The following paper contains an NP-hardness proof that reduces from (planar) 3-SAT to octilinear graph drawing.
In the proof, the variables and clauses of the given 3-SAT formula are represented by so-called "gadgets".

https://link.springer.com/article/10.1007%2Fs00450-007-0036-y (open access; you just need to read pages 39–41!)

Maybe such a gadget proof can be used to show that the partial respresentation extension problem that we discussed today is also NP-hard!

Good luck!

Alexander