3
$\begingroup$

Suppose that we are given $n$ points in the plane, with a degree prescribed for each, and the question is whether we can place a geometric graph on them. Is there an efficient algorithm for this?

Note that this is not the same as Erdős–Gallai for planar graphs. My motivation is to solve a puzzle game on my phone :P

Improve this question
$\endgroup$
4
  • $\begingroup$ Just out of curiosity, which puzzle game? :) $\endgroup$
    – Tadashi
    Commented Jan 14, 2016 at 22:24
  • 1
    $\begingroup$ @Shamisen Windows Phone/Logic Games app/Neighbours puzzle. $\endgroup$
    – domotorp
    Commented Jan 14, 2016 at 22:32
  • 1
    $\begingroup$ Your link describes different type of geometric graphs. Do you mean plane graph with straight edges? $\endgroup$
    – Ilya Bogdanov
    Commented Jan 15, 2016 at 10:45
  • $\begingroup$ @Ilya Yes, planar straight line graph. $\endgroup$
    – domotorp
    Commented Jan 15, 2016 at 11:27

0

Reset to default

You must log in to answer this question.