数值算法/人工智能

开发平台：
MultiPlatform

planar.tex：源码内容
							input cwebmac
documentstyle[comments,a4,psfig]{cweb}
typeout{TransFig: figure text in LaTeX.}
typeout{TransFig: figures in PostScript.}
begingroupmakeatletter
% extract first six characters in fmtname
defx#1#2#3#4#5#6#7relax{defx{#1#2#3#4#5#6}}
expandafterxfmtname xxxxxxrelax defy{splain}
endgroup
endinput
voffset=-0.5cm
textwidth		14cm
oddsidemargin          0.4cm
evensidemargin         1.4cm
marginparwidth		1.9cm
marginparsep		0.4cm
marginparpush		0.4cm
topmargin		0cm
headsep		1.5cm
textheight		21.5cm
footskip		2.2cm
begin{document}
thispagestyle{empty}
renewcommand{thefootnote}{fnsymbol{footnote}}
title{An Implementation of the Hopcroft and Tarjan Planarity Test and
Embedding Algorithm}
thanks{This work was supported in part by the German Ministry for Research
and Technology (Bundesministerium fuer Forschung und Technologie) under
grant ITS 9103 and by the ESPRIT Basic Research Actions Program under
contract No. 7141 (project ALCOM II).}
author{Kurt Mehlhorn\
        {footnotesize  Max-Planck-Institut fuer Informatik,}\[-0.7ex]
   	{footnotesize 66123 Saarbruecken, Germany}\[0.7ex]
	and Petra Mutzel\
        {footnotesize  Institut fuer Informatik,}\[-0.7ex]
	{footnotesize Universitaet zu Koeln, 50969 Koeln}\[0.7ex]
	and Stefan Naeher\
        {footnotesize  Max-Planck-Institut fuer Informatik,}\[-0.7ex]
   	{footnotesize 66123 Saarbruecken, Germany}\[0.7ex]}
        date{}
        maketitle
