Morphing Planar Graph Drawings Through 3D Kevin Buchin1 Will Evans2 Fabrizio Frati3

2025-05-02 0 0 647.05KB 16 页 10玖币

侵权投诉

Morphing Planar Graph Drawings Through 3D?

Kevin Buchin1, Will Evans2, Fabrizio Frati3, Irina Kostitsyna4,

Maarten L¨oﬄer5, Tim Ophelders6, and Alexander Wolﬀ7

1Technische Universit¨at Dortmund, Germany, kevin.buchin@tu-dortmund.de

2University of British Columbia, Canada, will@cs.ubc.ca

3Roma Tre University, Italy, fabrizio.frati@uniroma3.it

4TU Eindhoven, Netherlands, i.kostitsyna@tue.nl

5Utrecht University, Netherlands, m.loﬄer@uu.nl

6Utrecht University & TU Eindhoven, Netherlands, t.a.e.ophelders@uu.nl

7Universit¨at W¨urzburg, W¨urzburg, Germany

Abstract. In this paper, we investigate crossing-free 3D morphs be-

tween planar straight-line drawings. We show that, for any two (not

necessarily topologically equivalent) planar straight-line drawings of an

n-vertex planar graph, there exists a piecewise-linear crossing-free 3D

morph with O(n2) steps that transforms one drawing into the other. We

also give some evidence why it is diﬃcult to obtain a linear lower bound

(which exists in 2D) for the number of steps of a crossing-free 3D morph.

1 Introduction

Amorph is a continuous transformation between two given drawings of the

same graph. A morph is required to preserve speciﬁc topological and geometric

properties of the input drawings. For example, if the drawings are planar and

straight-line, the morph is required to preserve such properties throughout the

transformation. A morphing problem often assumes that the input drawings are

“topologically equivalent”, that is, they have the same “topological structure”.

For example, if the input drawings are planar, they are required to have the

same rotation system (i.e., the same clockwise order of the edges incident to

each vertex) and the same walk bounding the outer face; this condition is obvi-

ously necessary (and, if the graph is connected, also suﬃcient [6,12]) for a morph

to exist between the given drawings. A linear morph is a morph in which each

vertex moves along a straight-line segment, all vertices leave their initial posi-

tions simultaneously, move at uniform speed, and arrive at their ﬁnal positions

simultaneously. A piecewise-linear morph consists of a sequence of linear morphs,

called steps. A recent line of research culminated in an algorithm by Alamdari

et al. [3] that constructs a piecewise-linear morph with O(n) steps between any

two topologically equivalent planar straight-line drawings of the same n-vertex

planar graph; this bound is worst-case optimal.

?This research was partially supported by MIUR Project “AHeAD” under PRIN

20174LF3T8.

arXiv:2210.05384v1 [cs.CG] 11 Oct 2022

2 Buchin, Evans, Frati, Kostitsyna, L¨oﬄer, Ophelders, Wolﬀ

What can one gain by allowing the morph to use a third dimension? That is,

suppose that the input drawings still lie on the plane z= 0, does one get “better”

morphs if the intermediate drawings are allowed to live in 3D? Arseneva et al. [5]

proved that this is the case, as they showed that, for any two planar straight-

line drawings of an n-vertex tree, there exists a crossing-free (i.e., no two edges

cross in any intermediate drawing) piecewise-linear 3D morph between them

with O(log n) steps. Later, Istomina et al. [11] gave a diﬀerent algorithm for the

same problem. Their algorithm uses O(√nlog n) steps, however it guarantees

that any intermediate drawing of the morph lies on a 3D grid of polynomial size.

Our contribution. We prove that the use of a third dimension allows us to

construct a morph between any two, possibly topologically non-equivalent, planar

drawings. Indeed, we show that O(n2) steps always suﬃce for constructing a

crossing-free 3D morph between any two planar straight-line drawings of the

same n-vertex planar graph; see Sect. 2. Our algorithm deﬁnes some 3D morph

“operations” and applies a suitable sequence of these operations in order to

