Newsgroups: comp.theory
From: Hoey@AIC.NRL.Navy.Mil (Dan Hoey)
Date: 1996/12/06
Subject: Re: canonical planarization algorithm?

mann...@ochre.newcastle.edu.au (Joseph Manning) writes:

> Does anyone know of a linear-time canonical planarization algorithm?
  ...
> I am aware of several existing linear-time planarization algorithms,
> but it is unclear whether any of these produce a canonical embedding....

You won't find this under "planarization" because the "canonical" part
is an extension of the much harder problem of isomorphism.  While
graph isomorphism is not (shown to be) NP-hard, no known polynomial
algorithm is known.  Fortunately, there are good algorithms for
isomorphism of planar graphs, from which a canonical vertex ordering
can be derived.  Given a canonical vertex ordering, an arbitrary
deterministic embedding algorithm can be used.

I think you will find the time to be O(n log n), rather than linear.
While the last paper listed below describes a linear-time isomorphism
algorithm (building on ideas developed in the others), it looks as
though moving to a canonical ordering requires an extra log n.  I am
somewhat uncertain of this, however, especially as none of these
papers actually treats the canonization problem.

These are the papers I know of:

  Hopcroft,J.E. and Tarjan,R., "A V^2 Algorithm for Determining
  Isomorphism of Triconnected Planar Graphs", Information Processing
  Letters 1(1971)32-34.

  Hopcroft,J.E. and Tarjan,R., "Dividing a Graph into Triconnected
  Components", SIAM J. Comput, V2, N3(1973), 135-158.

  Hopcroft,J.E. and Tarjan,R., "Isomorphism of Planar Graphs
  (working paper)" in _Complexity of Computer Computations_,
  (R.E. Miller and J.W.  Thatcher, eds.), 131-152, Plenum Press,
  1972.

  Hopcroft,J.E. and Tarjan,R., "A V log V Algorithm for Isomorphism
  of Triconnected Planar Graphs", J. Comput. Syst. Sci, 7(1973),
  323-331.

  Hopcroft,J.E. and Wong,J.K., "Linear Time Algorithm for
  Isomorphism in Planar Graphs.", Sixth Annual Symposium on
  Theoretical Computer Science, Seattle, 1974.

I would appreciate hearing of any others you find, especially if there
has been anything published on finding canonical representatives of
planar graphs.

Dan Hoey
Hoey@AIC.NRL.Navy.Mil