setcounter{page}{0}
thispagestyle{empty}
%%%%%%% Abstract %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
vspace*{2.2cm}
begin{abstract}
We describe an implementation of the Hopcroft and Tarjan planarity test and
embedding algorithm. The program tests the planarity of the input
graph and either constructs a combinatorial embedding (if the graph
is planar) or exhibits a Kuratowski subgraph (if the graph is non-planar).
end{abstract}
tableofcontents
N{1}{1}Introduction.
We descibe two procedures to test the planarity of a graph PB{|G}:
begin{center}
PB{&{bool} \{planar}(&{graph} ${}{AND}|G,{}$&{bool} \{embed}${}K%
\{false})$}
end{center}
and
begin{center}
PB{&{bool} \{planar}(&{graph} ${}{AND}|G,&{list}langle&{edge}%
rangle{}$ ${}{AND}|P,{}$&{bool} \{embed}${}K\{false})$}.
end{center}
Both take a directed graph PB{|G} and test it for planarity.
If the graph is planar and bidirected, i.e., for every edge of PB{|G} its
reversal is also in PB{|G}, and the argument PB{\{embed}} is true, then
they
also compute a combinatorial embedding of PB{|G} (by suitably reordering
its adjacency lists). If the graph PB{|G} is
non-planar then the first version of PB{\{planar}} only records that fact.
The second version in addition returns a subgraph of PB{|G} homeomorphic
to $K_{3,3}$ or $K_5$ (as a list PB{|P} of edges). For a planar graph
PB{|G} the running time of
both versions is linear (cf. section ref{Efficiency} for more
detailed information). For non-planar graphs PB{|G} the
first version runs in linear time but the second version runs in
quadratic time.
We are aware of the linear time algorithm of Williamson
cite{Williamson:Kuratowski} to find Kuratowski subgraphs but have
not implemented it.
The implementation of PB{\{planar}} is based on the LEDA platform of
combinatorial
and geometric computing cite{LEDA-Manual,Mehlhorn-Naeher:LEDA}. It is part of
the LEDA-distribution (available through anonymous ftp at cs.uni-sb.de). In
this document we describe the implementation of both versions of PB{%
\{planar}} and
a demo, and report on our experimental experience.
Procedure PB{\{planar}} is based on the
Hopcroft and Tarjan linear time planarity testing algorithm as
described in cite[section IV.10]{Me:book}. For the sequel we assume
knowledge of section IV.10 of cite{Me:book}. A revised version of that section
is included in this document (see section ref{reprint}) for the convenience
of the reader. Our procedure PB{\{planar}} differs from cite[section
IV.10]{Me:book}
in two respects: Firstly, it works for arbitrary directed graphs and
not only for biconnected
undirected graphs. To this end we augment the input graph by additional edges
to make it biconnected and bidirected. The augmentation does not destroy
planarity. Secondly, the embedding
phase follows the
presentation in cite{Mehlhorn-Mutzel:embedding}. We want to remark that the
description of the embedding phase given
in cite[section IV.10]{Me:book} is false.
The essential part of cite{Mehlhorn-Mutzel:embedding} is reprinted in
section ref{embedding}.
This document defines the files PB{$\{planar}.|h$}, PB{$\{planar}.|c$},
and PB{$\{demo}.|c$}.
PB{$\{planar}.|c$} contains the code for procedure PB{\{planar}}, PB{$%
\{demo}.|c$}
contains the code for a demo, and PB{$\{planar}.|h$} consists of the
declarations of procedure PB{\{planar}}.
The third file is defined in section ref{demo}, the structure of the first two
files
is as follows:
YB4X1:.{planar.h }X${}E{}$6
&{bool} \{planar}(&{graph} ${}{AND}|G,39{}$&{bool} \{embed}${}K%
\{false});{}$6
&{bool} \{planar}(&{graph} ${}{AND}|G,39&{list}langle&{edge}rangle{}$
${}{AND}|P,39{}$&{bool} \{embed}${}K\{false});{}$6
&{void} \{Make_biconnected_graph}(&{graph} ${}{AND}|G){}$;par
fi
M{2}
YB4X2:.{planar.c }X${}E{}$6
X3:includesX;6
X11:typedefs, global variables and class declarationsX;6
X9:auxiliary functionsX;6
X5:first version of PB{\{planar}}X;6
X4:second version of PB{\{planar}}X;par
fi
M{3}We include parts of LEDA (who would want to
work without it) cite{LEDA-Manual,Mehlhorn-Naeher:LEDA}.
We need stacks, graphs, and graph algorithms.
YB4X3:includesX${}E{}$6
8#&{include} .{<LEDA/stack.h>}6
8#&{include} .{<LEDA/graph.h>}6
8#&{include} .{<LEDA/graph_alg.h>}6
8#&{include} .{"planar.h"}par
A36.
Us2ET35.fi
M{4}The second version of PB{\{planar}} is easy to describe. We first test
the
planarity of PB{|G} using the first version.
If PB{|G} is planar then we are done. If PB{|G} is
non-planar then we cycle through the edges of PB{|G}. For every edge PB{|e}
of
PB{|G} we test the planarity of PB{$|G-|e$}. If PB{$|G-|e$} is planar
we add PB{|e} back in.
In this way we determine a minimal (with respect to set inclusion)
non-planar subgraph of PB{|G}, i.e., either a $K_5$ or a $K_{3,3}$.
YB4X4:second version of PB{\{planar}}X${}E{}$6
&{bool} \{planar}(&{graph} ${}{AND}|G,39&{list}langle&{edge}rangle{}$
${}{AND}|P,39{}$&{bool} \{embed}${}K\{false}){}$11226
${}{{}$16
&{if} ${}(\{planar}(|G,39\{embed})){}$15
&{return} \{true};C{ We work on a copy PB{|H} of PB{|G} since the
procedure alters PB{|G}; we link every vertex and edge of PB{|H} with its
original. For the vertices we also have the reverse links. }27
${}&{GRAPH}langle&{node},39&{edge}rangle{}$ |H;6
${}&{node_array}langle&{node}rangle{}$ \{link}(|G);6
&{node} |v;7
&{forall_nodes} ${}(|v,39|G){}$15
${}\{link}[|v]K|H.\{new_node}(|v){}$;C{ This requires some explanation.
PB{$|H.\{new_node}(|v)$} adds a new node to PB{|H}, returns the new
node, and makes PB{|v} the information associated with the new node. So the
statement creates a copy of PB{|v} and bidirectionally links it with PB{|v}
}27
&{edge} |e;7
&{forall_edges} ${}(|e,39|G){}$15
${}|H.\{new_edge}(\{link}[\{source}(|e)],39\{link}[\{target}(|e)],39%
|e){}$;C{ PB{\{link}[\{source}(|e)]} and PB{\{link}[\{target}(|e)]}
are the copies of PB{\{source}(|e)} and PB{\{target}(|e)} in PB{|H}.
The operation PB{$|H.\{new_edge}$} creates a new edge with these endpoints,
returns it, and makes PB{|e} the information of that edge. So the effect of
the loop is to make the edge set of PB{|H} a copy of the edge set of PB{|G}
and to let every edge of PB{|H} know its original. We can now determine a
minimal non-planar subgraph of PB{|H} }27
${}&{list}langle&{edge}rangle{}$ |L${}K|H.\{all_edges}(,);{}$6
&{edge} \{eh};7
&{forall} ${}(\{eh},39|L){}$5
${}{{}$16
${}|eK|H[\{eh}]{}$;SHC{ the edge in PB{|G} corresponding to PB{\{eh}}
}7
&{node} |x${}K\{source}(\{eh});{}$6
&{node} |y${}K\{target}(\{eh});{}$7
${}|H.\{del_edge}(\{eh});{}$6
&{if} (\{planar}(|H))15
${}|H.\{new_edge}(|x,39|y,39|e){}$;SHC{put a new version of PB{%
\{eh}} back in and establish the correspondence }26
4${}}{}$C{ PB{|H} is now a homeomorph of either $K_5$ or $K_{3,3}$. We
still need to translate back to PB{|G}. }26
${}|P.\{clear}(,);{}$6
&{forall_edges} ${}(\{eh},39|H){}$15
${}|P.\{append}(|H[\{eh}]);{}$26
&{return} \{false};6
4${}}{}$2par
U2.fi
M{5}The first version of PB{\{planar}} is also quite simple to describe.
Graphs with at most three
vertices are always planar. So assume that PB{|G} has more than three
vertices. We first add edges to PB{|G} to make it bidirected
and then add some more edges to make
it biconnected (of course, without destroying planarity). Then we test
the planarity of the extended graph and construct an embedding.
Since PB{\{planar}} alters the input graph, it works on a copy of it.
YB4X5:first version of PB{\{planar}}X${}E{}$6
&{bool} \{planar}(&{graph} ${}{AND}\{Gin},39{}$&{bool} \{embed}${}K%
\{false}{}$)C{ PB{\{Gin}} is a directed graph. PB{\{planar}} decides
whether PB{\{Gin}} is planar. If it is and PB{$\{embed}E\{true}$} then it
also computes a  combinatorial embedding of PB{\{Gin}} by suitably reordering
its adjacency lists. PB{\{Gin}} must be bidirected in that case. }116
${$ &{int} |n${}K\{Gin}.\{number_of_nodes}(,);{}$7
&{if} ${}(|nZT{3}){}$15
&{return} \{true};26
&{if} ${}(\{Gin}.\{number_of_edges}(,)>T{6}*|n-T{12}){}$15
&{return} \{false};C{ An undirected planar graph has at most $3n-6$ edges; a
directed graph may have twice as many }26
${}\{cout}LL.{"number of nodes and}).{ edges  "}LL|nLL.{"  "}%
LL\{Gin}.\{number_of_edges}(,);{}$6
\{newline};7
&{float} |T${}K\{used_time}(,);{}$7
X6:make PB{|G} a copy of PB{\{Gin}} and add edges to make PB{|G}
bidirectedX;6
X8:make PB{|G} biconnectedX;6
${}\{cout}LL.{"time to copy and to}).{ make bidirected and}).{
connected  "}LL\{used_time}(|T);{}$6
\{newline};6
X13:test planarityX;6
${}\{cout}LL.{"time to test planar}).{ity   "}LL\{used_time}(%
|T);{}$6
\{newline}; &{if} (\{embed}) ${$ &{if} (\{Gin_is_bidirected}) %
X26:construct embeddingX 6
&{else}15
${}\{error_handler}(T{2},39.{"sorry: can only emb}).{ed bidirected
graphs}).{"});{}$26
${}\{cout}LL.{"time to construct e}).{mbedding   "}LL\{used%
_time}(|T);{}$6
\{newline}; $}$ &{return} \{true}; $}{}$par
U2.fi
M{6}We make PB{|G} a copy of PB{\{Gin}} and bidirectionally link all
vertices and
edges. Then we add edges to PB{|G} to make it bidirected. In
PB{\{Gin_is_bidirected}} we record whether we needed to add edges.
YB4X6:make PB{|G} a copy of PB{\{Gin}} and add edges to make PB{|G}
bidirectedX${}E{}$6
$&{GRAPH}langle&{node},39&{edge}rangle{}$ |G;6
${}&{edge_array}langle&{edge}rangle{}$ \{companion_in_G}(\{Gin});6
${}&{node_array}langle&{node}rangle{}$ \{link}(\{Gin});6
&{bool} \{Gin_is_bidirected}${}K\{true};{}$7
${}{{}$16
&{node} |v;7
&{forall_nodes} ${}(|v,39\{Gin}){}$15
${}\{link}[|v]K|G.\{new_node}(|v){}$;SHC{bidirectional links }27
&{edge} |e;7
&{forall_edges} ${}(|e,39\{Gin}){}$15
${}\{companion_in_G}[|e]K|G.\{new_edge}(\{link}[\{source}(|e)],39%
\{link}[\{target}(|e)],39|e);{}$26
4${}}{}$26
X7:bidirect GX;par
U5.fi
M{7}We bidirect G. We first assign numbers to nodes and edges. We make sure
that
the two versions of the same undirected edge get the same number but versions
of distinct undirected edges get different numbers. Then we sort the edges
according to numbers. Finally we step through the sorted list of edges
and add
missing edges.
YB4X7:bidirect GX${}E{}$6
${}{{}$16
${}&{node_array}langle&{int}rangle{}$ \{nr}(|G);6
${}&{edge_array}langle&{int}rangle{}$ \{cost}(|G);6
&{int} \{cur_nr}${}KT{0};{}$6
&{int} |n${}K|G.\{number_of_nodes}(,);{}$6
&{node} |v;6
&{edge} |e;7
&{forall_nodes} ${}(|v,39|G){}$15
${}\{nr}[|v]K\{cur_nr}PP;{}$26
&{forall_edges} ${}(|e,39|G){}$15
${}\{cost}[|e]K((\{nr}[\{source}(|e)]<\{nr}[\{target}(|e)])?|n*%
\{nr}[\{source}(|e)]+\{nr}[\{target}(|e)]:|n*\{nr}[\{target}(|e)]+%
\{nr}[\{source}(|e)]);{}$26
${}|G.\{sort_edges}(\{cost});{}$7
${}&{list}langle&{edge}rangle{}$ |L${}K|G.\{all_edges}(,);{}$7
&{while} ${}(R|L.\{empty}(,)){}$5
${}{{}$16
${}|eK|L.\{pop}(,){}$;C{ check whether the first edge on PB{|L} is
equal to the reversal of PB{|e}. If so, delete it from PB{|L}, if not, add
the reversal to PB{|G} }6
&{if} ${}(R|L.\{empty}(,)W(\{source}(|e)E\{target}(|L.\{head}(,)))%
W(\{source}(|L.\{head}(,))E\{target}(|e))){}$15
${}|L.\{pop}(,);{}$26
&{else}5
${}{{}$16
${}|G.\{new_edge}(\{target}(|e),39\{source}(|e));{}$6
${}\{Gin_is_bidirected}K\{false};{}$6
4${}}{}$26
4${}}{}$26
4${}}{}$2par
U6.fi
N{1}{8}Making the Graph Biconnected.
We make PB{|G} biconnected. We first make it connected by linking all
roots. Assume that is done. Let $a$ be any articulation
point and let $u$ and $v$ be neighbors of $a$ belonging to different
biconnected components. Then there are embeddings of the two components
with the edges ${u,a}$ and ${v,a}$ on the boundary of the unbounded
face. Hence we may add the edge ${u,v}$ without destroying planarity.
Proceeding in this way we make PB{|G}
biconnected.
In PB{\{Make_biconnected_graph}} we change the graph while working on it.
But we modify only
those adjacency lists that will not be touched later.
We need the biconnected version of PB{|G} (PB{|G} will be further modified
during the planarity test) in order to construct the planar embedding. So we
store it as a graph PB{|H}. For every edge of PB{\{Gin}} and PB{|G} we
store a link to
its copy in PB{|H}. In addition every edge of PB{|H} is made to know its
reversal.
YB4X8:make PB{|G} biconnectedX${}E{}$6
\{Make_biconnected_graph}(|G);6
X12:make PB{|H} a copy of PB{|G}X;par
U5.fi
M{9}We give the details of the procedure PB{\{Make_biconnected_graph}}. We
first make PB{|G}
connected by linking all roots of the DFS-forest. In a second step we make
PB{|G} biconnected.
YB4X9:auxiliary functionsX${}E{}$6
&{void} \{Make_biconnected_graph}(&{graph} ${}{AND}|G){}$11226
${}{{}$16
&{node} |v;6
${}&{node_array}langle&{bool}rangle{}$ ${}\{reached}(|G,39%
\{false});{}$6
&{node} |u${}K|G.\{first_node}(,);{}$7
&{forall_nodes} ${}(|v,39|G){}$5
${}{{}$16
&{if} ${}(R\{reached}[|v]){}$5
${}{{}$C{ explore the connected component with root PB{|v} }16
${}\{DFS}(|G,39|v,39\{reached});{}$6
&{if} ${}(|uI|v){}$5
${}{{}$C{ link PB{|v}'s component to the first component }16
${}|G.\{new_edge}(|u,39|v);{}$6
${}|G.\{new_edge}(|v,39|u);{}$6
4${}}{}$SHC{end if }26
4${}}{}$SHC{ end not reached }26
4${}}{}$SHC{end forall }C{ PB{|G} is now connected. We next make it
biconnected. }26
&{forall_nodes} ${}(|v,39|G){}$15
${}\{reached}[|v]K\{false};{}$27
${}&{node_array}langle&{int}rangle{}$ \{dfsnum}(|G);6
${}&{node_array}langle&{node}rangle{}$ ${}\{parent}(|G,39\{nil});{}$6
&{int} \{dfs_count}${}KT{0};{}$6
${}&{node_array}langle&{int}rangle{}$ \{lowpt}(|G);7
${}\{dfs_in_make_biconnected_graph}(|G,39|G.\{first_node}(,),39%
\{dfs_count},39\{reached},39\{dfsnum},39\{lowpt},39\{parent});{}$6
4${}}{}$SHC{ end PB{\{Make_biconnected_graph}} }2par
As10, 15, 16, 18ETs27.
U2.fi
M{10}We still have to give the procedure PB{\{dfs_in_make_biconnected%
_graph}}. It determines
articulation points and adds appropriate edges whenever it discovers one.
For a proof of correctness we refer the reader to
cite[section IV.6]{Me:book}.
YB4X9:auxiliary functionsX${}mathrel+E{}$6
&{void} \{dfs_in_make_biconnected_graph}(&{graph} ${}{AND}|G,39{}$%
&{node} |v${},39{}$&{int} ${}{AND}\{dfs_count},39&{node_array}langle%
&{bool}rangle{}$ ${}{AND}\{reached},3{-1}39&{node_array}langle&{int}%
rangle{}$ ${}{AND}\{dfsnum},39&{node_array}langle&{int}rangle{}$ ${}{%
AND}\{lowpt},39&{node_array}langle&{node}rangle{}$ ${}{AND}%
\{parent}){}$11226
${}{{}$16
&{node} |w;6
&{edge} |e;7
${}\{dfsnum}[|v]K\{dfs_count}PP;{}$6
${}\{lowpt}[|v]K\{dfsnum}[|v];{}$6
${}\{reached}[|v]K\{true};{}$6
&{if} ${}(R|G.\{first_adj_edge}(|v)){}$15
&{return};SHC{no children }27
&{node} |u${}K\{target}(|G.\{first_adj_edge}(|v)){}$;SHC{first child
}7
&{forall_adj_edges} ${}(|e,39|v){}$5
${}{{}$16
${}|wK\{target}(|e);{}$6
&{if} ${}(R\{reached}[|w]){}$5
${}{{}$C{ e is a tree edge }16
${}\{parent}[|w]K|v;{}$6
${}\{dfs_in_make_biconnected_graph}(|G,39|w,39\{dfs_count},39%
\{reached},39\{dfsnum},39\{lowpt},39\{parent});{}$6
&{if} ${}(\{lowpt}[|w]E\{dfsnum}[|v]){}$5
${}{{}$C{ PB{|v} is an articulation point. We now add an edge. If PB{|w}
is the first child and PB{|v} has a parent then we connect PB{|w} and PB{%
\{parent}[|v]}, if PB{|w} is a first child and PB{|v} has no parent then
we do nothing. If PB{|w} is not the first child then we connect PB{|w} to
the first child. The net effect of all of this is to link all children of an
articulation point to the first child and the first child to the parent (if it
exists) }16
&{if} ${}(|wE|uW\{parent}[|v]){}$5
${}{{}$16
${}|G.\{new_edge}(|w,39\{parent}[|v]);{}$6
${}|G.\{new_edge}(\{parent}[|v],39|w);{}$6
4${}}{}$26
&{if} ${}(|wI|u){}$5
${}{{}$16
${}|G.\{new_edge}(|u,39|w);{}$6
${}|G.\{new_edge}(|w,39|u);{}$6
4${}}{}$26
4${}}{}$SHC{ end if lowpt = dfsnum }26
${}\{lowpt}[|v]K\{Min}(\{lowpt}[|v],39\{lowpt}[|w]);{}$6
4${}}{}$SHC{end tree edge }26
&{else}15
${}\{lowpt}[|v]K\{Min}(\{lowpt}[|v],39\{dfsnum}[|w]){}$;SHC{non tree
edge }26
4${}}{}$SHC{ end forall }26
4${}}{}$SHC{end dfs }2par
fi
M{11}Because we use the function PB{\{dfs_in_make_biconnected_graph}}
before its declaration,
let's add it to the global declarations.
YB4X11:typedefs, global variables and class declarationsX${}E{}$6
&{void} \{dfs_in_make_biconnected_graph}(&{graph} ${}{AND}|G,39{}$%
&{node} |v${},39{}$&{int} ${}{AND}\{dfs_count},39&{node_array}langle%
&{bool}rangle{}$ ${}{AND}\{reached},3{-1}39&{node_array}langle&{int}%
rangle{}$ ${}{AND}\{dfsnum},39&{node_array}langle&{int}rangle{}$ ${}{%
AND}\{lowpt},39&{node_array}langle&{node}rangle{}$ ${}{AND}%
\{parent}){}$;par
As14, 17ETs20.
U2.fi
M{12}We make PB{|H} a copy of PB{|G} and create bidirectional links
between the
vertices and edges of PB{|G} and PB{|H}.
Also, each edge in PB{\{Gin}} gets a link to its copy in PB{|H} and every
edge
of PB{|H} gets to know its reversal. More precisely, PB{$|H[|G[|v]]K%
|v$} for every
node PB{|v} of PB{|G} and PB{$|H[|G[|e]]K|e$} for every edge PB{|e}
of PB{|G}, and
PB{\{companion_in_H}[\{ein}]} is the edge in PB{|H} corresponding to the
edge
PB{\{ein}} of PB{\{Gin}} for every edge PB{\{ein}} of PB{\{Gin}}.
Finally, if PB{$|eK(|u,|v)$} is
an edge of PB{|H} then PB{$\{reversal}[|e]K(|v,|u)$}.
YB4X12:make PB{|H} a copy of PB{|G}X${}E{}$6
$&{GRAPH}langle&{node},39&{edge}rangle{}$ |H;6
${}&{edge_array}langle&{edge}rangle{}$ \{companion_in_H}(\{Gin});7
${}{{}$16
&{node} |v;7
&{forall_nodes} ${}(|v,39|G){}$15
${}|G.\{assign}(|v,39|H.\{new_node}(|v));{}$27
&{edge} |e;7
&{forall_edges} ${}(|e,39|G){}$15
${}|G.\{assign}(|e,39|H.\{new_edge}(|G[\{source}(|e)],39|G[%
\{target}(|e)],39|e));{}$27
&{edge} \{ein};7
&{forall_edges} ${}(\{ein},39\{Gin}){}$15
${}\{companion_in_H}[\{ein}]K|G[\{companion_in_G}[\{ein}]];{}$26
4${}}{}$27
${}&{edge_array}langle&{edge}rangle{}$ \{reversal}(|H);7
${}\{compute_correspondence}(|H,39\{reversal}){}$;par
U8.fi
N{1}{13}The Planarity Test.
We are now ready for the planarity test proper. We follow
cite[page 95]{Me:book}. We first compute PB{\{dfsnumber}}s and PB{%
\{parent}}s, we
delete all forward edges and all reversals of tree edges, and we
reorder the adjaceny lists as described in cite[page 101]{Me:book}.
We then test the strong planarity.
The array PB{\{alpha}} is needed for the embedding process. It
records the placement of the subsegments.
YB4X13:test planarityX${}E{}$6
$&{node_array}langle&{int}rangle{}$ \{dfsnum}(|G);6
${}&{node_array}langle&{node}rangle{}$ ${}\{parent}(|G,39\{nil});{}$7
${}\{reorder}(|G,39\{dfsnum},39\{parent});{}$7
${}&{edge_array}langle&{int}rangle{}$ ${}\{alpha}(|G,39T{0});{}$7
${}{{}$16
${}&{list}langle&{int}rangle{}$ \{Att};7
${}\{alpha}[|G.\{first_adj_edge}(|G.\{first_node}(,))]K\{left};{}$6
&{if} ${}(R\{strongly_planar}(|G.\{first_adj_edge}(|G.\{first_node}(%
,)),39|G,39\{Att},39\{alpha},39\{dfsnum},39\{parent})){}$15
&{return} \{false};26
4${}}{}$2par
U5.fi
M{14}We need two global constants PB{\{left}} and PB{\{right}}.
YB4X11:typedefs, global variables and class declarationsX${}mathrel+E{}$%
6
&{const} &{int} \{left}${}KT{1};{}$6
&{const} &{int} \{right}${}KT{2}{}$;par
fi
M{15}We give the details of the procedure PB{\{reorder}}. It first performs
DFS
to compute PB{\{dfsnum}}, PB{\{parent}}, PB{\{lowpt1}} and PB{%
\{lowpt2}}, and the list PB{\{Del}}
of all forward edges and all reversals of tree edges.
It then deletes the edges in PB{\{Del}} and finally it
reorders the edges.
YB4X9:auxiliary functionsX${}mathrel+E{}$6
&{void} \{reorder}(&{graph} ${}{AND}|G,39&{node_array}langle&{int}%
rangle{}$ ${}{AND}\{dfsnum},39&{node_array}langle&{node}rangle{}$ ${}{%
AND}\{parent}){}$11226
${}{{}$16
&{node} |v;6
${}&{node_array}langle&{bool}rangle{}$ ${}\{reached}(|G,39%
\{false});{}$6
&{int} \{dfs_count}${}KT{0};{}$6
${}&{list}langle&{edge}rangle{}$ \{Del};6
${}&{node_array}langle&{int}rangle{}$ \{lowpt1}(|G)${},{}$ \{lowpt2}(%
|G);7
${}\{dfs_in_reorder}(\{Del},39|G.\{first_node}(,),39\{dfs_count},%
39\{reached},39\{dfsnum},39\{lowpt1},39\{lowpt2},39\{parent}){}$;C{
remove forward and reversals of tree edges }7
&{edge} |e;7
&{forall} ${}(|e,39\{Del}){}$15
${}|G.\{del_edge}(|e){}$;C{ we now reorder adjacency lists as described in
cite[page 101]{Me:book} }27
&{node} |w;6
${}&{edge_array}langle&{int}rangle{}$ \{cost}(|G);7
&{forall_edges} ${}(|e,39|G){}$5
${}{{}$16
${}|vK\{source}(|e);{}$6
${}|wK\{target}(|e);{}$6
${}\{cost}[|e]K((\{dfsnum}[|w]<\{dfsnum}[|v])?T{2}*\{dfsnum}[|w]:((%
\{lowpt2}[|w]G\{dfsnum}[|v])?T{2}*\{lowpt1}[|w]:T{2}*\{lowpt1}[|w]+%
T{1}));{}$6
4${}}{}$26
${}|G.\{sort_edges}(\{cost});{}$6
4${}}{}$2par
fi
M{16}We still have to give the procedure PB{\{dfs_in_reorder}}. It's a bit
long but standard.
YB4X9:auxiliary functionsX${}mathrel+E{}$6
&{void} \{dfs_in_reorder}${}(&{list}langle&{edge}rangle{}$ ${}{AND}%
\{Del},39{}$&{node} |v${},39{}$&{int} ${}{AND}\{dfs_count},39&{node%
_array}langle&{bool}rangle{}$ ${}{AND}\{reached},3{-1}39&{node_array}%
langle&{int}rangle{}$ ${}{AND}\{dfsnum},39&{node_array}langle&{int}%
rangle{}$ ${}{AND}\{lowpt1},39&{node_array}langle&{int}rangle{}$ ${}{%
AND}\{lowpt2},3{-1}39&{node_array}langle&{node}rangle{}$ ${}{AND}%
\{parent}){}$11226
${}{{}$16
&{node} |w;6
&{edge} |e;7
${}\{dfsnum}[|v]K\{dfs_count}PP;{}$6
${}\{lowpt1}[|v]K\{lowpt2}[|v]K\{dfsnum}[|v];{}$6
${}\{reached}[|v]K\{true};{}$6
&{forall_adj_edges} ${}(|e,39|v){}$5
${}{{}$16
${}|wK\{target}(|e);{}$6
&{if} ${}(R\{reached}[|w]){}$5
${}{{}$C{ e is a tree edge }16
${}\{parent}[|w]K|v;{}$6
${}\{dfs_in_reorder}(\{Del},39|w,39\{dfs_count},39\{reached},39%
\{dfsnum},39\{lowpt1},39\{lowpt2},39\{parent});{}$6
${}\{lowpt1}[|v]K\{Min}(\{lowpt1}[|v],39\{lowpt1}[|w]);{}$6
4${}}{}$SHC{end tree edge }26
&{else}5
${}{{}$16
${}\{lowpt1}[|v]K\{Min}(\{lowpt1}[|v],39\{dfsnum}[|w]){}$;SHC{ no
effect for forward edges }6
&{if} ${}((\{dfsnum}[|w]G\{dfsnum}[|v])V|wE\{parent}[|v]{}$)C{
forward edge or reversal of tree edge }16
${}\{Del}.\{append}(|e);{}$26
4${}}{}$SHC{end non-tree edge }26
4${}}{}$SHC{ end forall }C{ we know PB{\{lowpt1}[|v]} at this point and
now make a second pass over all      adjacent edges of PB{|v} to compute PB{%
\{lowpt2}} }26
&{forall_adj_edges} ${}(|e,39|v){}$5
${}{{}$16
${}|wK\{target}(|e);{}$6
&{if} ${}(\{parent}[|w]E|v){}$5
${}{{}$C{ tree edge }16
&{if} ${}(\{lowpt1}[|w]I\{lowpt1}[|v]){}$15
${}\{lowpt2}[|v]K\{Min}(\{lowpt2}[|v],39\{lowpt1}[|w]);{}$26
${}\{lowpt2}[|v]K\{Min}(\{lowpt2}[|v],39\{lowpt2}[|w]);{}$6
4${}}{}$SHC{end tree edge }26
&{else}SHC{ all other edges }6
&{if} ${}(\{lowpt1}[|v]I\{dfsnum}[|w]){}$15
${}\{lowpt2}[|v]K\{Min}(\{lowpt2}[|v],39\{dfsnum}[|w]);{}$26
4${}}{}$SHC{end forall }26
4${}}{}$SHC{end dfs }2par
fi
M{17}Because we use the function PB{\{dfs_in_reorder}} before its
declaration,
let's add it to the global declarations.
YB4X11:typedefs, global variables and class declarationsX${}mathrel+E{}$%
6
&{void} \{dfs_in_reorder}${}(&{list}langle&{edge}rangle{}$ ${}{AND}%
\{Del},39{}$&{node} |v${},39{}$&{int} ${}{AND}\{dfs_count},39&{node%
_array}langle&{bool}rangle{}$ ${}{AND}\{reached},3{-1}39&{node_array}%
langle&{int}rangle{}$ ${}{AND}\{dfsnum},39&{node_array}langle&{int}%
rangle{}$ ${}{AND}\{lowpt1},39&{node_array}langle&{int}rangle{}$ ${}{%
AND}\{lowpt2},3{-1}39&{node_array}langle&{node}rangle{}$ ${}{AND}%
\{parent}){}$;par
fi
M{18}We now come to the heart of the planarity test: procedure PB{\{strongly%
_planar}}.
It takes a tree edge $e0 = (x,y)$ and tests whether
the segment $S(e0)$ is strongly planar. If  successful it returns  (in PB{%
\{Att}}) the
ordered list of attachments of $S(e0)$ (excluding $x$); high DFS-numbers are
at the front of the list. In PB{\{alpha}} it
records the placement of the subsegments.
PB{\{strongly_planar}} operates in three phases. It first constructs the
cycle $C(e0)$
underlying the segment $S(e0)$. It then constructs the interlacing graph for
the
segments emanating from the spine of the cycle. If this graph is non-bipartite
then the segment $S(e0)$ is non-planar. If it is bipartite then the segment is
planar. In this case the third phase checks whether the segment is strongly
planar and, if so, computes its list of attachments.
YB4X9:auxiliary functionsX${}mathrel+E{}$6
&{bool} \{strongly_planar}(&{edge} \{e0}${},39{}$&{graph} ${}{AND}|G,%
39&{list}langle&{int}rangle{}$ ${}{AND}\{Att},39&{edge_array}langle%
&{int}rangle{}$ ${}{AND}\{alpha},3{-1}39&{node_array}langle&{int}%
rangle{}$ ${}{AND}\{dfsnum},39&{node_array}langle&{node}rangle{}$ ${}{%
AND}\{parent}){}$11226
${}{{}$16
X19:determine the cycle $C(e0)$X;6
X21:process all edges leaving the spineX;6
X25:test strong planarity and compute PB{\{Att}}X;6
&{return} \{true};6
4${}}{}$2par
fi
M{19}We determine the cycle $C(e0)$ by following first edges until a back
edge is encountered. PB{\{wk}} will be the last node on the tree path and %
PB{\{w0}}
is the destination of the back edge. This agrees with the
notation of cite{Me:book}.
YB4X19:determine the cycle $C(e0)$X${}E{}$6
&{node} |x${}K\{source}(\{e0});{}$6
&{node} |y${}K\{target}(\{e0});{}$6
&{edge} |e${}K|G.\{first_adj_edge}(|y);{}$6
&{node} \{wk}${}K|y;{}$7
&{while} ${}(\{dfsnum}[\{target}(|e)]>\{dfsnum}[\{wk}]{}$)SHC{ e is a
tree edge }6
${}{{}$16
${}\{wk}K\{target}(|e);{}$6
${}|eK|G.\{first_adj_edge}(\{wk});{}$6
4${}}{}$27
&{node} \{w0}${}K\{target}(|e){}$;par
U18.fi
M{20}The second phase of PB{\{strongly_planar}} constructs the connected
components of
the interlacing graph of the segments emananating from the the spine of the
cycle $C(e0)$. We call a connected component a {em block}. For each block
we store the segments comprising its left and right side (lists
PB{\{Lseg}} and PB{\{Rseg}} contain the edges
defining these segments) and the ordered list of attachments of the segments
in the block; lists PB{\{Latt}} and PB{\{Ratt}} contain the DFS-numbers of
the
attachments; high DFS-numbers are at the front of the list. Blocks are
so important that we make them a class.
We need the following operations on blocks.
The constructor takes an edge and a list of attachments and creates
a block having the edge as the only segment in its left side.
PB{\{flip}} interchanges the two sides of a block.
PB{\{head_of_Latt}} and PB{\{head_of_Ratt}} return the first elements
on PB{\{Latt}} and PB{\{Ratt}} respectively
and PB{\{Latt_empty}} and PB{\{Ratt_empty}} check these lists for
emptyness.
PB{\{left_interlace}} checks whether the block interlaces with the left side
of the topmost block of
stack PB{|S}. PB{\{right_interlace}} does the same for the right side.
PB{\{combine}} combines the block with another block PB{\{Bprime}} by
simply concatenating all
lists.
PB{\{clean}} removes the attachment PB{|w} from the block PB{|B} (it is
guaranteed to be the
first attachment of PB{|B}). If the block becomes empty then it records the
placement of all segments in the block in the array PB{\{alpha}} and returns
true.
Otherwise it returns false.
PB{\{add_to_Att}} first makes sure that the right side has no attachment
above PB{\{w0}}
(by
flipping); when PB{\{add_to_Att}} is called at least one side has no
attachment above PB{\{w0}}.
PB{\{add_to_Att}} then adds the lists PB{\{Ratt}} and PB{\{Latt}} to
the output list PB{\{Att}}
and records the placement of all segments in the block in PB{\{alpha}}.
We advise the reader to only skim the rest of the section at this
point and to come back to it when the procedures are first used.
YB4X11:typedefs, global variables and class declarationsX${}mathrel+E{}$%
6
&{class} &{block} ${}{{}$16
4&{private}:5
${}&{list}langle&{int}rangle{}$ \{Latt}${},{}$ \{Ratt};SHC{list of
attachments }6
${}&{list}langle&{edge}rangle{}$ \{Lseg}${},{}$ \{Rseg};SHC{list of
segments represented by their defining edges }7
4&{public}:5
&{block}(&{edge} |e${},39&{list}langle&{int}rangle{}$ ${}{AND}|A){}$%
11226
${}{{}$16
${}\{Lseg}.\{append}(|e);{}$6
${}\{Latt}.\{conc}(|A){}$;SHC{ the other two lists are empty }6
4${}}{}$27
${}CM&{block}{}$(,)5
${}{,}{}$7
&{void} \{flip}(,)11226
${}{{}$16
${}&{list}langle&{int}rangle{}$ \{ha};6
${}&{list}langle&{edge}rangle{}$ \{he};C{ we first interchange PB{%
\{Latt}} and PB{\{Ratt}} and then PB{\{Lseg}} and PB{\{Rseg}} }7
${}\{ha}.\{conc}(\{Ratt}){}$;5
${}\{Ratt}.\{conc}(\{Latt}){}$;5
${}\{Latt}.\{conc}(\{ha});{}$6
${}\{he}.\{conc}(\{Rseg}){}$;5
${}\{Rseg}.\{conc}(\{Lseg}){}$;5
${}\{Lseg}.\{conc}(\{he});{}$6
4${}}{}$27
&{int} \{head_of_Latt}(,)5
${}{{}$5
1&{return} ${}\{Latt}.\{head}(,){}$;5
${}}{}$27
&{bool} \{empty_Latt}(,)5
${}{{}$5
1&{return} ${}\{Latt}.\{empty}(,){}$;5
${}}{}$27
&{int} \{head_of_Ratt}(,)5
${}{{}$5
1&{return} ${}\{Ratt}.\{head}(,){}$;5
${}}{}$27
&{bool} \{empty_Ratt}(,)5
${}{{}$5
1&{return} ${}\{Ratt}.\{empty}(,){}$;5
${}}{}$27
&{bool} \{left_interlace}${}(&{stack}langle{}$&{block} ${}{*}rangle{}$
${}{AND}|S){}$11226
${}{{}$C{ check for interlacing with the left side of the topmost block of %
PB{|S} }16
&{if} ${}(\{Latt}.\{empty}(,)){}$15
${}\{error_handler}(T{1},39.{"Latt is never empty}).{"});{}$26
&{if} ${}(R|S.\{empty}(,)WR((|S.\{top}(,))MG\{empty_Latt}(,))W%
\{Latt}.\{tail}(,)<(|S.\{top}(,))MG\{head_of_Latt}(,)){}$15
&{return} \{true};26
&{else}15
&{return} \{false};26
4${}}{}$27
&{bool} \{right_interlace}${}(&{stack}langle{}$&{block} ${}{*}rangle{}$
${}{AND}|S){}$11226
${}{{}$C{ check for interlacing with the right side of the topmost block of %
PB{|S} }16
&{if} ${}(\{Latt}.\{empty}(,)){}$15
${}\{error_handler}(T{1},39.{"Latt is never empty}).{"});{}$26
&{if} ${}(R|S.\{empty}(,)WR((|S.\{top}(,))MG\{empty_Ratt}(,))W%
\{Latt}.\{tail}(,)<(|S.\{top}(,))MG\{head_of_Ratt}(,)){}$15
&{return} \{true};26
&{else}15
&{return} \{false};26
4${}}{}$27
&{void} \{combine}(&{block} ${}{*}{AND}\{Bprime}){}$11226
${}{{}$C{ add block Bprime to the rear of PB{$this$} block }16
${}\{Latt}.\{conc}(\{Bprime}MG\{Latt});{}$6
${}\{Ratt}.\{conc}(\{Bprime}MG\{Ratt});{}$6
${}\{Lseg}.\{conc}(\{Bprime}MG\{Lseg});{}$6
${}\{Rseg}.\{conc}(\{Bprime}MG\{Rseg});{}$6
&{delete} (\{Bprime});6
4${}}{}$27
&{bool} \{clean}(&{int} \{dfsnum_w}${},39&{edge_array}langle&{int}%
rangle{}$ ${}{AND}\{alpha},39&{node_array}langle&{int}rangle{}$ ${}{%
AND}\{dfsnum}){}$11226
${}{{}$C{ remove all attachments to PB{|w}; there may be several }16
&{while} ${}(R\{Latt}.\{empty}(,)W\{Latt}.\{head}(,)E\{dfsnum%
_w}){}$15
${}\{Latt}.\{pop}(,);{}$26
&{while} ${}(R\{Ratt}.\{empty}(,)W\{Ratt}.\{head}(,)E\{dfsnum%
_w}){}$15
${}\{Ratt}.\{pop}(,);{}$26
&{if} ${}(R\{Latt}.\{empty}(,)VR\{Ratt}.\{empty}(,)){}$15
&{return} \{false};C{PB{\{Latt}} and PB{\{Ratt}} are empty; we record
the placement of the subsegments in PB{\{alpha}}. }27
&{edge} |e;7
&{forall} ${}(|e,39\{Lseg}){}$15
${}\{alpha}[|e]K\{left};{}$26
&{forall} ${}(|e,39\{Rseg}){}$15
${}\{alpha}[|e]K\{right};{}$26
&{return} \{true};6
4${}}{}$27
&{void} \{add_to_Att}${}(&{list}langle&{int}rangle{}$ ${}{AND}\{Att},%
39{}$&{int} \{dfsnum_w0}${},39&{edge_array}langle&{int}rangle{}$ ${}{%
AND}\{alpha},3{-1}39&{node_array}langle&{int}rangle{}$ ${}{AND}%
\{dfsnum}){}$11226
${}{{}$C{ add the block to the rear of PB{\{Att}}. Flip if necessary }16
&{if} ${}(R\{Ratt}.\{empty}(,)W\{head_of_Ratt}(,)>\{dfsnum_w0}){}$%
15
\{flip}(,);26
${}\{Att}.\{conc}(\{Latt});{}$6
${}\{Att}.\{conc}(\{Ratt}){}$;C{ This needs some explanation. Note that %
PB{\{Ratt}} is either empty or ${w0}$. Also if PB{\{Ratt}} is non-empty
then all subsequent sets are contained in ${w0}$. So we indeed compute an
ordered set of attachments. }7
&{edge} |e;7
&{forall} ${}(|e,39\{Lseg}){}$15
${}\{alpha}[|e]K\{left};{}$26
&{forall} ${}(|e,39\{Rseg}){}$15
${}\{alpha}[|e]K\{right};{}$26
4${}}{}$226
${}}{}$;par
fi
M{21}We process the edges leaving the spine of $S(e0)$ starting at node PB{%
\{wk}}
and working backwards. The interlacing graph of the segments emanating from
the cycle is represented as a stack PB{|S} of blocks.
YB4X21:process all edges leaving the spineX${}E{}$6
&{node} |w${}K\{wk};{}$6
${}&{stack}langle{}$&{block} ${}{*}rangle{}$ |S;7
&{while} ${}(|wI|x){}$5
${}{{}$16
&{int} \{count}${}KT{0};{}$7
&{forall_adj_edges} ${}(|e,39|w){}$5
${}{{}$16
${}\{count}PP;{}$6
&{if} ${}(\{count}IT{1}{}$)SHC{no action for first edge }6
${}{{}$16
X22:test recursivelyX;6
X23:update stack PB{|S} of attachmentsX;6
4${}}{}$SHC{ end if }26
4${}}{}$SHC{end forall }26
X24:prepare for next iterationX;6
${}|wK\{parent}[|w];{}$6
4${}}{}$SHC{end while }2par
U18.fi
M{22}Let $e$ be any edge leaving the spine. We need to test whether
$S(e)$ is strongly planar and if so compute its list PB{|A} of attachments.
If $e$ is a tree edge we call our procedure recursively and if $e$ is a
back edge then $S(e)$ is certainly strongly planar and PB{\{target}(|e)} is
the only attachment. If we detect non-planarity we return flase and free
the storage allocated for the blocks of stack PB{|S}.
YB4X22:test recursivelyX${}E{}$6
$&{list}langle&{int}rangle{}$ |A;7
&{if} ${}(\{dfsnum}[|w]<\{dfsnum}[\{target}(|e)]){}$5
${}{{}$C{ tree edge }16
&{if} ${}(R\{strongly_planar}(|e,39|G,39|A,39\{alpha},39\{dfsnum},%
39\{parent})){}$5
${}{{}$16
&{while} ${}(R|S.\{empty}(,)){}$15
&{delete} ${}(|S.\{pop}(,));{}$26
&{return} \{false};6
4${}}{}$26
4${}}{}$26
&{else}15
${}|A.\{append}(\{dfsnum}[\{target}(|e)]){}$;SHC{ a back edge }2par
U21.fi
M{23}The list PB{|A} contains the ordered list of attachments of segment
$S(e)$. We create an new block consisting only of segment $S(e)$ (in its
$L$-part) and then combine this block with the topmost block of stack PB{|S}
as
long as
there is interlacing. We check for interlacing with the $L$-part. If there
is interlacing then we flip the two sides of the topmost block. If there
is still interlacing with the left side then the interlacing graph is
non-bipartite and
we declare the graph non-planar (and also free the storage allocated
for the blocks). Otherwise we check for interlacing with
the R-part. If there is interlacing then we combine PB{|B} with the topmost
block and repeat the process with the new topmost block. If there is no
interlacing then we push block PB{|B} onto PB{|S}.
YB4X23:update stack PB{|S} of attachmentsX${}E{}$6
&{block} ${}{*}|BK{}$&{new} &{block} ${}(|e,39|A);{}$7
&{while} (\{true})5
${}{{}$16
&{if} ${}(|BMG\{left_interlace}(|S)){}$15
${}(|S.\{top}(,))MG\{flip}(,);{}$26
&{if} ${}(|BMG\{left_interlace}(|S)){}$5
${}{{}$16
&{delete} (|B);6
&{while} ${}(R|S.\{empty}(,)){}$15
&{delete} ${}(|S.\{pop}(,));{}$26
&{return} \{false};6
4${}}{}$26
;6
&{if} ${}(|BMG\{right_interlace}(|S)){}$15
${}|BMG\{combine}(|S.\{pop}(,));{}$26
&{else}15
&{break};26
4${}}{}$SHC{end while }26
${}|S.\{push}(|B){}$;par
U21.fi
M{24}We have now processed all edges emanating from vertex PB{|w}. Before
starting to
process edges emanating from vertex PB{\{parent}[|w]} we remove PB{%
\{parent}[|w]} from
the list of attachments of the topmost block of stack PB{|S}. If this block
becomes empty then we pop it from the stack and record the placement for all
segments in the block in array PB{\{alpha}}.
YB4X24:prepare for next iterationX${}E{}$6
&{while} ${}(R|S.\{empty}(,)W(|S.\{top}(,))MG\{clean}(\{dfsnum}[%
\{parent}[|w]],39\{alpha},39\{dfsnum})){}$15
&{delete} ${}(|S.\{pop}(,)){}$;2par
U21.fi
M{25}We test the strong planarity of the segment $S(e0)$.
We know at this point that the
interlacing graph is bipartite. Also for each of its connected components the
corresponding block on stack PB{|S} contains the list of attachments below %
PB{|x}.
Let PB{|B} be the topmost block of PB{|S}. If both sides of PB{|B} have
an attachment
above PB{\{w0}} then $S(e0)$ is not strongly planar. We free the storage
allocated for
the blocks and return false. Otherwise (cf. procedure
PB{\{add_to_Att}}) we first make sure that the right side of PB{|B}
attaches only to PB{\{w0}}
(if at all) and then add the two sides of PB{|B} to the output list PB{%
\{Att}}. We also
record the placements of the subsegments in PB{\{alpha}}.
YB4X25:test strong planarity and compute PB{\{Att}}X${}E{}$6
$\{Att}.\{clear}(,);{}$6
&{while} ${}(R|S.\{empty}(,)){}$5
${}{{}$16
&{block} ${}{*}|BK|S.\{pop}(,);{}$7
&{if} ${}(R(|BMG\{empty_Latt}(,))WR(|BMG\{empty_Ratt}(,))W(|B%
MG\{head_of_Latt}(,)>\{dfsnum}[\{w0}])W(|BMG\{head_of_Ratt}(,)>%
\{dfsnum}[\{w0}])){}$5
${}{{}$16
&{delete} (|B);6
&{while} ${}(R|S.\{empty}(,)){}$15
&{delete} ${}(|S.\{pop}(,));{}$26
&{return} \{false};6
4${}}{}$26
${}|BMG\{add_to_Att}(\{Att},39\{dfsnum}[\{w0}],39\{alpha},39%
\{dfsnum});{}$6
&{delete} (|B);6
4${}}{}$SHC{end while }C{ Let's not forget (as the book does) that $w0$ is
an attachment of $S(e0)$ except if $w0 = x$. }26
&{if} ${}(\{w0}I|x){}$15
${}\{Att}.\{append}(\{dfsnum}[\{w0}]){}$;2par
U18.fi
N{1}{26}Constructing the Embedding.    label{embedding}
%%%%%%%%%%%%%%%%%% einbinden von bildern mit Unterschrift %%%%%%%%%%%%%
newcommand{bild}[2]{
begin{figure}[htb]
begin{center}
input{#1.tex}
end{center}
caption{{#2}label{#1}}
end{figure}
}
%%%%%  wird so benutzt: bild{<label>}{<caption>}  %%%%%%%%%%%%%%%%%%%%
%%%%%  z.B. bild{part}{A part of the augmented segment tree structure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
newtheorem{theorem}{Theorem}
We now discuss how the planarity testing algorithm can be extended
so that it also computes a planar map.
Consider a segment $S(e_0)=C+S(e_1)+ldots +S(e_m)$ consisting of
cycle $C$ and emanating segments $S(e_1),ldots ,S(e_m)$ and
recall that the proofs of Lemmas 8 and 9 describe how
the embeddings of the $S(e_i)$'s have to be combined to yield a
canonical embedding of $S(e_0)$.
Our goal is to turn these proofs into an efficient algorithm.
The proofs of Lemmas 8 and 9 demonstrate two things:
begin{itemize}
item How to test whether $IG(C)$ is bipartite and how to construct
a partition ${L,R}$ of its vertex set, and
item how to construct an embedding of $S(e_0)$ from the embeddings of
the $S(e_i)$'s. This involves flipping of embeddings as we
incrementally construct the embedding of $S(e_0)$.
end{itemize}
Suppose now that some benign agent told us that $IG(C)$ were bipartite
and gave us an appropriate partition ${L,R}$ of its vertex set,
i.e., a partition ${L,R}$ such that no
two segments in $L$ and no two segments in $R$ interlace and such that
$A(e_i)cap {w_1,ldots ,w_{r-1}}=emptyset$ for any segment
$S(e_i)in R$.
Here, as before, $w_0,ldots ,w_r$ denotes the stem of $C$.
Then no flipping would ever be necessary;
we can simply combine the embeddings of the $S(e_i)$'s as prescribed
by the partition ${L,R}$.
More precisely, to construct a canonical embedding of $S(e_0)$ draw
the path $w_0,ldots ,w_k$ (consisting of stem $w_0,ldots ,w_r$,
edge $e_0 = (w_r,w_{r+1})$ and spine $w_{r+1},ldots ,w_k$) as a
vertical upwards directed path, add edge $(w_k,w_0)$, and then for $i$,
$1leq ileq m$, and $S(e_i)in L$ extend the embedding of
$C+S(e_1)+ldots S(e_{i-1})$ by glueing a canonical embedding of
$S(e_i)$ onto the left side of the vertical path, and for $i$,
$1leq ileq m$, and $S(e_i)in R$ extend the embedding of
$C+S(e_1)+ldots +S(e_{i-1})$ by glueing a reversed canonical
embedding of $S(e_i)$ onto the right side of the vertical path.
Similarly, if the goal is to construct a reversed canonical embedding
of $S(e_0)$ then, if $S(e_i)in L$, a reversed canonical embedding of
$S(e_i)$ is glued onto the right side of the vertical path, and if
$S(e_i) in R$, then a canonical embedding of $S(e_i)$ is glued onto the
left side of the vertical path.
Who is the benign agent which tells us that $IG(C)$ is bipartite and
gives us the appropriate partition ${L,R}$ of the segments emanating
from $C=C(e_0)$?
It's the call {em stronglyplanar}($e_0$).
After all, it tests whether $IG(C)$ is bipartite and computes a
bipartition of its vertex set.
Let $S(e)$ be a segment emanating from $C$ and let $B$ be the connected
component of $IG(C)$ containing $S(e)$.
The call {em stronglyplanar}($e_0$) computes $B$ iteratively.
The construction of $B$ is certainly completed when $B$ is popped from
stack $S$.
Put $S(e)$ into $R$ when $S(e)in RB$ at that moment and put $S(e)$
into $L$ otherwise.
With this extension, algorithm {em stronglyplanar} computes the
partition ${L,R}$ of the segments emanating from $C$ in linear time.
We assume for notational convenience that the partition (more precisely,
the union of all partitions for all cycles $C(e_0)$ encountered in the
algorithm) is given as a function $alpha :Sto {L,R}$ where $S$ is
the set of edges for which {em stronglyplanar} is called.
We next give the algorithmic details of the embedding process.
We first use procedure {em stronglyplanar} to compute the mapping
$alpha$.
We then use a procedure {em embedding} to actually compute an
embedding.
The procedure {em embedding} takes two parameters: an edge $e_0$ and
a flag $tin {L,R}$.
A call {em embedding}($e_0,L$) computes a canonical embedding of
$S(e_0)$ and a call {em embedding}($e_0,R$) computes a reversed
canonical embedding of $S(e_0)$.
The call {em embedding}($(1,2),L$) embeds the entire graph.
The embedding of $S(e_0)$ computed by {em embedding}$(e_0,t)$ is
represented in the following non-standard way:
begin{enumerate}
item For the vertices $vin V(e_0)$ we use the standard
representation, i.e., the cyclic list of the incident
edges corresponding to the clockwise ordering of the edges
in the embedding.
item For the vertices in the stem we use a non-standard representation.
For each vertex $w_iin{w_0,ldots,w_{r}}$ let the lists
$AL(w_i)$ and $AR(w_i)$ be such that the catenation of
$(w_i,w_{i+1})$, $AR(w_i)$, $(w_i,w_{i-1})$, and
$AL(w_i)$ corresponds to the clockwise ordering of the edges
incident to $w_i$ in the embedding. Here, $w_{-1}=w_k$.
Note that $AR(w_i)=emptyset$ for $1leq i<r$ if $t=L$, and
$AL(w_i)=emptyset$ for $1leq i<r$, if $t=R$.
The lists $AL(w_i)$, $AR(w_i)$, $0leq ileq r$, are returned in an
implicit way: $AL(w_r)$ and $AR(w_r)$ are returned as the list
$T=AL(w_r),(w_r,w_{r+1})$, $AR(w_r)$ and the other lists
are returned as the list $A=$ $AR(w_{r-1}),ldots,$
$AR(w_0),(w_0,w_k),AL(w_0),ldots ,AL(w_{r-1})$,
cf. Figure~ref{result-embedding.pstex_t}.
end{enumerate}
bild{result-embedding.pstex_t}{A call {em embedding} $(e_0,t)$ returns lists
$T$ and $A$.}
The procedure {em embedding} has the same structure as the procedure
{em stronglyplanar} and is given in Program 1 on page pageref{program}.
It first constructs the stem and the spine (line (1)) of cycle $C(e_0)$,
then walks down the spine (lines (3) to (14)), and finally computes
the lists $T$ and $A$ it wants to return (lines (15) and (16)).
We first discuss the walk down the spine.
Suppose that the walk has reached vertex $w_j$.
We first recursively process the edges emanating from $w_j$
(lines (4) to (10)), and then compute the cyclic adjacency list of vertex
$w_j$ and prepare for the next iteration (lines (11) to (13)).
We discuss lines (4) to (10) first.
In general, some number of edges emanating from $w_j$ and all edges
incident to vertices $w_l$ with $l>j$ will have been processed already.
In agreement with our previous notation call the processed edges
$e_1,ldots ,e_{i-1}$.
We claim that the following statement is an invariant of the loop (4) to (10):
$T$ concatenated with $(w_j,w_{j-1})$ is the cyclic adjacency list of
vertex $w_j$ in the embedding of $C+S(e_1)+ldots +S(e_{i-1})$, and
$AL$ and $AR$ are the catenation of lists $AL(w_0),ldots ,AL(w_{j-1})$
and $AR(w_{j-1}),ldots ,AR(w_0)$ respectively where $(w_l,w_{l+1})$,
$AR(w_l), (w_l,w_{l-1}), AL(w_l)$ is the cyclic adjacency
list of vertex $w_l$, $0leq lleq j-1$, in the embedding of
$C+S(e_0)+ldots +S(e_{i-1})$.
The lists $T$, $AL$, and $AR$ are certainly initialized correctly in
line (2).
Assume now that we process edge $e'=e_i$ emanating from $w_j$.
The flag $alpha(e')$ indicates what kind of embedding of $S(e_i)$ is
needed to build a canonical embedding of $S(e_0)$; the opposite kind of
embedding of $S(e_i)$ is needed to build a reversed canonical embedding
of $S(e_0)$.
So the required kind is given by $toplusalpha(e')$, where
$Loplus L=Roplus R=L$ and $Loplus R=Roplus L=R$.
The call {em embedding}$(e',toplusalpha(e'))$ computes the cyclic
adjacency lists of the vertices in $V(e')$ and returns lists $T'$ and
$A'$ as defined above.
If $S(e_i)$ has to be glued to the left side of the vertical path
$w_0,ldots ,w_k$, i.e., if  $t=alpha(e')$ then we append $T'$ to the front of
$T$ and $A'$ to
the end of $AL$, cf. Figure~ref{glueing}.
Analogously, if $S(e_i)$ has to be glued to the right side of the
path $w_0,ldots ,w_k$, i.e., if $tnot=alpha(e')$, then we append $T'$
to the end of $T$ and $A'$ to the front of $AR$.
This clearly maintains the invariant.
Suppose now that we have processed all edges emanating from $w_j$.
Then $(w_j,w_{j-1})$ concatenated with $T$ is the cyclic adjacency list
of vertex $w_j$ (line (11)).
begin{figure}[htb]
begin{center}
input{glueing.pstex_t}
end{center}
caption{label{glueing}
Glueing $S(e')$ to the left or right side of the path
$w_0,ldots ,w_k$ respectively.}
end{figure}
We next prepare for the treatment of vertex $w_{j-1}$.
Let $T'$ and $T''$ be the list of darts incident to $w_{j-1}$ from
the left and from the right respectively and having their other
endpoint in an already embedded segment.
List $T'$ is a suffix of $AL$ and list $T''$ is a prefix of $AR$.
The catenation of $T',(w_{j-1},w_j)$, $T''$, and
$(w_{j-1},w_{j-2})$ is the current clockwise adjacency list of
vertex $w_{j-1}$.
Thus lines (12) and (13) correctly initialize $AL$, $AR$, and $T$ for
the next iteration.
Suppose now that all edges emanating from the spine of $C(e_0)$ have
been processed, i.e., control reaches line (15).
At this point, list $T$ is the ordered list of darts incident to $w_r$
(except $(w_r,w_{r-1})$) and the two lists $AL$ and $AR$ are the
ordered list of darts incident to the two sides of the stem of $C(e_0)$.
Thus $T$ and the catenation of $AR,(w_0,w_k)$, and
$AL$ are the two components of the output of {em embedding}$(e_0,t)$.
We summarize in
begin{theorem}
Let $G=(V,E)$ be a planar graph.
Then $G$ can be turned into a planar map $(G,sigma)$ in linear time.
end{theorem}
begin{table}
~hrulefill
begin{tabbing}
qquad = {bf do} = {bf do} = kill
> (0) ' {bf procedure} {em embedding}($e_0$: edge, $t$: ${L,R}$)+\
($*$ computes an embedding of $S(e_0)$, $e_0=(x,y)$, as described in the text; %
\
> it returns the lists $T$ and $A$ defined in the text $*$)-\
> (1) ' find the spine of segment $S(e_0)$ by starting in node $y$ and always%
+\
> take the first edge of every adjacency list until a back edge is \
> encountered. This back edge leads to node $w_0=lowpt[y]$. \
> Let $w_0,ldots,w_r$ be the tree path from $w_0$ to $x=w_r$ and \
> let $w_{r+1}=y,ldots,w_k$ be the spine constructed above. -\
> (2) ' $AL gets AR gets$ empty list of darts;\
>     > $T gets (w_k,w_0)$; ` ($*$ a list of darts $*$)\
> (3) ' {bf for} $j$ {bf from} $k$ {bf downto} $r+1$ \
> (4) ' {bf do} {bf for} all edges $e'$ (except the first) emanating from
$w_j$ \
> (5) ' > {bf do} $(T',A') gets$ {em embedding}$(e',toplusalpha(e'))$\
> (6) ' > > {bf if} $t=alpha(e')$\
> (7) ' > > {bf then} $T gets T'$ {bf conc} $T$; $AL gets AL$ {bf
conc} $A'$\
> (8) ' > > {bf else} $T gets T$ {bf conc} $T'$; $AR gets A'$ {bf
conc}  $AR$\
> (9) ' > > {bf fi}\
>(10) ' > {bf od}\
>(11) ' > {bf output} $(w_j,w_{j-1})$ {bf conc} $T$;
` ($*$ the cyclic adjacency list of vertex $w_j$ $*$) \
>(12) ' > {bf let} $AL=AL'$ {bf conc} $T'$ and $AR=T''$
{bf conc} $AR'$\
>     > > where $T'$ and $T''$ contain all darts incident
to $w_{j-1}$;\
>(13) ' > $ALgets AL'$; $ARgets AR'$; $Tgets
T'$ {bf conc} $(w_{j-1},w_j)$ {bf conc} $T''$\
>(14) ' {bf od}\
>(15) ' $Agets$ $AR$ {bf conc} $(w_0,w_k)$ {bf conc} $AL$;\
>(16) ' {bf return} $T$ and $A$\
>(17) ' {bf end}
end{tabbing}
~hrulefill Program 1 label{program} hrulefill
end{table}
In our implementation we follow the book except in three minor points. PB{|G}
has only one directed
version of each edge but PB{|H} has both. In the embedding
phase we need both
directions and therefore construct the embedding of
PB{|H} and later translate it back to PB{\{Gin}}. Secondly, we do not
construct the embedding
of PB{|H} vertex by vertex but in one shot. To that effect we compute a
labelling
PB{\{sort_num}} of the edges of PB{|H} and later sort the edges.
Thirdly, the book makes reference to edges $(w_{i-1},w_i)$
and their reversals. To make these edges available we compute an array PB{%
\{tree_edge_into}}
that contains for each node the incoming tree edge.
We finally want to remark on our convention for drawing lists.
In Figures ref{result-embedding.pstex_t}
and ref{glueing} the arrows indicate the end (!!!) of the lists.
clearpage
YB4X26:construct embeddingX${}E{}$6
${}{{}$16
${}&{list}langle&{edge}rangle{}$ |T${},{}$ |A;SHC{lists of edges of PB{%
|H} }6
&{int} \{cur_nr}${}KT{0};{}$6
${}&{edge_array}langle&{int}rangle{}$ \{sort_num}(|H);6
${}&{node_array}langle&{edge}rangle{}$ \{tree_edge_into}(|G);7
${}\{embedding}(|G.\{first_adj_edge}(|G.\{first_node}(,)),39\{left},%
39|G,39\{alpha},39\{dfsnum},39|T,39|A,39\{cur_nr},39\{sort%
_num},39\{tree_edge_into},39\{parent},39\{reversal}){}$;C{ PB{|T}
contains all edges incident to the first node except the cycle edge into it.
That edge comprises PB{|A} }6
${}|T.\{conc}(|A);{}$7
&{edge} |e;7
&{forall} ${}(|e,39|T){}$15
${}\{sort_num}[|e]K\{cur_nr}PP;{}$27
${}&{edge_array}langle&{int}rangle{}$ \{sort_Gin}(\{Gin});7
${}{{}$16
&{edge} \{ein};7
&{forall_edges} ${}(\{ein},39\{Gin}){}$15
${}\{sort_Gin}[\{ein}]K\{sort_num}[\{companion_in_H}[\{ein}]];{}$26
4${}}{}$26
${}\{Gin}.\{sort_edges}(\{sort_Gin});{}$6
4${}}{}$2par
U5.fi
M{27}It remains to describe procedure PB{\{embedding}}.
YB4X9:auxiliary functionsX${}mathrel+E{}$6
&{void} \{embedding}(&{edge} \{e0}${},39{}$&{int} |t${},39&{GRAPH}%
langle&{node},39&{edge}rangle{}$ ${}{AND}|G,39&{edge_array}langle%
&{int}rangle{}$ ${}{AND}\{alpha},3{-1}39&{node_array}langle&{int}%
rangle{}$ ${}{AND}\{dfsnum},39&{list}langle&{edge}rangle{}$ ${}{AND}%
|T,39&{list}langle&{edge}rangle{}$ ${}{AND}|A,39{}$&{int} ${}{AND}%
\{cur_nr},3{-1}39&{edge_array}langle&{int}rangle{}$ ${}{AND}\{sort%
_num},39&{node_array}langle&{edge}rangle{}$ ${}{AND}\{tree_edge%
_into},3{-1}39&{node_array}langle&{node}rangle{}$ ${}{AND}\{parent},%
39&{edge_array}langle&{edge}rangle{}$ ${}{AND}\{reversal}){}$11226
${}{{}$16
X28:embed: determine the cycle $C(e0)$X;6
X29:process the subsegmentsX;6
X33:prepare the outputX;6
4${}}{}$2par
fi
M{28}We start by determining the spine cycle. This is precisley as in PB{%
\{strongly_planar}}.
We also record for the vertices $w_{r+1}$, $ldots$, $w_k$, and $w_0$ the
incoming cycle edge either in PB{\{tree_edge_into}} or in the local
variable PB{\{back_edge_into_w0}}. This is line (1) of Program1.
YB4X28:embed: determine the cycle $C(e0)$X${}E{}$6
&{node} |x${}K\{source}(\{e0});{}$6
&{node} |y${}K\{target}(\{e0});{}$7
${}\{tree_edge_into}[|y]K\{e0};{}$7
&{edge} |e${}K|G.\{first_adj_edge}(|y);{}$6
&{node} \{wk}${}K|y;{}$7
&{while} ${}(\{dfsnum}[\{target}(|e)]>\{dfsnum}[\{wk}]{}$)SHC{ e is a
tree edge }6
${}{{}$16
${}\{wk}K\{target}(|e);{}$6
${}\{tree_edge_into}[\{wk}]K|e;{}$6
${}|eK|G.\{first_adj_edge}(\{wk});{}$6
4${}}{}$27
&{node} \{w0}${}K\{target}(|e);{}$6
&{edge} \{back_edge_into_w0}${}K|e{}$;par
U27.fi
M{29}Lines (2) to (14).
YB4X29:process the subsegmentsX${}E{}$6
&{node} |w${}K\{wk};{}$6
${}&{list}langle&{edge}rangle{}$ \{Al}${},{}$ \{Ar};6
${}&{list}langle&{edge}rangle{}$ \{Tprime}${},{}$ \{Aprime};7
${}|T.\{clear}(,);{}$6
${}|T.\{append}(|G[|e]){}$;SHC{ PB{$|eK(\{wk},\{w0})$} at this point,
line (2) }6
&{while} ${}(|wI|x){}$5
${}{{}$16
&{int} \{count}${}KT{0};{}$7
&{forall_adj_edges} ${}(|e,39|w){}$5
${}{{}$16
${}\{count}PP;{}$6
&{if} ${}(\{count}IT{1}{}$)SHC{no action for first edge }6
${}{{}$16
X30:embed recursivelyX;6
X31:update lists PB{|T}, PB{\{Al}}, and PB{\{Ar}}X;6
4${}}{}$SHC{ end if }26
4${}}{}$SHC{end forall }26
X32:compute PB{|w}'s adjacency list and prepare for next iterationX;6
${}|wK\{parent}[|w];{}$6
4${}}{}$SHC{end while }2par
U27.fi
M{30}Line (5). The book does not distinguish between tree and back edges but
we do
here.
YB4X30:embed recursivelyX${}E{}$6
&{if} ${}(\{dfsnum}[|w]<\{dfsnum}[\{target}(|e)]){}$5
${}{{}$C{ tree edge }16
&{int} \{tprime}${}K((|tE\{alpha}[|e])?\{left}:\{right});{}$7
${}\{embedding}(|e,39\{tprime},39|G,39\{alpha},39\{dfsnum},39%
\{Tprime},39\{Aprime},39\{cur_nr},39\{sort_num},39\{tree_edge%
_into},39\{parent},39\{reversal});{}$6
4${}}{}$26
&{else}5
${}{{}$C{ back edge }16
${}\{Tprime}.\{append}(|G[|e]){}$;SHC{$e$ }6
${}\{Aprime}.\{append}(\{reversal}[|G[|e]]){}$;SHC{reversal of $e$ }6
4${}}{}$2par
U29.fi
M{31}Lines (6) to (9).
YB4X31:update lists PB{|T}, PB{\{Al}}, and PB{\{Ar}}X${}E{}$6
&{if} ${}(|tE\{alpha}[|e]){}$5
${}{{}$16
${}\{Tprime}.\{conc}(|T);{}$6
${}|T.\{conc}(\{Tprime}){}$;SHC{$T = Tprime conc T$ }6
${}\{Al}.\{conc}(\{Aprime}){}$;SHC{$Al = Al conc Aprime$ }6
4${}}{}$26
&{else}5
${}{{}$16
${}|T.\{conc}(\{Tprime}){}$;SHC{ $ T = T conc Tprime $ }6
${}\{Aprime}.\{conc}(\{Ar});{}$6
${}\{Ar}.\{conc}(\{Aprime}){}$;SHC{ $ Ar = Aprime conc Ar$ }6
4${}}{}$2par
U29.fi
M{32}Lines (11) to (13).
YB4X32:compute PB{|w}'s adjacency list and prepare for next iteration%
X${}E{}$6
$|T.\{append}(\{reversal}[|G[\{tree_edge_into}[|w]]]){}$;SHC{
$(w_{j-1},w_j)$ }6
&{forall} ${}(|e,39|T){}$15
${}\{sort_num}[|e]K\{cur_nr}PP{}$;C{ PB{|w}'s adjacency list is now
computed; we clear PB{|T} and prepare for the next iteration by moving all
darts incident to PB{\{parent}[|w]} from PB{\{Al}} and PB{\{Ar}} to PB{%
|T}. These darts are at the rear end of PB{\{Al}} and at the front end of %
PB{\{Ar}} }26
${}|T.\{clear}(,);{}$6
&{while} ${}(R\{Al}.\{empty}(,)W\{source}(\{Al}.\{tail}(,))E|G[%
\{parent}[|w]]{}$)SHC{ PB{\{parent}[|w]} is in PB{|G}, PB{$\{Al}.%
\{tail}$} in PB{|H} }6
${}{{}$16
${}|T.\{push}(\{Al}.\{Pop}(,)){}$;SHC{Pop removes from the rear }6
4${}}{}$26
${}|T.\{append}(|G[\{tree_edge_into}[|w]]){}$;SHC{ push would be
equivalent }6
&{while} ${}(R\{Ar}.\{empty}(,)W\{source}(\{Ar}.\{head}(,))E|G[%
\{parent}[|w]]{}$)SHC{ }6
${}{{}$16
${}|T.\{append}(\{Ar}.\{pop}(,)){}$;SHC{ pop removes from the front }6
4${}}{}$2par
U29.fi
M{33}Line (15). Concatenate PB{\{Ar}}, $(w_0,w_r)$, and PB{\{Al}}.
YB4X33:prepare the outputX${}E{}$6
$|A.\{clear}(,);{}$6
${}|A.\{conc}(\{Ar});{}$6
${}|A.\{append}(\{reversal}[|G[\{back_edge_into_w0}]]);{}$6
${}|A.\{conc}(\{Al}){}$;par
U27.fi
N{1}{34}Efficiency. label{Efficiency}
Under LEDA 3.0 the space requirement of the first version of PB{\{planar}} is
approximately
$160 (n+m) +100 alpha m$ Bytes, where $n$ and $m$ denote the number of nodes
and edges respectively and $alpha$ is the fraction of edges in the input graph
that do not have their reversal in the input graph. For the pseudo-random
planar graphs generated in the demo we have $alpha = 0$ and $m = 4n$ and hence
the
space requirement is about $800 n$ Bytes. The second version needs an
additional
$54n + 66m$ Bytes.
The running time of PB{\{planar}} is about $50$ times the running
time of PB{\{STRONG_COMPONENTS}}. On a 50 MIPS SPARC10 workstation
the planarity of a
planar graph with 16000 nodes and 30000 edges ($alpha = 0$) is tested in
about 10 seconds. It takes 5.4 seconds to make the graph bidirected and
biconnected, about 3.9 seconds to test its planarity, and
another 6.1 seconds to
construct an embedding. The space requirement is about 15 MByte.
fi
N{1}{35}A Demo. label{demo}
The demo allows the user to either interactively construct a graph
using
LEDA's graph editor or to construct a random graph, or to
construct a ``pseudo-random'' planar graph
(the graph defined by an arrangement of random line segments). The graph is
then tested for
planarity. If the graph is planar a straight-line embedding is output. If the
graph is non-planar a Kuratowski subgraph is highlighted.
The demo proceeds in cycles. In each cycle we first clear the graphics window %
PB{|W} and
the graph PB{|G} and then give the user the choice of a new input graph.
YB4X35:.{demo.c }X${}E{}$6
X3:includesX;6
X37:procedure to draw graphsX;6
\{main}(,)11 ${$ X38:initiation and declarationsX;6
&{while} (\{true}) ${$ X39:select graphX;6
X40:test graph for planarity and show outputX X41:reset windowX;6
$}$ &{return} T{0}; $}{}$par
fi
M{36}We need to include PB{$\{planar}.|h$} and various parts of LEDA.
YB4X3:includesX${}mathrel+E{}$6
8#&{include} .{"planar.h"}6
8#&{include} .{<LEDA/graph.h>}6
8#&{include} .{<LEDA/graph_alg.h>}6
8#&{include} .{<LEDA/window.h>}6
8#&{include} .{<LEDA/graph_edit.h>}par
fi
M{37}We need a simple procedure to draw a graph in a graphics window. The
numbering of the nodes is optional.
YB4X37:procedure to draw graphsX${}E{}$6
&{void} \{draw_graph}(&{const} &{GRAPH}${}langle&{point},39&{int}%
rangle{}$ ${}{AND}|G,39{}$&{window} ${}{AND}|W,39{}$&{bool} %
\{numbering}${}K\{false}){}$11226
${}{{}$16
&{node} |v;6
&{edge} |e;6
&{int} |i${}KT{0};{}$7
&{forall_edges} ${}(|e,39|G){}$15
${}|W.\{draw_edge}(|G[\{source}(|e)],39|G[\{target}(|e)],39%
\{blue});{}$26
&{if} (\{numbering})16
&{forall_nodes} ${}(|v,39|G){}$15
${}|W.\{draw_int_node}(|G[|v],39|iPP,39\{red});{}$226
&{else}16
&{forall_nodes} ${}(|v,39|G){}$15
${}|W.\{draw_filled_node}(|G[|v],39\{red});{}$226
4${}}{}$2par
U35.fi
M{38}We give the user a short explanation of the demo and declare some
variables.
YB4X38:initiation and declarationsX${}E{}$6
&{panel} |P;7
${}|P.\{text_item}(.{"This demo illustrat}).{es planarity testing})%
.{ and planar straight}).{-line"});{}$6
${}|P.\{text_item}(.{"embedding. You have}).{ two ways to constru}%
).{ct a graph: either i}).{nteractively"});{}$6
${}|P.\{text_item}(.{"using the LEDA grap}).{h editor or by calli}%
).{ng one of two graph }).{generators."});{}$6
${}|P.\{text_item}(.{"The first generator}).{ constructs a random})%
.{ graph with a certai}).{n"});{}$6
${}|P.\{text_item}(.{"number of nodes and}).{ edges (you will be
}).{asked how many) and }).{the "});{}$6
${}|P.\{text_item}(.{"second generator co}).{nstructs a planar gr})%
.{aph  by intersecting}).{ a certain"});{}$6
${}|P.\{text_item}(.{"number of random li}).{ne segments in the u}%
).{nit square (you will}).{ be asked how many).}).{"});{}$6
${}|P.\{text_item}(.{" "});{}$6
${}|P.\{text_item}(.{"The graph is displa}).{yed and then tested }%
).{for planarity."});{}$6
${}|P.\{text_item}(.{"If the graph is non}).{-planar a Kuratowski}%
).{ subgraph is highlig}).{hted."});{}$6
${}|P.\{text_item}(.{"If the graph is pla}).{nar, a straight-line}%
).{ drawing is produced}).{."});{}$6
${}|P.\{button}(.{"continue"});{}$6
${}|P.\{open}(,);{}$7
&{window} |W;6
${}&{GRAPH}langle&{point},39&{int}rangle{}$ |G;6
&{node} |v${},{}$ |w;6
&{edge} |e;6
&{int} |n${}KT{250};{}$6
&{int} |m${}KT{250};{}$6
&{const} &{double} \{pi}${}KT{3.14};{}$6
&{panel} \{P1}(.{"PLANARITY TEST"});7
${}\{P1}.\{int_item}(.{"|V| = "},39|n,39T{0},39T{500});{}$6
${}\{P1}.\{int_item}(.{"|E| = "},39|m,39T{0},39T{500});{}$6
${}\{P1}.\{button}(.{"edit"});{}$6
${}\{P1}.\{button}(.{"random"});{}$6
${}\{P1}.\{button}(.{"planar"});{}$6
${}\{P1}.\{button}(.{"quit"});{}$6
${}\{P1}.\{text_item}(.{" "});{}$6
${}\{P1}.\{text_item}(.{"The first slider as}).{ks for the number
n }).{of nodes and"});{}$6
${}\{P1}.\{text_item}(.{"the second slider a}).{sks for the number
m}).{ of edges."});{}$6
${}\{P1}.\{text_item}(.{"If you select the r}).{andom input button
t}).{hen a graph with"});{}$6
${}\{P1}.\{text_item}(.{"that number of node}).{s and edges is
const}).{ructed, if you"});{}$6
${}\{P1}.\{text_item}(.{"select the planar i}).{nput button then
2.5}).{ times square-root o}).{f n"});{}$6
${}\{P1}.\{text_item}(.{"random line segment}).{s are chosen and
int}).{ersected to yield"});{}$6
${}\{P1}.\{text_item}(.{"a planar graph with}).{ about n nodes,
and }).{if you select the"});{}$6
${}\{P1}.\{text_item}(.{"edit button then th}).{e graph editor is
ca}).{lled."});{}$6
${}\{P1}.\{text_item}(.{" "}){}$;par
U35.fi
M{39}We display the panel PB{\{P1}} until the user makes his choice. Then we
construct
the appropriate graph.
YB4X39:select graphX${}E{}$6
&{int} \{inp}${}K\{P1}.\{open}(|W){}$;SHC{ P1 is displayed until a
button is pressed }7
&{if} ${}(\{inp}ET{3}){}$15
&{break};SHC{ quit button pressed }26
${}|W.\{init}(T{0},39T{1000},39T{0});{}$6
${}|W.\{set_node_width}(T{5});{}$6
&{switch} (\{inp})5
${}{{}$16
4&{case} T{0}:6
${}{{}$SHC{ graph editor }16
${}|W.\{set_node_width}(T{10});{}$6
${}|G.\{clear}(,);{}$6
${}\{graph_edit}(|W,39|G,39\{false});{}$6
&{break};6
4${}}{}$26
4&{case} T{1}:6
${}{{}$SHC{ random graph }16
${}|G.\{clear}(,);{}$6
${}\{random_graph}(|G,39|n,39|m){}$;C{ eliminate parallel edges and
self-loops }6
\{eliminate_parallel_edges}(|G);7
${}&{list}langle&{edge}rangle{}$ \{Del}${}K|G.\{all_edges}(,);{}$7
&{forall} ${}(|e,39\{Del}){}$16
&{if} ${}(|G.\{source}(|e)E|G.\{target}(|e)){}$15
${}|G.\{del_edge}(|e){}$;C{ draw the graph with its nodes on a circle}22%
7
&{float} \{ang}${}KT{0};{}$7
&{forall_nodes} ${}(|v,39|G){}$5
${}{{}$16
${}|G[|v]K&{point}(T{500}+T{400}*\{sin}(\{ang}),39T{500}+T{400}*%
\{cos}(\{ang}));{}$6
${}\{ang}MRL{+{K}}T{2}*\{pi}/|n;{}$6
4${}}{}$26
${}\{draw_graph}(|G,39|W);{}$6
&{break};6
4${}}{}$26
4&{case} T{2}:6
${}{{}$SHC{ pseudo-random planar graph }16
${}&{node_array}langle&{double}rangle{}$ \{xcoord}(|G);6
${}&{node_array}langle&{double}rangle{}$ \{ycoord}(|G);7
${}|G.\{clear}(,);{}$6
${}\{random_planar_graph}(|G,39\{xcoord},39\{ycoord},39|n);{}$6
&{forall_nodes} ${}(|v,39|G){}$15
${}|G[|v]K&{point}(T{1000}*\{xcoord}[|v],39T{900}*\{ycoord}[|v]);{}$%
26
${}\{draw_graph}(|G,39|W);{}$6
&{break};6
4${}}{}$26
4${}}{}$2par
U35.fi
M{40}We test the planarity of our graph PB{|G} using our procedure PB{%
\{planar}}.
YB4X40:test graph for planarity and show outputX${}E{}$6
&{if} ${}(\{PLANAR}(|G,39\{false})){}$5
${}{{}$16
&{if} ${}(|G.\{number_of_nodes}(,)<T{4}){}$15
${}|W.\{message}(.{"That's an insult: E}).{very graph with |V| })%
.{<= 4 is planar"});{}$26
&{else}5
${}{{}$16
${}|W.\{message}(.{"G is planar. I comp}).{ute a straight-line })%
.{embedding ..."}){}$;C{ we first make PB{|G} bidirected. We remember the
edges added in PB{\{n_edges}} }7
${}&{node_array}langle&{int}rangle{}$ \{nr}(|G);6
${}&{edge_array}langle&{int}rangle{}$ \{cost}(|G);6
&{int} \{cur_nr}${}KT{0};{}$6
&{int} |n${}K|G.\{number_of_nodes}(,);{}$6
&{node} |v;6
&{edge} |e;7
&{forall_nodes} ${}(|v,39|G){}$15
${}\{nr}[|v]K\{cur_nr}PP;{}$26
&{forall_edges} ${}(|e,39|G){}$15
${}\{cost}[|e]K((\{nr}[\{source}(|e)]<\{nr}[\{target}(|e)])?|n*%
\{nr}[\{source}(|e)]+\{nr}[\{target}(|e)]:|n*\{nr}[\{target}(|e)]+%
\{nr}[\{source}(|e)]);{}$26
${}|G.\{sort_edges}(\{cost});{}$7
${}&{list}langle&{edge}rangle{}$ |L${}K|G.\{all_edges}(,);{}$6
${}&{list}langle&{edge}rangle{}$ \{n_edges};7
&{while} ${}(R|L.\{empty}(,)){}$5
${}{{}$16
${}|eK|L.\{pop}(,);{}$6
&{if} ${}(R|L.\{empty}(,)W\{source}(|e)E\{target}(|L.\{head}(,))W%
\{target}(|e)E\{source}(|L.\{head}(,))){}$15
${}|L.\{pop}(,);{}$26
&{else}5
${}{{}$16
${}\{n_edges}.\{append}(|G.\{new_edge}(\{target}(|e),39\{source}(%
|e)));{}$6
4${}}{}$26
4${}}{}$26
\{Make_biconnected_graph}(|G);6
${}\{PLANAR}(|G,39\{true});{}$7
${}&{node_array}langle&{int}rangle{}$ \{xcoord}(|G)${},{}$ \{ycoord}(%
|G);7
${}\{STRAIGHT_LINE_EMBEDDING}(|G,39\{xcoord},39\{ycoord});{}$7
&{float} |f${}KT{900.0}/(T{2}*|G.\{number_of_nodes}(,));{}$7
&{forall_nodes} ${}(|v,39|G){}$15
${}|G[|v]K&{point}(|f*\{xcoord}[|v]+T{30},39T{2}*|f*\{ycoord}[|v]+%
T{30});{}$26
&{forall} ${}(|e,39\{n_edges}){}$15
${}|G.\{del_edge}(|e);{}$26
${}|W.\{clear}(,);{}$6
&{if} ${}(\{inp}ET{0}){}$15
${}\{draw_graph}(|G,39|W,39\{true}){}$;SHC{ with node numbering }26
&{else}15
${}\{draw_graph}(|G,39|W);{}$26
4${}}{}$26
4${}}{}$26
&{else}5
${}{{}$16
${}|W.\{message}(.{"Graph is not planar}).{. I compute the Kura})%
.{towski subgraph ..."});{}$7
${}&{list}langle&{edge}rangle{}$ |L;7
${}\{PLANAR}(|G,39|L,39\{false});{}$7
${}&{node_array}langle&{int}rangle{}$ ${}\{deg}(|G,39T{0});{}$6
&{int} \{lw}${}K|W.\{set_line_width}(T{3});{}$6
&{edge} |e;7
&{forall} ${}(|e,39|L){}$5
${}{{}$16
&{node} |v${}K\{source}(|e);{}$6
&{node} |w${}K\{target}(|e);{}$7
${}\{deg}[|v]PP;{}$6
${}\{deg}[|w]PP;{}$6
${}|W.\{draw_edge}(|G[|v],39|G[|w]);{}$6
4${}}{}$27
&{int} |i${}KT{1}{}$;C{ We highlight the Kuratowski subgraph. Nodes with
degree are drawn black. The nodes with larger degree are shown green and
numbered from 1 to 6 }7
&{forall_nodes} ${}(|v,39|G){}$5
${}{{}$16
&{if} ${}(\{deg}[|v]ET{2}){}$15
${}|W.\{draw_filled_node}(|G[|v],39\{black});{}$26
&{if} ${}(\{deg}[|v]>T{2}){}$5
${}{{}$16
&{int} \{nw}${}K|W.\{set_node_width}(T{10});{}$7
${}|W.\{draw_int_node}(|G[|v],39|iPP,39\{green});{}$6
${}|W.\{set_node_width}(\{nw});{}$6
4${}}{}$26
4${}}{}$26
${}|W.\{set_line_width}(\{lw});{}$6
4${}}{}$2par
U35.fi
M{41}We reset the graphics window.
YB4X41:reset windowX${}E{}$6
$|W.\{set_show_coordinates}(\{false});{}$6
${}|W.\{set_frame_label}(.{"click any button to}).{ continue"});{}$6
${}|W.\{read_mouse}(,){}$;SHC{ wait for a click }6
${}|W.\{reset_frame_label}(,);{}$6
${}|W.\{set_show_coordinates}(\{true}){}$;par
U35.fi
N{1}{42}Some Theory.    label{reprint}
We give the theory underlying the planarity test as described in
cite[section IV.10]{Me:book}.
%Our next ...
bibliography{/KM/usr/mehlhorn/tex/my}
bibliographystyle{alpha}
end{document}
fi

						