modify the embedding of the ﬁrst drawing into that of the second drawing. The

topological eﬀect of our operations on the drawing is similar to, although not

the same as, that of the operations deﬁned by Angelini et al. in [4]. Both the

operations deﬁned by Angelini et al. and ours allow to transform an embedding

of a biconnected planar graph into any other. However, while our operations are

3D crossing-free morphs, we see no easy way to directly implement the operations

deﬁned by Angelini et al. as 3D crossing-free morphs. We stress that the input

of our algorithm consists of a pair of planar drawings in the plane z= 0; the

algorithm cannot handle general 3D drawings as input.

We then discuss the diﬃculty of establishing non-trivial lower bounds for the

number of steps needed to construct a crossing-free 3D morph between planar

straight-line drawings; see Sect. 3. We show that, with the help of the third

dimension, one can morph, in a constant number of steps, two topologically

equivalent drawings of a nested-triangle graph (see Fig. 8) that are known to

require a linear number of steps in any crossing-free 2D morph [3].

We conclude with some open problems in Sect. 4.

2 An Upper Bound

This section is devoted to a proof of the following theorem.

Theorem 1. For any two planar straight-line drawings (not necessarily with

the same embedding) of an n-vertex planar graph, there exists a crossing-free

piecewise-linear 3D morph between them with O(n2)steps.

We ﬁrst assume that the given planar graph Gis biconnected and describe

four operations (Sect. 2.1) that allow us to morph a given 2D planar straight-

line drawing of Ginto another one, while achieving some desired change in the

embedding. We then show (Sect. 2.2) how these operations can be used to con-

struct a 3D crossing-free morph between any two planar straight-line drawings

of G. Finally, we remove our biconnectivity assumption (Sect. 2.3).

Morphing Planar Graph Drawings Through 3D 3

Graph ﬂip

(a) O1 w.r.t. {u, v}

Outer face change

(b) O2 w.r.t. f

Component ﬂip

Component skip

(d) O4 w.r.t. G2

Fig. 1: The four operations that are the building blocks for our piecewise-linear morphs.

We give some deﬁnitions. Throughout this paragraph, every considered graph

is assumed to be connected. Two planar drawings of a graph are (topologically)

equivalent if they have the same rotation system and the same clockwise order of

the vertices along the boundary of the outer face. An embedding is an equivalence

class of planar drawings of a graph. A plane graph is a graph with an embedding;

when we talk about a planar drawing of a plane graph, we always assume that the

embedding of the drawing is that of the plane graph. The ﬂip of an embedding E

produces an embedding in which the clockwise order of the edges incident to

each vertex and the clockwise order of the vertices along the boundary of the

outer face are the opposite of the ones in E.

A pair of vertices of a biconnected graph Gis a separation pair if its removal

disconnects G. A split pair of Gis a separation pair or a pair of adjacent vertices.

Asplit component of Gwith respect to a split pair {u, v}is the edge (u, v) or a

maximal subgraph Guv of Gsuch that {u, v}is not a split pair of Guv . A plane

graph is internally-triconnected if every split pair consists of two vertices both

incident to the outer face.

2.1 3D Morph Operations

We begin by describing four operations that morph a given planar straight-line

drawing into another with a diﬀerent embedding; see Fig. 1.

Operation 1: Graph ﬂip. Let Gbe a biconnected plane graph, let uand vbe

two vertices of G, and let Γbe a planar straight-line drawing of G.

Lemma 1. There exists a 2-step 3D crossing-free morph from Γto a planar

straight-line drawing Γ00 of Gwhose embedding is the ﬂip of the embedding that

Ghas in Γ; moreover, uand vdo not move during the morph.

We implement Operation 1, which proves Lemma 1, as follows. Let Πbe the

plane z= 0, which contains Γ. Let Π0be the plane that is orthogonal to Π

4 Buchin, Evans, Frati, Kostitsyna, L¨oﬄer, Ophelders, Wolﬀ

and contains the line `uv through uand v. Let Γ0be the image of Γunder

a clockwise rotation around `uv by 90◦. Note that Γ0is contained in Π0. Now

