5.340. two_layer_edge_crossing

DESCRIPTIONLINKSGRAPH
Origin

Inspired by [HararySchwenk72].

Constraint

𝚝𝚠𝚘_πš•πšŠπš’πšŽπš›_𝚎𝚍𝚐𝚎_πšŒπš›πš˜πšœπšœπš’πš—πšπ™½π™²πšπ™Ύπš‚πš‚,πš…π™΄πšπšƒπ™Έπ™²π™΄πš‚_π™»π™°πšˆπ™΄πš1,πš…π™΄πšπšƒπ™Έπ™²π™΄πš‚_π™»π™°πšˆπ™΄πš2,π™΄π™³π™Άπ™΄πš‚

Arguments
π™½π™²πšπ™Ύπš‚πš‚πšπšŸπšŠπš›
πš…π™΄πšπšƒπ™Έπ™²π™΄πš‚_π™»π™°πšˆπ™΄πš1πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš’πš-πš’πš—πš,πš™πš˜πšœ-πšπšŸπšŠπš›)
πš…π™΄πšπšƒπ™Έπ™²π™΄πš‚_π™»π™°πšˆπ™΄πš2πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš’πš-πš’πš—πš,πš™πš˜πšœ-πšπšŸπšŠπš›)
π™΄π™³π™Άπ™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš’πš-πš’πš—πš,πšŸπšŽπš›πšπšŽπš‘1-πš’πš—πš,πšŸπšŽπš›πšπšŽπš‘2-πš’πš—πš)
Restrictions
π™½π™²πšπ™Ύπš‚πš‚β‰₯0
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™΄πšπšƒπ™Έπ™²π™΄πš‚_π™»π™°πšˆπ™΄πš1,[πš’πš,πš™πš˜πšœ])
πš…π™΄πšπšƒπ™Έπ™²π™΄πš‚_π™»π™°πšˆπ™΄πš1.πš’πšβ‰₯1
πš…π™΄πšπšƒπ™Έπ™²π™΄πš‚_π™»π™°πšˆπ™΄πš1.πš’πšβ‰€|πš…π™΄πšπšƒπ™Έπ™²π™΄πš‚_π™»π™°πšˆπ™΄πš1|
πšπš’πšœπšπš’πš—πšŒπš(πš…π™΄πšπšƒπ™Έπ™²π™΄πš‚_π™»π™°πšˆπ™΄πš1,πš’πš)
πšπš’πšœπšπš’πš—πšŒπš(πš…π™΄πšπšƒπ™Έπ™²π™΄πš‚_π™»π™°πšˆπ™΄πš1,πš™πš˜πšœ)
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™΄πšπšƒπ™Έπ™²π™΄πš‚_π™»π™°πšˆπ™΄πš2,[πš’πš,πš™πš˜πšœ])
πš…π™΄πšπšƒπ™Έπ™²π™΄πš‚_π™»π™°πšˆπ™΄πš2.πš’πšβ‰₯1
πš…π™΄πšπšƒπ™Έπ™²π™΄πš‚_π™»π™°πšˆπ™΄πš2.πš’πšβ‰€|πš…π™΄πšπšƒπ™Έπ™²π™΄πš‚_π™»π™°πšˆπ™΄πš2|
πšπš’πšœπšπš’πš—πšŒπš(πš…π™΄πšπšƒπ™Έπ™²π™΄πš‚_π™»π™°πšˆπ™΄πš2,πš’πš)
πšπš’πšœπšπš’πš—πšŒπš(πš…π™΄πšπšƒπ™Έπ™²π™΄πš‚_π™»π™°πšˆπ™΄πš2,πš™πš˜πšœ)
πš›πšŽπššπšžπš’πš›πšŽπš(π™΄π™³π™Άπ™΄πš‚,[πš’πš,πšŸπšŽπš›πšπšŽπš‘1,πšŸπšŽπš›πšπšŽπš‘2])
π™΄π™³π™Άπ™΄πš‚.πš’πšβ‰₯1
π™΄π™³π™Άπ™΄πš‚.πš’πšβ‰€|π™΄π™³π™Άπ™΄πš‚|
πšπš’πšœπšπš’πš—πšŒπš(π™΄π™³π™Άπ™΄πš‚,πš’πš)
π™΄π™³π™Άπ™΄πš‚.πšŸπšŽπš›πšπšŽπš‘1β‰₯1
π™΄π™³π™Άπ™΄πš‚.πšŸπšŽπš›πšπšŽπš‘1≀|πš…π™΄πšπšƒπ™Έπ™²π™΄πš‚_π™»π™°πšˆπ™΄πš1|
π™΄π™³π™Άπ™΄πš‚.πšŸπšŽπš›πšπšŽπš‘2β‰₯1
π™΄π™³π™Άπ™΄πš‚.πšŸπšŽπš›πšπšŽπš‘2≀|πš…π™΄πšπšƒπ™Έπ™²π™΄πš‚_π™»π™°πšˆπ™΄πš2|
Purpose

