Non-Crossing Shortest Paths are Covered with Exactly Four Forests Lorenzo Balzotti
2025-05-02
0
0
640.81KB
25 页
10玖币
侵权投诉
Non-Crossing Shortest Paths are Covered with Exactly
Four Forests
Lorenzo Balzotti∗
Abstract
Given a set of paths Pwe define the Path Covering with Forests Number of P(PCFN(P))
as the minimum size of a set Fof forests satisfying that every path in Pis contained in at
least one forest in F. We show that PCFN(P) is treatable when Pis a set of non-crossing
shortest paths in a plane graph or subclasses. We prove that if Pis a set of non-crossing
shortest paths of a planar graph Gwhose extremal vertices lie on the same face of G, then
PCFN(P)≤4, and this bound is tight.
Keywords: shortest paths, planar undirected graphs, non-crossing paths, Path Covering with
Forests Number
1 Introduction
In this article we investigate the structure of particular sets of paths. Given a set of paths Pwe
define the Path Covering with Forests Number of P(PCFN(P)) as the minimum size of a set F
of forests satisfying that every path in Pis contained in at least one forest in F. A trivial upper
bound is PCFN(P)≤ |P|, in which every forest is composed exactly by one path.
We note that if there are different subpaths joining the same pair of vertices, then it may
happen PCFN(P) = |P|. This cannot happen if Pis a set of shortest paths, such that there is a
unique shortest path for any pair of vertices. We deal with a slightly more general case for which
we require the single-touch property: given two paths in P, their intersection is still a path. If
all paths in Pare shortest paths in G, then the single-touch property is implied by ensuring the
uniqueness of the shortest path in G, that can be obtained through a tiny perturbation of edges’
weights (of G).
There is a very restricted literature dealing with this problem for general graph, a first recent
result by Bodwin [14] in 2019 develops a structural theory of unique shortest paths in real weighted
graphs: the author characterizes exactly which sets of node sequences can be realized as unique
shortest paths in a graph with arbitrary real edge weights. The characterizations are based on a
new connection between shortest paths and topology; in particular, the new forbidden patterns
are in natural correspondence with two-colored topological 2-manifolds, which are visualized as
polyhedra. Even if finding shortest paths is a classical problem with applications in several fields,
there are not other results focused on shortest paths’ structure.
We prove that if Pis a set of non-crossing shortest paths in a plane (i.e., a planar graph with
a fixed embedding) undirected graph G, whose extremal vertices lie on the same face of G, then
PCFN(P)≤4, and this bound is tight, where two paths are non-crossing if they do not cross each
other in the given embedding.
We first explain that this setting, i.e., non-crossing paths in plane graphs, is not too restrictive.
Removing the non-crossing property makes PCFN(P) dependent on the dimension of P. We briefly
prove this with an example. In Figure 1 there are six pairwise crossing paths in a grid graph having
the extremal vertices on the same face of G. Note that any set of three paths forms a cycle, hence,
each forest can contain at most two paths. So the Path Covering with Forests Number of these six
paths is three. It is trivial to generalize this example to a set Pof single-touch shortest paths in
a plane graph whose extremal vertices lie on the same face so that PCFN(P) = |P|/2.
∗Dipartimento di Scienze di Base e Applicate per l’Ingegneria, Sapienza Universit`a di Roma, Via Antonio Scarpa,
16, 00161 Roma, Italy. lorenzo.balzotti@sbai.uniroma1.it.
1
arXiv:2210.13036v1 [math.CO] 24 Oct 2022
v1
v2
v3
v4
v5
v6
Figure 1: a set Pof pairwise crossing paths satisfying PCFN(P) = |P|/2. If edges incident on vi,
for i∈[6], have weight less than 1 and other edges have weight 1, then colored paths are unique
shortest paths between their extremal vertices.
Our result about the Path Covering with Forests Number of non-crossing shortest paths in
plane undirected graphs answers to the open problem by Balzotti and Franciosa [8], asking for an
algorithm able to list a path in a time proportional to its length. Indeed, all algorithms that find
non-crossing shortest paths in plane graphs [10, 50, 51] actually find their union, and so listing a
path is not trivial. In this way, we can apply the result by Gabow and Tarjan [21] about lowest
common ancestor queries, hence it is possible to list each path in Pin time proportional to its
length. This application was the idea behind the introduction of the Path Covering with Forests
Number.
Finding non-crossing shortest paths in a plane graph is a problem with primary applications in
VLSI layout [13, 37, 38], and thanks to the article by Reif [47] it is also used to compute the max
flow in undirected plane graphs [30, 33] and vitality problems [9]. The above cited articles [51, 50]
solve this problem for positive weighted graphs , while in [10] a linear time algorithm is shown for
the unweighted case. In this settings, the extremal vertices of the non-crossing shortest path are
always on the same face of the planar embedding (in [51] it is also studied the case in which the
extremal vertices are on two faces), while in [20] the extremal vertices are on hface boundaries.
It is stated in [20] that the union of a set Pof non-crossing shortest paths in a plane graph whose
extremal vertices lie on the same face can be covered with at most two forests so that each path
is contained in at least one forest, i.e., PCFN(P) = 2. We stress that this result is incorrect, a
first counterexample is shown in Figure 2 whose Path Covering with Forests Number is 3 (it can
be proved by a simple enumeration).
Figure 2: a set of 15 non-crossing paths whose Path Covering with Forests Number is 3 (parallel
adjacent segments represent overlapping paths).
Related problems The Path Covering with Forests Number is strictly linked to the concept of
arboricity. The arboricity of an undirected graph Gis the minimum number of forests γf(G) into
which its edges can be partitioned. It measures how a graph is dense, indeed, graphs with many
edges have high arboricity, and graphs with high arboricity must have a dense subgraph. By the
well-known Nash-Williams Theorem [41] (proved also independently by Tutte [52])
γf(G) = max
X⊆V(G)|E(G[X])|
|X| − 1
where G[X] denotes the subgraph of Ginduced by X. The fractional arboricity was introduced
by Payan in [44], see also [17, 22]. Arboricity is studied for general graphs and it is specialized for
planar graph and subclasses of planar graphs. By the above cited Nash-Williams Theorem [41],
every planar graph has arboricity 3, i.e., every planar graph can be covered with at most 3 forests,
and if it has girth greater or equal to 4, then it decomposes into two forests. In [24, 31] planar
graphs with girth larger than some constant are decomposed into a forest and a graph with bounded
2
degree. Decomposition of planar graphs into a forest and a matching has been studied in [11, 15,
16, 31, 39, 53].
Arboricity is one of the many faces of graphs covering [12, 28, 29, 42] which is a classical
problem in graph theory. A recent and complete overview about covering problems can be found
in [49]. The classical covering problem asks for covering an input graph Hwith graphs from
a fixed covering class G. Some variants of the problems are in [36]. In the arboricity problem
the family Gconsists in forests. Other kinds of arboricity have been introduced in literature,
as star arboricity [3, 4, 6], caterpillar arboricity [23, 25], linear arboricity [2, 5, 46, 54], pseudo
arboricity [27, 45] in which graphs are covered with star forests, caterpillar forests, linear forests,
and pseudoforests (undirected graphs in which every connected component has at most one cycle),
respectively.
If the covering class is the class of planar graph, outerplanar graph, or interval graph, then we
deal with planar thickness [12], outerplanar thickness [40] or track number [26], respectively.
Future works With the introduction of the Path Covering with Forests Number, we propose an
original nuance on the classical covering problem and we would like to deal with the Path Covering
with Forests Number in a more general context. The first generalization is to ask whether the
Path Covering with Forests Number of a set of non-crossing single-touch shortest paths in a plane
graph is bounded by a constant, even if the extremal vertices of the paths are not required to lie
on the same face. We conjecture that such a constant exists for general plane graph thanks also
to the following remark, whose proof is omitted.
Remark 1. Let Pbe a set of non-crossing single-touch shortest paths in a plane graph Gand let
vbe a vertex of G. Then all paths of Pcontaining vform a tree.
Conjecture 1. There exists `∈Nsuch that PCFN(P)≤`, for any set Pof non-crossing single-
touch shortest paths in a plane graph.
The Path Covering with Forests Number can be studied also for a set of paths Pbeyond planar
graphs, as in k-planar graphs [43], k-quasi-planar graphs [1], RAC graphs [19], fan-crossing-free
graphs [18], fan-planar graphs [35], k-gap-planar graphs [7]; a complete survey about these graph
classes can be found in [32].
It would be interesting to investigate the Path Covering with Forests Number in the case of
crossing paths in plane graphs or related graph classes. As shown in Figure 1, for a set of crossing
paths Pits Path Covering with Forests Number may depend on |P|. To deal with these cases
it is necessary to understand “how much” the paths cross each others. In [48] several notions
about crossing, crossing number and variants are explained, thus the Path Covering with Forests
Number can be studied with respect to these measures. We note that in [48] the notions are given
for graphs, but they can be extended to sets of paths.
Clearly, the Path Covering with Forests Number can be generalized to other covering families as
done for the arboricity or the classical covering problem. Thus we can introduce, for example, the
Path Covering with Stars Number, the Path Covering with Caterpillars Number, Path Covering
with Planars Number and so on.
Our approach In a first step we organize all the paths into a partial order named genealogy tree.
Then we translate the Path Covering with Forests Number into a problem of forest labeling, i.e., a
labeling assigning labels to paths such that then union of paths with a same label is a forest. The
number of distinct labels corresponds to the upper bound of Path Covering with Forests Number.
A crucial result is that we can establish whether a labeling is a forest labeling by restricting the
check only to the faces of the graph resulting from the union of the paths. At this point the main
result is reached by three steps: first we prove that the Path Covering with Forests Number is
constant by introducing a simple algorithm FifteenForests able to give a forest labeling which
uses at most 15 labels (see Theorem 2 and Corollary 1); then we refine this algorithm obtaining
algorithm FourForests able to give a forest labeling which uses at most 4 labels; finally we show
that this result is tight by exhibiting a set of non-crossing shortest paths in a plane graph whose
Path Covering with Forests Number is at least 4 (we recall that in Figure 2 there is a set of
non-crossing shortest paths Psuch that PCFN(P) = 3). This proves our main result.
3
Now we briefly explain the strategy behind our algorithms. We recursively decompose all the
paths with respect to the genealogy tree and intersections between paths. In this way, at each
iteration our algorithms have to assign labels only to paths intersecting a fixed path p.
Structure of the article In Section 2 preliminaries notations and definitions are given, we also
propose a labeling approach for our problem. In Section 3 we prove that we can restrict us only
to U’s faces, where Uis the graph obtained by the union of all non-crossing shortest paths. In
Section 4 we prove that the Path Covering with Forests Number of a set of non-crossing shortest
paths in a plane graph is at most 15. In Section 5 we decrease this bound to 4. Finally, in Section 6
we show that the latter bound is tight. Conclusions are in Section 7.
2 Preliminaries
In this section we introduce some definitions and notations. In Subsection 2.1 we give general
notation. In Subsection 2.2 we formally define the problem and we describe our labeling approach.
In Subsection 2.3 we partially order the non-crossing shortest paths by the genealogy tree.
2.1 Notations
All graphs in this article are undirected. Let G= (V, E) be a graph, where Vis a set of vertices
and Eis a collection of pairs of vertices called edges. We recall standard union and intersection
operators on graphs.
Definition 1. Given two graphs G= (V(G), E(G)) and H= (V(H), E(H)), we define the fol-
lowing operations and relations:
•G∪H= (V(G)∪V(H), E(G)∪E(H)),
•G∩H= (V(G)∩V(H), E(G)∩E(H)),
•H⊆G⇐⇒ V(H)⊆V(G)and E(H)⊆E(G),
•G\H= (V(G), E(G)\E(H)).
Given a graph G= (V(G), E(G)), given an edge eand a vertex vwe write, for short, e∈Gin
place of e∈E(G) and v∈Gin place of v∈V(G).
We denote by uv the edge whose endpoints are uand v. We use angle brackets to denote
ordered sets. For example, {a, b, c}={c, a, b}and (a, b, c)6= (c, a, b). Moreover, for every `∈Nwe
denote by [`] the set {1, . . . , `}.
Given a path p∈Pand two vertices u, v of p, we define p[u, v] the subpath of pfrom uto v.
We say that a path pis an ab path if its extremal vertices are aand b. For an ab path qand a bc
path r, we define q◦ras the (possibly not simple) path obtained by the concatenation of qand r.
We denote by f∞
Gthe external face of a plane graph G, if no confusions arise we remove the
subscript G.
For a simple cycle Cof a plane graph G, we define the region bounded by Cthe maximal
subgraph of Gwhose external face has Cas boundary.
2.2 The problem and a labeling approach
In this subsection we give a formally definition of our problem and we introduce a labeling approach.
From now on Gdenotes a plane graph and f∞denotes the external face of G. For convenience,
we assume that the extremal vertices of paths in Plie on f∞.
Definition 2. Two paths pand qare single-touch if their intersection is still a (possibly empty)
path.
4
We observe that the single-touch property can be always required for a set of shortest paths,
and it also known as consistent property in the literature of path systems [14]. We stress that
in this article we use the single-touch property rather than the property of being shortest paths.
Indeed, it is easy to describe a set Pof knon-crossing shortest paths in a plane graphs whose Path
Covering with Forests Number is k−1 if the single-touch property is not required.
Definition 3. Given a set of paths Pwe say that Pis a set of non-crossing shortest paths (NCSP)
if there exists a plane graph Gsuch that
•for each p∈P, the extremal vertices of pare in f∞,
•for each p∈P,pis a shortest path in Gand Pis a set of single-touch paths,
•for each p, q ∈P,pand qare non-crossing in G.
We observe that the single-touch property can be always required for a set of shortest paths, and
it also known as consistent property in the literature of path systems [14]. Indeed, the single-touch
property is implied by ensuring the uniqueness of the shortest path in G, that can be obtained
through a tiny perturbation of edges’ weights. We stress that in this chapter we use the single-
touch property rather than the property of being shortest paths. Indeed, it is easy to describe a set
Pof knon-crossing shortest paths in a plane graphs whose Path Covering with Forests Number is
k−1 if the single-touch property is not required.
From now on, if no confusions arise, given a NCSP P,Gis the plane graph in Definition 3.
We study the Path Covering with Forests Number of a NCSP Pby using a labeling function that
assigns labels to paths in P. So we say that a function L:Q7→ [k] is a path labeling of Pif L
assigns one value of [k] to each path in Q, for some k∈Nand Q⊆P. If no confusion arises, then
we omit the dependence on P.
Definition 4. Given a NCSP P, given a path labeling Lof P,L:P7→ [k], we say that Lis a
forest labeling if S{p∈P| L(p)=i}pis a forest for each i∈[k].
We extend the definition of labeling to a set of paths Qby denoting L(Q) = Sq∈QL(q).
Moreover, given an edge e, we define L(e) = L({q∈P|e∈E(q)}), hence, L(e) may contain more
colors.
For a path p, we denote its extremal vertices by xpand yp. W.l.o.g., we assume that the
terminal pairs are distinct, i.e., there is no pair p, q ∈Psuch that {xp, yp}={xq, yq}. Let γpbe
the path in f∞that goes clockwise from xpto yp, for p∈P. We say that pairs {(xp, yp)}p∈P
are well-formed if for all q, r ∈Peither γq⊆γror γr⊇γqor γqand γrshare no edges. We
note that if terminal pairs are well-formed, then there always exists a set of pairwise non-crossing
shortest paths, each one joining a pair. The revers is not true if some paths are subpaths of the
infinite face of G; this case is not interesting in the applications and it has never been studied in
literature, where the terminal pairs are always assumed to be well-formed. Hence we assume that
pairs {(xp, yp)}p∈Pare well-formed.
Finally, we observe that the non-crossing and single-touch properties of the paths imply that
the embedding of the paths is unique; this fact is formally proved in [8].
2.3 Genealogy tree
Given a NCSP P, we define here a partial ordering as in [51] that represents the inclusion relation
between the γp’s. This relation intuitively corresponds to an adjacency relation between non-
crossing shortest paths joining each pair.
Choose an arbitrary p1∈Psuch that there are neither xqnor yq, with q6=p1and q∈P,
walking on f∞from xp1to yp1(either clockwise or counterclockwise), and let e1be an arbitrary
edge on that walk. For each q∈P, we can assume that e16∈ γq, indeed if it is not true, then it
suffices to switch xqwith yq. Given p, q ∈P, We say that pqif γp⊆γq. We define the genealogy
tree TP
gof Pas the transitive reduction of poset (P, ); if no confusion arises, then we omit the
apex P. We consider TP
gas a rooted tree.
If pq, then we say that pis a descendant of qand qis an ancestor of p. Given p, q ∈P, we
say that pand qare uncomparable if pqand qp.
5
摘要：
展开>>
收起<<
Non-CrossingShortestPathsareCoveredwithExactlyFourForestsLorenzoBalzotti*AbstractGivenasetofpathsPwede nethePathCoveringwithForestsNumberofP(PCFN(P))astheminimumsizeofasetFofforestssatisfyingthateverypathinPiscontainedinatleastoneforestinF.WeshowthatPCFN(P)istreatablewhenPisasetofnon-crossingshortes...
声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！
相关推荐
-
架构演进：小米的经验分享VIP免费
2025-03-31 5 -
Discrete-time Flatness and Linearization along Trajectories Bernd KolarJohannes DiwoldConrad Gst ottner
2025-05-03 0 -
Discrete orthogonality of the polynomial sequences in the q-Askey scheme
2025-05-03 0 -
Discovering New Intents Using Latent Variables Yunhua Zhou Peiju Liu Yuxin Wang Xipeng Qiu School of Computer Science Fudan University
2025-05-03 0 -
Discovering Differences in the Representation of People using Contextualized Semantic Axes Li Lucy Divya Tadimeti and David Bamman
2025-05-03 0 -
Discovering Design Concepts for CAD Sketches Yuezhi Yang The University of Hong Kong
2025-05-03 0 -
Discourse-Aware Emotion Cause Extraction in Conversations Dexin Kong1 Nan Yu1 Yun Yuan1 Guohong Fu12 Chen Gong12 1School of Computer Science and Technology Soochow University China
2025-05-03 1 -
Discourse Context Predictability Effects in Hindi Word Order Sidharth Ranjan IIT Delhi
2025-05-03 0 -
DISCO SENSE Commonsense Reasoning with Discourse Connectives Prajjwal Bhargava University of Texas at Dallas
2025-05-03 0 -
Discharge of elongated grains in silos under rotational shear Tivadar Pong o12Tam as B orzs onyi2and Ra ul Cruz Hidalgo1 1F sica y Matem atica Aplicada Facultad de Ciencias Universidad de Navarra Pamplona Spain
2025-05-03 0
分类：图书资源
价格：10玖币
属性：25 页
大小：640.81KB
格式：PDF
时间：2025-05-02
作者详情
相关内容
-
Discovering Design Concepts for CAD Sketches Yuezhi Yang The University of Hong Kong
分类：图书资源
时间：2025-05-03
标签：无
格式：PDF
价格：10 玖币
-
Discourse-Aware Emotion Cause Extraction in Conversations Dexin Kong1 Nan Yu1 Yun Yuan1 Guohong Fu12 Chen Gong12 1School of Computer Science and Technology Soochow University China
分类：图书资源
时间：2025-05-03
标签：无
格式：PDF
价格：10 玖币
-
Discourse Context Predictability Effects in Hindi Word Order Sidharth Ranjan IIT Delhi
分类：图书资源
时间：2025-05-03
标签：无
格式：PDF
价格：10 玖币
-
DISCO SENSE Commonsense Reasoning with Discourse Connectives Prajjwal Bhargava University of Texas at Dallas
分类：图书资源
时间：2025-05-03
标签：无
格式：PDF
价格：10 玖币
-
Discharge of elongated grains in silos under rotational shear Tivadar Pong o12Tam as B orzs onyi2and Ra ul Cruz Hidalgo1 1F sica y Matem atica Aplicada Facultad de Ciencias Universidad de Navarra Pamplona Spain
分类：图书资源
时间：2025-05-03
标签：无
格式：PDF
价格：10 玖币
渝公网安备50010702506394