let Γ00 be the image of Γ0under another clockwise rotation around `uv by 90◦.

Note that Γ00 is a ﬂipped copy of Γand is contained in Π. Consider the linear

morphs hΓ, Γ 0iand hΓ0, Γ 00 i. In each of them, every vertex travels on a line that

makes a 45◦-angle with both Πand Π0, and all these lines are parallel. Due

to the linearity of the morph and the fact that both pre-image and image are

planar, all vertices stay coplanar during both linear morphs (although, unlike in a

true rotation, the intermediate drawing size changes continuously). In particular,

every intermediate drawing is crossing-free, and uand v(as well as all the points

on `uv) are ﬁxed points.

Operation 2: Outer face change. Let Gbe a biconnected plane graph, let Γ

be a planar straight-line drawing of G, and let fbe a face of Γ.

Lemma 2. There exists a 4-step 3D crossing-free morph from Γto a planar

straight-line drawing Γ000 of Gwhose embedding is the same as the one of Γ,

except that the outer face of Γ000 is f.

We implement Operation 2, which proves Lemma 2, using the stereographic

projection. Let Πbe the plane z= 0, which contains Γ. Let Sbe a sphere that

contains Γin its interior and is centered on a point in the interior of f. Let Γ0be

the 3D straight-line drawing obtained by projecting the vertices of Gfrom their

positions in Γvertically to the Northern hemisphere of S. Let Γ00 be determined

by projecting the vertices of Γ0centrally from the North Pole of Sto Π. Both

projections deﬁne linear morphs: hΓ, Γ 0iand hΓ0, Γ 00 i. Indeed, any intermediate

drawing is crossing-free since the rays along which we project are parallel in

hΓ, Γ 0iand diverge in hΓ0, Γ 00 i, and there is a one-to-one correspondence between

the points in the pre-image and in the image. Since the morph also inverts the

rotation system of Γ00 with respect to Γ, we apply Operation 1 to Γ00 , which,

within two morphing steps, ﬂips Γ00 and yields our ﬁnal drawing Γ000 .

Operation 3: Component ﬂip. Let Gbe a biconnected plane graph, and let

{u, v}be a split pair of G. Let G1, . . . , Gkbe the split components of Gwith

respect to {u, v}. Let Γbe a planar straight-line drawing of Gin which uand

vare incident to the outer face, as in Fig. 2a. Relabel G1, . . . , Gkso that they

appear in clockwise order G1, . . . , Gkaround u, where G1and Gkare incident

to the outer face of Γ. Let iand jbe two (not necessarily distinct) indices with

1≤i≤j≤kand with the following property1: If Gcontains the edge (u, v),

then this edge is one of the components Gi, . . . , Gj. Operation 3 allows us to ﬂip

the embedding of the components Gi, . . . , Gj(and to incidentally reverse their

order), while leaving the embedding of the other components of Gunchanged.

This is formalized in the following.

Lemma 3. There exists an O(n)-step 3D crossing-free morph from Γto a pla-

nar straight-line drawing Γ0of Gin which the embedding of G`is the ﬂip of the

1This is a point where our operations diﬀer from the ones of Angelini et al. [4]. Indeed,

their ﬂip operation applies to any sequence of components of G, while ours does not.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

MorphingPlanarGraphDrawingsThrough3D?KevinBuchin1,WillEvans2,FabrizioFrati3,IrinaKostitsyna4,MaartenLoer5,TimOphelders6,andAlexanderWol71TechnischeUniversitatDortmund,Germany,kevin.buchin@tu-dortmund.de2UniversityofBritishColumbia,Canada,will@cs.ubc.ca3RomaTreUniversity,Italy,fabrizio.frati@unir...

展开>> 收起<<

Morphing Planar Graph Drawings Through 3D Kevin Buchin1 Will Evans2 Fabrizio Frati3.pdf

共16页,预览4页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Morphing Planar Graph Drawings Through 3D Kevin Buchin1 Will Evans2 Fabrizio Frati3

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: