Drawing Simultaneously Embedded Graphs with Few Bends - Graph Drawing - page 43

Theorem 1. Let ( G 1 ,...,G k ) be a sunflower instance of S EFE with pairwise common
graph G together witha S EFE embedding.Then the following S EFE drawingsrealizing
the given S EFE embedding exist.
(i) If G is biconnected andinduced, there exists a (0,0)-drawing.
(ii) If G is biconnected, there exists a (0,1)-drawing.
(iii) If G is connected andinduced, there exists a (0,1)-drawing.
(iv)If G is connected, there exists a (0,3)-drawing.

Before we proceed to prove Theorem 1, we first mention an interesting implica-
tion; the first efficient algorithm for testing the existence of S GE on a non-trivial class
of graphs. By Theorem 1(i) two graphs whose common graph is biconnected and in-
duced admit an SGE if and only if they admit a S EFE . The latter can be tested in linear
time [2,10].

Corollary 1. There is a linear-time algorithm for S IMULTANEOUS G EOMETRIC E M -
BEDDING if thecommongraph is biconnected andinduced.

The rest of this section is devoted to proving Theorem 1. The main tool for the proof
is the existence of certain planar straight-line drawings of the common graph, so-called
universal drawings, that can be extended to a drawing of any plane supergraph of G
with few bends per edge. Theorem 1 is an immediate consequence of the existence of
such drawings.
Let G be a planar graph and let ʓ be a planar straight-line drawing of G .Let H G

be a plane supergraph of G . We say that ʓ is k -extendable for H if it can be extended
to a drawing of H that has at most k bends per edge. The drawing ʓ is k -universal if it
is k -extendable to every plane supergraph H . The drawing ʓ is induced k -universal if
it is k -extendable for any plane supergraph H that contains G as an induced subgraph.
Similar to Lemma 2, a drawing that is induced k -universal is 2 k +1-universal.

ↇ

Lemma 3. Let G be a planar graphandlet ʓ be an induced k -universaldrawing of G .
Then ʓ is (2 k +1) -universal.

G be an arbitrary plane supergraph of G .Let H be the graph obtained
from H by subdividing each edgeof H

Proof. Let H ↇ

G whose endpoints both belong to H .Since ʓ
is induced k -universal, we find a drawing ʓ of H extending ʓ that has at most k bends
per edge. By interpreting the subdivision vertices as bends, the drawing ʓ can be seen
as a drawing of H with at most (2 k +1)-bends per edge, extending ʓ . This finishes the
proof, since H is an arbitrary plane supergraph of G .

−

We are now ready to prove the existence of universal drawings for biconnected planar
graphs.

Theorem 2. Every biconnected plane graphhas an induced 0 -universaldrawing.

Proof. Let G be a biconnected plane graph. We claim that a star-shaped drawing of G ,
whichexistsbyLemma1isinduced 0-universal.
Let H G be a planar supergraph of G with a fixed embedding that extends that

of G . Withoutlossofgenerality, we assume that H is a triangulation. If it is not, we add

ↇ