1
$\begingroup$

I'm interested in the following paper http://www.computer.org/csdl/trans/tc/1981/02/06312176.pdf

In particular i'm interested in the construction Valiant describes to prove that it is possible to embed a $4$-planar graph in a grid of size $9n^{2}$ (on the top right of page 2). He says that the construction is described in fig 2, but i do not understand it completely. I was hoping someone may be able to explain it more clearly. One of my confusions with the diagram in fig 2 is how do we know the neighbours of the next vertex to be added namely the $(I+1)$st vertex lie on the border of the currently constructed embedding, what's to say stopping one it's neighbours being in the middle of the embedding?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ This doesn't answer your question, but perhaps you are aware that the state-of-the-art has advanced since that 1981 paper. E.g., Cornelsen, Sabine, and Andreas Karrenbauer. "Accelerated bend minimization." Graph Drawing. Springer Berlin Heidelberg, 2012. They compute a min bend drawing in subquadratic time. $\endgroup$
    – Joseph O'Rourke
    Commented Jan 12, 2016 at 14:49
  • $\begingroup$ Thanks for the info, i'm interested in this particular construction however. $\endgroup$
    – Pavan Sangha
    Commented Jan 12, 2016 at 20:25
  • $\begingroup$ You have already asked the same question before (mathoverflow.net/questions/219260/…) which I already answered and you accepted. Is there a reason that you are asking it again? $\endgroup$
    – Tony Huynh
    Commented Jan 12, 2016 at 22:43
  • $\begingroup$ Hi, you said it was a graph with $n$ vertices but it should actually be $n$ edges, it says the size of the graph is $n$ and the size is the cardinality of the edge set. In addition what did you mean by the same outer face? $\endgroup$
    – Pavan Sangha
    Commented Jan 13, 2016 at 10:33
  • $\begingroup$ Would your original proof change in anyway based on the fact that you did yours with $n$ vertices? $\endgroup$
    – Pavan Sangha
    Commented Jan 14, 2016 at 10:44

0

Reset to default

You must log in to answer this question.