[Solved]: Equivalent Straight Line Embedding of a Planar Graph Drawing on a Grid

ignougroup
Problem Detail: An embedding of a graph G on a surface Σ is a representation of G on Σ in which points of Σ are associated to vertices and simple arcs are associated to edges in such a way that:

  • the endpoints of the arc associated to an edge e are the points associated to the end vertices of e,
  • no arcs include points associated with other vertices,
  • two arcs never intersect at a point which is interior to either of the arcs.

Two embeddings of a planar graph in the plane are called equivalent for every vertex of the graph the cyclic order of the incident edges is the same in both embeddings. I am looking for a reference which shows that any Jordan arc embedding of a planar graph can be equivalently embedded as a straight line drawing with the $n$ vertices of the graph lying on the vertices of an $O(n) times O(n)$ grid. (Certainly any planar graph can be embedded with its vertices on the vertices of such a grid but I’m looking for an embedding that’s equivalent to the originally given one.) Schnyder’s algorithm seems to produce an embedding equivalent to the topological embedding given as its input but I’ve not managed to find a proof of this. Does anybody know of such a theorem?

Asked By : user695652

Answered By : A.Schulz

“Schnyder’s algorithm” computes an embedding on an $O(n)times O(n)$ grid. See here for a reference, and see here for a more general treatment that is not behind a paywall. Note that if your initial (topological) embedding is not unique, you can just add edges (while preserving planarity) until the graph becomes 3-connected (or even a triangulation) and then apply some drawing algorithm. Once the layout is computed you simply remove the augmentation. I want to point out that there is also a different drawing algorithm for the $O(n)times O(n)$ grid by De Fraysseix, Pach and Pollack. It is based on the canonical order of the planar graph. See here for the reference if the graph is a triangulation, and here for 3-connected planar graphs.enter link description here. These articles are behind paywalls, but the algorithms are standard and you will find lecture notes if you google the keywords. You might also try to check out the handbook of graph drawing for more information.
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/39557  Ask a Question  Download Related Notes/Documents