Planar graph embedding book unclear description

Question

I've been searching for linear-time planar graph embedding algorithm. I've found one book "A Linear-time Algorithm for Drawing a Planar Graph on a Grid" - M.Chobak, T.H.Payne.

In algorithm description they write "We assume that G is already triangulated and embedded in the plane, and that a canonical ordering of G is given."

It's kind of strange that algorithm which purpose is plane embedding require plane embedding already computed.

How can it be explained? And then what algorithm(s) I should use to get plane embedding if I have only adjacency matrix/list.

Answer 1

There are more variations of graph embedding problem.

The article you found deals with embedding a graph into a grid, that is to identify graph's vertices with the vetices of a grid, such that edges form non-intersecting straight lines. If I understand right, you are dealing with embedding graph into a plane in general.

While the grid embedding is a solution for your problem, the planar embedding of a graph has to be altered to fit a grid with straight lines as edges. And this is precisely what the article deals with.

As for a particular algorithm for planar embedding, this might be useful (implementing it might be a challenge though):
Chiba, Nishizeki, Abe, Ozawa, A linear algorithm for embedding planar graphs using PQ-trees.