3
$\begingroup$

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?

Improve this question
$\endgroup$
14
  • 1
    $\begingroup$ @RickDecker Please note that this question does not ask whether it is possible to embed any graph in a grid, but it asks for equivalent embeddings. $\endgroup$
    – user695652
    Feb 19, 2015 at 2:40
  • 2
    $\begingroup$ @user695652 Did you check the answers to the other question? Do they produce embeddings that are not equivalent to the original graph? $\endgroup$
    – David Richerby
    Feb 19, 2015 at 8:18
  • 1
    $\begingroup$ @ David Richerby Thank you for your comment. After carefully reading the related question and the linked literature, I do understand that Schnyder's algorithm produces an equivalent embedding (to the topological embedding given as input to the algorithm). Nevertheless I did not success to find a theorem stating that fact. Do you know of any reference? $\endgroup$
    – user695652
    Feb 22, 2015 at 22:25
  • 1
    $\begingroup$ A planar drawing/embedding of a (not necessarily planar) graph determines a circular ordering of the edges incident to each vertex. In the literature, a planar graph together with a chosen drawing/embedding is called a plane graph. This question is asking if there's a straight-line grid drawing for every plane graph, i.e. that preserves the order of the edges on each vertex. $\endgroup$
    – Fizz
    Mar 3, 2015 at 13:11
  • 1
    $\begingroup$ The fact that every plane graph (i.e. planar graph + fixed embedding, i.e. fixed rotation system) can be turned into a plane graph with straight lines (i.e. preserving the rotation system) is trivially contained in the proof of Fary's theorem. This is because the proof deletes star vertices and then reinserts them with straightened edges while keeping all other vertices fixed; so the edge order at every vertex, thus rotation system is preserved. However this does entail anything about what other "straightening" algorithms do with respect to the rotation system... $\endgroup$
    – Fizz
    Mar 3, 2015 at 16:52

1 Answer 1

Reset to default
2
+150
$\begingroup$

"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.

Improve this answer
$\endgroup$
12
  • $\begingroup$ So, in other words, this question was an exact duplicate of the other one, safe for explicitly asking for references. $\endgroup$
    – Fizz
    Mar 3, 2015 at 10:47
  • 1
    $\begingroup$ @RespawnedFluff: No, it is not. The OP asks for an algorithm that respect a topological embedding that is given beforehand. Also he asks for straight-line embedding. Finally, he is not interested in general grid embeddings, but in embeddings on the $O(n)\times O(n)$ grid. $\endgroup$
    – A.Schulz
    Mar 3, 2015 at 12:27
  • $\begingroup$ But then have you actually answered the question? Do either of these algorithms preserve the (circular) edge order on each vertex (for a plane graph, i.e. where the ordering of the edges is fixed/given)? This is what the OP seem to be actually asking. $\endgroup$
    – Fizz
    Mar 3, 2015 at 13:17
  • 1
    $\begingroup$ @A.Schulz Thank you. To make sure I understand your argument: We know that any maximally planar graph (on more than 3 vertices) is 3-connetected and Whitney's theorem states that every 3-connected planar graph has a unique embedding . Given an input graph $G(V,E)$ vertices and it's embedding, we make it maximally planar by adding $(3|V|-6) - |E|$ many edges. We then pass the resulting maximally plane embedding to Schnyder's algorithm which creates an equivalent straight-line embedding on a grid (due to the uniqueness of the embedding) and then remove the added edges. Is that right? $\endgroup$
    – user695652
    Mar 3, 2015 at 19:47
  • 1
    $\begingroup$ @user695652: Diestel has the proof: Lemma 4.4.5; Corollary 4.4.7; pp. 104-105 in the 4th ed.. The way he proves Kuratowski's theorem essentially contains this result as part of the proof of the theorem. $\endgroup$
    – Fizz
    Mar 3, 2015 at 23:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.