π™½π™²πšπ™Ύπš‚πš‚ is the number of line-segments intersections.

Example
2,πš’πš-1 πš™πš˜πšœ-1,πš’πš-2 πš™πš˜πšœ-2,πš’πš-1 πš™πš˜πšœ-3,πš’πš-2 πš™πš˜πšœ-1,πš’πš-3 πš™πš˜πšœ-2,πš’πš-1πšŸπšŽπš›πšπšŽπš‘1-2πšŸπšŽπš›πšπšŽπš‘2-2,πš’πš-2πšŸπšŽπš›πšπšŽπš‘1-2πšŸπšŽπš›πšπšŽπš‘2-3,πš’πš-3πšŸπšŽπš›πšπšŽπš‘1-1πšŸπšŽπš›πšπšŽπš‘2-1

FigureΒ 5.340.1 provides a picture of the example, where one can see the two line -segments intersections. Each line -segment of FigureΒ 5.340.1 is labelled with its identifier and corresponds to an item of the π™΄π™³π™Άπ™΄πš‚ collection. The two vertices on top of FigureΒ 5.340.1 correspond to the items of the πš…π™΄πšπšƒπ™Έπ™²π™΄πš‚_π™»π™°πšˆπ™΄πš1 collection, while the three other vertices are associated with the items of πš…π™΄πšπšƒπ™Έπ™²π™΄πš‚_π™»π™°πšˆπ™΄πš2.

Figure 5.340.1. Intersection between line-segments joining two layers
ctrs/two_layer_edge_crossing1
Symmetries
  • Arguments are permutable w.r.t. permutation (π™½π™²πšπ™Ύπš‚πš‚) (πš…π™΄πšπšƒπ™Έπ™²π™΄πš‚_π™»π™°πšˆπ™΄πš1,πš…π™΄πšπšƒπ™Έπ™²π™΄πš‚_π™»π™°πšˆπ™΄πš2) (π™΄π™³π™Άπ™΄πš‚).

  • Items of πš…π™΄πšπšƒπ™Έπ™²π™΄πš‚_π™»π™°πšˆπ™΄πš1 are permutable.

  • Items of πš…π™΄πšπšƒπ™Έπ™²π™΄πš‚_π™»π™°πšˆπ™΄πš2 are permutable.

Remark

The two-layer edge crossing minimisation problem was proved to be NP-hard inΒ [GareyJohnson83].

See also

common keyword: πšŒπš›πš˜πšœπšœπš’πš—πš, πšπš›πšŠπš™πš‘_πšŒπš›πš˜πšœπšœπš’πš—πšΒ (line-segments intersection).

Keywords

characteristic of a constraint: derived collection.

geometry: geometrical constraint, line-segments intersection.

miscellaneous: obscure.

