Information Technology Reference
In-Depth Information
Drawing Partially Embedded
and Simultaneously Planar Graphs
Timothy M. Chan
1
, Fabrizio Frati
2
, Carsten Gutwenger
3
, Anna Lubiw
1
,
Petra Mutzel
3
,andMarcus Schaefer
4
1
Cheriton School of Computer Science, University of Waterloo, Canada
{
tmchan,alubiw
}
@uwaterloo.ca
2
School of Information Technologies, The University of Sydney, Australia
fabrizio.frati@sydney.adu.au
3
Technische Universitat Dortmund, Dortmund, Germany
{
carsten.gutwenger,petra.mutzel
}
@tu-dortmund.de
4
DePaul University, Chicago, Illinois, USA
mschaefer@cdm.depaul.edu
Abstract.
We investigate the problem of constructing planar drawings with few
bends for two related problems, the
partially embedded graph
(PEG) problem—
to extend a straight-line planar drawing of a subgraph to a planar drawing of the
whole graph—and the
simultaneousplanarity
(SEFE) problem—to find planar
drawingsoftwographs that coincide on shared vertices and edges. In both cases
we show that if the required planar drawings exist, then there are planar drawings
with a linear number of bends per edge and, in the case of simultaneous planarity,
a constant number of crossings between every pair of edges. Our proofs provide
efficient algorithms if the combinatorial embedding information about the draw-
ing is given. Ourresult on partially embedded graph drawinggeneralizes a classic
result of Pach and Wenger showing that any planar graph can be drawn with fixed
locations for its vertices and with a linear number of bends per edge.
1
Introduction
In many practical applications we wish to draw a planar graph while satisfying some
geometric or topological constraints. One natural situation is that we have a drawing of
part of the graph and wish to extend it to a planar drawing of the whole graph. Pach and
We nger [20] considered a special case of this problem. They showed that any planar
graph can be drawn with its vertices lying at pre-assigned points in the plane and with
a linear number of bends per edge. In this case the pre-drawn subgraph has no edges.
If the pre-drawn subgraph
H
has edges, a planar drawing of the whole graph
G
extending the given drawing
of
H
might not exist. Angelini et al. [1] gave a linear-
time algorithm for the corresponding decision problem; the algorithm returns, for a
positive answer, a planar embedding of
G
that
extends
that of
H
(i.e., if we restrict the
embedding of
G
to the edges and vertices of
H
, we obtain the embedding corresponding
to
H
). If one does not care about maintaining the actual planar drawing of
H
this is
the end of the story, since standard methods can be used to find a straight-line planar
drawing of
G
in which the drawing of
H
is topologically equivalent to the one of
H
H
.In
