Parameterized Approaches to Orthogonal Compaction Walter Didimo1 Siddharth Gupta2 Philipp Kindermann3

2025-05-02 0 0 3.02MB 40 页 10玖币
侵权投诉
Parameterized Approaches
to Orthogonal Compaction?
Walter Didimo1, Siddharth Gupta2, Philipp Kindermann3, Giuseppe Liotta1,
Alexander Wolff4, and Meirav Zehavi5
1Universit`a degli Studi di Perugia, Perugia, Italy
walter.didimo@unipg.it,giuseppe.liotta@unipg.it
2University of Warwick, Coventry, United Kingdom
siddharth.gupta.1@warwick.ac.uk
3Universit¨at Trier, Trier, Germany
kindermann@uni-trier.de
4Universit¨at W¨urzburg, W¨urzburg, Germany
5Ben-Gurion University of the Negev, Israel
zehavimeirav@gmail.com
Abstract.
Orthogonal graph drawings are used in applications such as
UML diagrams, VLSI layout, cable plans, and metro maps. We focus on
drawing planar graphs and assume that we are given an orthogonal repre-
sentation that describes the desired shape, but not the exact coordinates
of a drawing. Our aim is to compute an orthogonal drawing on the grid
that has minimum area among all grid drawings that adhere to the given
orthogonal representation.
This problem is called orthogonal compaction (OC) and is known to be
NP-hard, even for orthogonal representations of cycles [Evans et al. 2022].
We investigate the complexity of OC with respect to several parameters.
Among others, we show that OC is fixed-parameter tractable with respect
to the most natural of these parameters, namely, the number of kitty
corners of the orthogonal representation: the presence of pairs of kitty
corners in an orthogonal representation makes the OC problem hard.
Informally speaking, a pair of kitty corners is a pair of reflex corners of a
face that point at each other. Accordingly, the number of kitty corners is
the number of corners that are involved in some pair of kitty corners.
Keywords:
Orthogonal Graph Drawing
·
Orthogonal Representation
·
Compaction ·Parameterized Complexity
1 Introduction
In a planar orthogonal drawing of a planar graph
G
each vertex is mapped to a
distinct point of the plane and each edge is represented as a sequence of horizontal
?
This research was initiated at Dagstuhl Seminar 21293: Parameterized Complexity
in Graph Drawing. Work partially supported by: (i) Dep. of Engineering, Perugia
University, grant RICBA21LG: Algoritmi, modelli e sistemi per la rappresentazione
visuale di reti, (ii) Engineering and Physical Sciences Research Council (EPSRC) grant
EP/V007793/1, (v) European Research Council (ERC) grant termed PARAPATH.
arXiv:2210.05019v1 [cs.CG] 10 Oct 2022
2 Didimo, Gupta, Kindermann, Liotta, Wolff, and Zehavi
and vertical segments. A planar graph
G
admits a planar orthogonal drawing if
and only if it has vertex-degree at most four. A planar orthogonal representation
H
of
G
is an equivalence class of planar orthogonal drawings of
G
that have the
same “shape”, i.e., the same planar embedding, the same ordered sequence of
bends along the edges, and the same vertex angles. A planar orthogonal drawing
belonging to the equivalence class
H
is simply called a drawing of
H
. For example,
Figs. 1a and 1b are drawings of the same orthogonal representation, while Fig. 1c
is a drawing of the same graph with a different shape.
Given a planar orthogonal representation
H
of a connected planar graph
G
,
the orthogonal compaction problem (OC for short) for
H
asks to compute a
minimum-area drawing of
H
. More formally, it asks to assign integer coordinates
to the vertices and to the bends of
H
such that the area of the resulting planar
orthogonal drawing is minimum over all drawings of
H
. The area of a drawing is
the area of the minimum bounding box that contains the drawing. For example,
the drawing in Fig. 1a has area 7
×
5 = 35, whereas the drawing in Fig. 1b has
area 7 ×4 = 28, which is the minimum for that orthogonal representation.
The area of a graph layout is considered one of the most relevant readability
metrics in orthogonal graph drawing (see, e.g., [
16
,
26
]). Compact grid drawings
are desirable as they yield a good overview without neglecting details. For this
reason, the OC problem is widely investigated in the literature. Bridgeman et
al. [
11
] showed that OC can be solved in linear time for a subclass of planar
orthogonal representations called turn-regular. Informally speaking, a face of a
planar orthogonal representation
H
is turn-regular if it does not contain any pair
of so-called kitty corners, i.e., a pair of reflex corners (turns of 270
◦
) that point
to each other; a representation is turn-regular if all its faces are turn-regular.
See Fig. 1 and refer to Section 2 for a formal definition. On the other hand,
Patrignani [30] proved that, unfortunately, OC is NP-hard in general. Evans et
al. [
22
] showed that OC remains NP-hard even for orthogonal representations of
simple cycles. Since cycles have constant pathwidth (namely 2), this immediately
shows that we cannot expect an FPT (or even an XP) algorithm parameterized
by pathwidth alone unless P = NP. The same holds for parametrizations with
respect to treewidth since the treewidth of a graph is upper bounded by its
pathwidth.
In related work, Bannister et al. [
3
] showed that several problems of compacting
not necessarily planar orthogonal graph drawings to use the minimum number of
rows, area, length of longest edge, or total edge length cannot be approximated
better than within a polynomial factor of optimal (if P
6
=NP). They also provided
an FPT algorithm for testing whether a drawing can be compacted to a small
number of rows. Note that their algorithm does not solve the planar case because
the algorithm is allowed to change the embedding.
The research in this paper is motivated by the relevance of the OC problem
and by the growing interest in parameterized approaches for NP-hard prob-
lems in graph drawing [
24
]. Recent works on the subject include parameterized
algorithms for book embeddings and queue layouts [
2
,
7
,
8
,
10
,
27
], upward pla-
nar drawings [
10
,
12
], orthogonal planarity testing and grid recognition [
18
,
25
],
Parameterized Approaches to Orthogonal Compaction 3
v
u
w
z
7
5
(a) area = 35
v
u
w
z
7
4
(b) area = 28
u
v
w
z
6
4
(c) area = 24
Fig. 1:
(a) Drawing of a non-turn-regular orthogonal representation
H
; vertices
u
and
v
point to each other in the filled internal face, thus they represent a pair of kitty corners.
Vertices
w
and
z
are a pair of kitty corners in the external face. (b) Another drawing
of
H
with minimum area. (c) Minimum-area drawing of a turn-regular orthogonal
representation of the same graph.
clustered planarity and hybrid planarity [
15
,
28
,
29
], 1-planar drawings [
1
], and
crossing minimization [4,20,21].
Contribution. Extending this line of research, we initiate the study of the param-
eterized complexity of OC and investigate several parameters:
–
Number of kitty corners. Given that OC can be solved efficiently for orthogo-
nal representations without kitty corners, the number of kitty corners (that
is, the number of corners involved in some pair of kitty corners) is a very
natural parameter for OC. We show that OC is fixed-parameter tractable
(FPT) with respect to the number of kitty corners (Theorem 1 in Section 3).
–
Number of faces. Since OC remains NP-hard for orthogonal representations
of simple cycles [
22
], OC is para-NP-hard when parameterized by the number
of faces. Hence, we cannot expect an FPT (or even an XP) algorithm in this
parameter alone, unless P = NP. However, for orthogonal representations of
simple cycles we show the existence of a polynomial kernel for OC when
parameterized by the number of kitty corners (Theorem 2 in Section 4).
–
Maximum face-degree. The maximum face-degree is the maximum number of
vertices on the boundary of a face. Since both the NP-hardness reductions by
Patrignani [
30
] and Evans et al. [
22
] require faces of linear size, it is interesting
to know whether faces of constant size make the problem tractable. We prove
that this is not the case, i.e., OC remains NP-hard when parameterized by
the maximum face degree (Theorem 3 in Section 5).
–
Height. The height of an orthogonal representation is the minimum number
of distinct y-coordinates required to draw the representation. Since a
w×h
grid has pathwidth at most
h
, graphs with bounded height have bounded
pathwidth, but the converse is generally not true [
9
]. In fact, we show that
OC admits an XP algorithm parameterized by the height of the given
representation (see Theorem 4 in Section 6). In this context, we remark
that a related problem has been considered by Chaplick et al. [
13
]. Given a
4 Didimo, Gupta, Kindermann, Liotta, Wolff, and Zehavi
planar graph
G
, they defined
¯π1
2
(
G
) to be the minimum number of distinct
y-coordinates required to draw the graph straight-line. (In their version of
the problem, however, the embedding of Gis not fixed.)
We start with some basics in Section 2 and close with open problems in Section 7.
Theorems marked with a (clickable) ?are proven in detail in the appendix.
2 Basic Definitions
Let
G
= (
V, E
) be a connected planar graph of vertex-degree at most four and let
Γ
be a planar orthogonal drawing of
G
. We assume that in
Γ
all the vertices and
bends have integer coordinates, i.e., we assume that
Γ
is an integer-coordinate
grid drawing. Two planar orthogonal drawings
Γ1
and
Γ2
of
G
are shape-equivalent
if: (
i
)
Γ1
and
Γ2
have the same planar embedding; (
ii
) for each vertex
v∈V
,
the geometric angles at
v
(formed by any two consecutive edges incident on
v
)
are the same in
Γ1
and
Γ2
; (
iii
) for each edge
e
= (
u, v
)
∈E
the sequence of left
and right bends along
e
while moving from
u
to
v
is the same in
Γ1
and
Γ2
. An
orthogonal representation
H
of
G
is a class of shape-equivalent planar orthogonal
drawings of
G
. It follows that an orthogonal representation
H
is completely
described by a planar embedding of
G
, by the values of the angles around each
vertex (each angle being a value in the set
{
90
◦,
180
◦,
270
◦,
360
◦}
), and by the
ordered sequence of left and right bends along each edge (
u, v
), moving from
u
to
v
; if we move from
v
to
u
, then this sequence and the direction (left/right) of
each bend are reversed. If
Γ
is a planar orthogonal drawing in the class
H
, then
we also say that
Γ
is a drawing of
H
. Without loss of generality, we also assume
that an orthogonal representation
H
comes with a given “orientation”, i.e., for
each edge segment
pq
of
H
(where
p
and
q
correspond to vertices or bends), we
fix whether plies to the left, to the right, above, or below q.
Turn-regular orthogonal representations. Let
H
be a planar orthogonal represen-
tation. For the purpose of the OC problem, and without loss of generality, we
always assume that each bend in
H
is replaced by a degree-2 vertex. Let
f
be a
face of a planar orthogonal representation
H
and assume that the boundary of
f
is traversed counterclockwise (resp. clockwise) if
f
is internal (resp. external). Let
u
and
v
be two reflex vertices of
f
. Let
rot
(
u, v
) be the number of convex corners
minus the number of reflex corners encountered while traversing the boundary
of
f
from
u
(included) to
v
(excluded); a reflex vertex of degree one is counted
like two reflex vertices. We say that
u
and
v
is a pair of kitty corners of
f
if
rot
(
u, v
) = 2 or
rot
(
v, u
) = 2. A vertex is a kitty corner if it is part of a pair of
kitty corners. A face
f
of
H
is turn-regular if it does not contain a pair of kitty
corners. The representation His turn-regular if all faces are turn-regular.
For information on parameterized complexity, we refer to books such as
[14,19,23] and Appendix A.
Parameterized Approaches to Orthogonal Compaction 5
L
L
L
L
L
L
L
L
(a)
t
s
(b)
Fig. 2:
(a) An upward plane DAG
D
and the corresponding upward labeling. (b) A
plane st-graph obtained by augmenting Dwith a complete saturator (dotted edges).
3 Number of Kitty Corners: An FPT Algorithm
Turn-regular orthogonal representation can be compacted optimally in linear
time [11]. We recall this result and then describe our FPT algorithm.
Upward planar embeddings and saturators. Let
D
= (
V, E
) be a plane DAG, i.e.,
an acyclic digraph with a given planar embedding. An upward planar drawing
Γ
of
D
is an embedding-preserving drawing of
D
where each vertex
v
is mapped
to a distinct point of the plane and each edge is drawn as a simple Jordan arc
monotonically increasing in the upward direction. Such a drawing exists if and
only if
D
is the spanning subgraph of a plane
st
-graph, i.e., a plane digraph with
a unique source
s
and a unique sink
t
, which are both on the external face [
17
].
Let
S
be the set of sources of
D
,
T
be the set of sinks, and
I
=
V\
(
S∪T
).
D
is bimodal if, for every vertex
v∈I
, the outgoing edges (and hence the incoming
edges) of
v
are consecutive in the clockwise order around
v
. If an upward planar
drawing
Γ
of
D
exists, then
D
is necessarily bimodal and
Γ
uniquely defines the
left-to-right orderings of the outgoing and incoming edges of each vertex. This
set of orderings (for all vertices of
D
) is an upward planar embedding of
D
, and
is regarded an equivalence class of upward planar drawings of
D
. A plane DAG
with a given upward planar embedding is an upward plane DAG.
Let
e1
and
e2
be two consecutive edges on the boundary of a face
f
of a
bimodal plane digraph
D
, and let
v
be their common vertex. Vertex
v
is a source
switch of
f
(resp. a sink switch of
f
) if both
e1
and
e2
are outgoing edges (resp.
incoming edges) of
v
. Note that, for each face
f
, the number
nf
of source switches
of
f
equals the number of sink switches of
f
. The capacity of
f
is the function
cap
(
f
) =
nf−
1 if
f
is an internal face and
cap
(
f
) =
nf
+ 1 if
f
is the external
face. If
Γ
is an upward planar drawing of
D
, then each vertex
v∈S∪T
has
exactly one angle larger than 180
◦
, called a large angle, in one of its incident faces,
and
deg
(
v
)
−
1 angles smaller than 180
◦
, called small angles, in its other incident
faces. For a source or sink switch of f, assign either a label Lor a label Sto its
angle in
f
, depending on whether this angle is large or small. For each face
f
摘要：

ParameterizedApproachestoOrthogonalCompaction?WalterDidimo1,SiddharthGupta2,PhilippKindermann3,GiuseppeLiotta1,AlexanderWol 4,andMeiravZehavi51UniversitadegliStudidiPerugia,Perugia,Italywalter.didimo@unipg.it,giuseppe.liotta@unipg.it2UniversityofWarwick,Coventry,UnitedKingdomsiddharth.gupta.1@warwi...

展开>> 收起<<
Parameterized Approaches to Orthogonal Compaction Walter Didimo1 Siddharth Gupta2 Philipp Kindermann3.pdf

共40页,预览5页

还剩页未读， 继续阅读

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

相关推荐

更多
立即下载
分类：图书资源 价格：10玖币 属性：40 页 大小：3.02MB 格式：PDF 时间：2025-05-02

开通VIP享超值会员特权

  • 多端同步记录
  • 高速下载文档
  • 免费文档工具
  • 分享文档赚钱
  • 每日登录抽奖
  • 优质衍生服务

作者详情

相关内容

更多

热门标签

人际关系 动力学连接体 力的合成 配电装置 高考理综 全宋诗作者索引 公务员考试
/ 40
评分 收藏
分享
立即下载
客服
关注