Derived Collection
πšŒπš˜πš•π™΄π™³π™Άπ™΄πš‚_π™΄πš‡πšƒπšπ™΄π™Όπ™Έπšƒπ™Έπ™΄πš‚-πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš•πšŠπš’πšŽπš›1-πšπšŸπšŠπš›,πš•πšŠπš’πšŽπš›2-πšπšŸπšŠπš›),πš’πšπšŽπš–πš•πšŠπš’πšŽπš›1-π™΄π™³π™Άπ™΄πš‚.πšŸπšŽπš›πšπšŽπš‘1(πš…π™΄πšπšƒπ™Έπ™²π™΄πš‚_π™»π™°πšˆπ™΄πš1,πš™πš˜πšœ,πš’πš),πš•πšŠπš’πšŽπš›2-π™΄π™³π™Άπ™΄πš‚.πšŸπšŽπš›πšπšŽπš‘2(πš…π™΄πšπšƒπ™Έπ™²π™΄πš‚_π™»π™°πšˆπ™΄πš2,πš™πš˜πšœ,πš’πš)
Arc input(s)

π™΄π™³π™Άπ™΄πš‚_π™΄πš‡πšƒπšπ™΄π™Όπ™Έπšƒπ™Έπ™΄πš‚

Arc generator
πΆπΏπΌπ‘„π‘ˆπΈ(<)β†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(𝚎𝚍𝚐𝚎𝚜_πšŽπš‘πšπš›πšŽπš–πš’πšπš’πšŽπšœ1,𝚎𝚍𝚐𝚎𝚜_πšŽπš‘πšπš›πšŽπš–πš’πšπš’πšŽπšœ2)

Arc arity
Arc constraint(s)
β‹β‹€πšŽπšπšπšŽπšœ_πšŽπš‘πšπš›πšŽπš–πš’πšπš’πšŽπšœ1.πš•πšŠπš’πšŽπš›1<𝚎𝚍𝚐𝚎𝚜_πšŽπš‘πšπš›πšŽπš–πš’πšπš’πšŽπšœ2.πš•πšŠπš’πšŽπš›1,𝚎𝚍𝚐𝚎𝚜_πšŽπš‘πšπš›πšŽπš–πš’πšπš’πšŽπšœ1.πš•πšŠπš’πšŽπš›2>𝚎𝚍𝚐𝚎𝚜_πšŽπš‘πšπš›πšŽπš–πš’πšπš’πšŽπšœ2.πš•πšŠπš’πšŽπš›2,β‹€πšŽπšπšπšŽπšœ_πšŽπš‘πšπš›πšŽπš–πš’πšπš’πšŽπšœ1.πš•πšŠπš’πšŽπš›1>𝚎𝚍𝚐𝚎𝚜_πšŽπš‘πšπš›πšŽπš–πš’πšπš’πšŽπšœ2.πš•πšŠπš’πšŽπš›1,𝚎𝚍𝚐𝚎𝚜_πšŽπš‘πšπš›πšŽπš–πš’πšπš’πšŽπšœ1.πš•πšŠπš’πšŽπš›2<𝚎𝚍𝚐𝚎𝚜_πšŽπš‘πšπš›πšŽπš–πš’πšπš’πšŽπšœ2.πš•πšŠπš’πšŽπš›2
Graph property(ies)
𝐍𝐀𝐑𝐂=π™½π™²πšπ™Ύπš‚πš‚

Graph model

As usual for the two-layer edge crossing problem [HararySchwenk72],Β [DiBattistaEadesTamassiaTollis99], positions of the vertices on each layer are represented as a permutation of the vertices. We generate a derived collection that, for each edge, contains the position of its extremities on both layers. In the arc generator we use the restriction < in order to generate one single arc for each pair of segments. This is required, since otherwise we would count more than once a line-segments intersection.

PartsΒ (A) andΒ (B) of FigureΒ 5.340.2 respectively show the initial and final graph associated with the Example slot. Since we use the 𝐍𝐀𝐑𝐂 graph property, the arcs of the final graph are stressed in bold.

Figure 5.340.2. Initial and final graph of the 𝚝𝚠𝚘_πš•πšŠπš’πšŽπš›_𝚎𝚍𝚐𝚎_πšŒπš›πš˜πšœπšœπš’πš—πš constraint
ctrs/two_layer_edge_crossingActrs/two_layer_edge_crossingB
(a) (b)