5.145. graph_crossing

DESCRIPTIONLINKSGRAPH
Origin

N.Β Beldiceanu

Constraint

πšπš›πšŠπš™πš‘_πšŒπš›πš˜πšœπšœπš’πš—πš(π™½π™²πšπ™Ύπš‚πš‚,π™½π™Ύπ™³π™΄πš‚)

Synonyms

πšŒπš›πš˜πšœπšœπš’πš—πš, πš—πšŒπš›πš˜πšœπšœ.

Arguments
π™½π™²πšπ™Ύπš‚πš‚πšπšŸπšŠπš›
π™½π™Ύπ™³π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(𝚜𝚞𝚌𝚌-πšπšŸπšŠπš›,𝚑-πš’πš—πš,𝚒-πš’πš—πš)
Restrictions
π™½π™²πšπ™Ύπš‚πš‚β‰₯0
πš›πšŽπššπšžπš’πš›πšŽπš(π™½π™Ύπ™³π™΄πš‚,[𝚜𝚞𝚌𝚌,𝚑,𝚒])
π™½π™Ύπ™³π™΄πš‚.𝚜𝚞𝚌𝚌β‰₯1
π™½π™Ύπ™³π™΄πš‚.πšœπšžπšŒπšŒβ‰€|π™½π™Ύπ™³π™΄πš‚|
Purpose

π™½π™²πšπ™Ύπš‚πš‚ is the number of proper intersections between line-segments, where each line-segment is an arc of the directed graph defined by the arc linking a node and its unique successor.

Example
2,𝚜𝚞𝚌𝚌-1𝚑-4𝚒-7,𝚜𝚞𝚌𝚌-1𝚑-2𝚒-5,𝚜𝚞𝚌𝚌-1𝚑-7𝚒-6,𝚜𝚞𝚌𝚌-2𝚑-1𝚒-2,𝚜𝚞𝚌𝚌-3𝚑-2𝚒-2,𝚜𝚞𝚌𝚌-2𝚑-5𝚒-3,𝚜𝚞𝚌𝚌-3𝚑-8𝚒-2,𝚜𝚞𝚌𝚌-9𝚑-6𝚒-2,𝚜𝚞𝚌𝚌-10𝚑-10𝚒-6,𝚜𝚞𝚌𝚌-8𝚑-10𝚒-1

FigureΒ 5.145.1 shows the line-segments associated with the π™½π™Ύπ™³π™΄πš‚ collection. One can note the following line-segments intersection:

  • Arcs 8β†’9 and 7β†’3 cross,

  • Arcs 5β†’3 and 6β†’2 cross also.

Consequently, the πšπš›πšŠπš™πš‘_πšŒπš›πš˜πšœπšœπš’πš—πš constraint holds since its first argument π™½π™²πšπ™Ύπš‚πš‚ is set to 2.

Figure 5.145.1. A graph covering with 2 line-segments intersections
ctrs/graph_crossing1
Typical
|π™½π™Ύπ™³π™΄πš‚|>1
πš›πšŠπš—πšπšŽ(π™½π™Ύπ™³π™΄πš‚.𝚜𝚞𝚌𝚌)>1
πš›πšŠπš—πšπšŽ(π™½π™Ύπ™³π™΄πš‚.𝚑)>1
πš›πšŠπš—πšπšŽ(π™½π™Ύπ™³π™΄πš‚.𝚒)>1
Symmetries
  • Attributes of π™½π™Ύπ™³π™΄πš‚ are permutable w.r.t. permutation (𝚜𝚞𝚌𝚌) (𝚑,𝚒) (permutation applied to all items).

  • One and the same constant can be added to the 𝚑 attribute of all items of π™½π™Ύπ™³π™΄πš‚.

  • One and the same constant can be added to the 𝚒 attribute of all items of π™½π™Ύπ™³π™΄πš‚.

Usage

This is a general crossing constraint that can be used in conjunction with one graph covering constraint such as πšŒπš’πšŒπš•πšŽ, πšπš›πšŽπšŽ or πš–πšŠπš™. In many practical problems ones want not only to cover a graph with specific patterns but also to avoid too much crossing between the arcs of the final graph.

Remark

We did not give a specific crossing constraint for each graph covering constraint. We feel that it is better to start first with a more general constraint before going in the specificity of the pattern that is used for covering the graph.

See also

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

πšŒπš’πšŒπš•πšŽ, πš–πšŠπš™, πšπš›πšŽπšŽΒ (graph constraint,graph partitioning constraint), 𝚝𝚠𝚘_πš•πšŠπš’πšŽπš›_𝚎𝚍𝚐𝚎_πšŒπš›πš˜πšœπšœπš’πš—πšΒ (line-segments intersection).

Keywords

constraint type: graph constraint, graph partitioning constraint.

geometry: geometrical constraint, line-segments intersection.

Arc input(s)

π™½π™Ύπ™³π™΄πš‚

Arc generator
πΆπΏπΌπ‘„π‘ˆπΈ(<)β†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš—1,πš—2)

Arc arity
Arc constraint(s)
β€’ πš–πšŠπš‘(πš—1.𝚑,π™½π™Ύπ™³π™΄πš‚[πš—1.𝚜𝚞𝚌𝚌].𝚑)β‰₯πš–πš’πš—(πš—2.𝚑,π™½π™Ύπ™³π™΄πš‚[πš—2.𝚜𝚞𝚌𝚌].𝚑)
β€’ πš–πšŠπš‘(πš—2.𝚑,π™½π™Ύπ™³π™΄πš‚[πš—2.𝚜𝚞𝚌𝚌].𝚑)β‰₯πš–πš’πš—(πš—1.𝚑,π™½π™Ύπ™³π™΄πš‚[πš—1.𝚜𝚞𝚌𝚌].𝚑)
β€’ πš–πšŠπš‘(πš—1.𝚒,π™½π™Ύπ™³π™΄πš‚[πš—1.𝚜𝚞𝚌𝚌].𝚒)β‰₯πš–πš’πš—(πš—2.𝚒,π™½π™Ύπ™³π™΄πš‚[πš—2.𝚜𝚞𝚌𝚌].𝚒)
β€’ πš–πšŠπš‘(πš—2.𝚒,π™½π™Ύπ™³π™΄πš‚[πš—2.𝚜𝚞𝚌𝚌].𝚒)β‰₯πš–πš’πš—(πš—1.𝚒,π™½π™Ύπ™³π™΄πš‚[πš—1.𝚜𝚞𝚌𝚌].𝚒)
β€’ (πš—2.𝚑-π™½π™Ύπ™³π™΄πš‚[πš—1.𝚜𝚞𝚌𝚌].𝚑)*(π™½π™Ύπ™³π™΄πš‚[πš—1.𝚜𝚞𝚌𝚌].𝚒-πš—1.𝚒)-(π™½π™Ύπ™³π™΄πš‚[πš—1.𝚜𝚞𝚌𝚌].𝚑-πš—1.𝚑)*(πš—2.𝚒-π™½π™Ύπ™³π™΄πš‚[πš—1.𝚜𝚞𝚌𝚌].𝚒)β‰ 0
β€’ (π™½π™Ύπ™³π™΄πš‚[πš—2.𝚜𝚞𝚌𝚌].𝚑-π™½π™Ύπ™³π™΄πš‚[πš—1.𝚜𝚞𝚌𝚌].𝚑)*(πš—2.𝚒-πš—1.𝚒)-(πš—2.𝚑-πš—1.𝚑)*(π™½π™Ύπ™³π™΄πš‚[πš—2.𝚜𝚞𝚌𝚌].𝚒-π™½π™Ύπ™³π™΄πš‚[πš—1.𝚜𝚞𝚌𝚌].𝚒)β‰ 0
β€’ πšœπš’πšπš—(πš—2.𝚑-π™½π™Ύπ™³π™΄πš‚[πš—1.𝚜𝚞𝚌𝚌].𝚑)*(π™½π™Ύπ™³π™΄πš‚[πš—1.𝚜𝚞𝚌𝚌].𝚒-πš—1.𝚒)-(π™½π™Ύπ™³π™΄πš‚[πš—1.𝚜𝚞𝚌𝚌].𝚑-πš—1.𝚑)*(πš—2.𝚒-π™½π™Ύπ™³π™΄πš‚[πš—1.𝚜𝚞𝚌𝚌].𝚒)β‰ πšœπš’πšπš—(π™½π™Ύπ™³π™΄πš‚[πš—2.𝚜𝚞𝚌𝚌].𝚑-π™½π™Ύπ™³π™΄πš‚[πš—1.𝚜𝚞𝚌𝚌].𝚑)*(πš—2.𝚒-πš—1.𝚒)-(πš—2.𝚑-πš—1.𝚑)*(π™½π™Ύπ™³π™΄πš‚[πš—2.𝚜𝚞𝚌𝚌].𝚒-π™½π™Ύπ™³π™΄πš‚[πš—1.𝚜𝚞𝚌𝚌].𝚒)
Graph property(ies)
𝐍𝐀𝐑𝐂=π™½π™²πšπ™Ύπš‚πš‚

Graph model

Each node is described by its coordinates 𝚑 and 𝚒, and by its successor 𝚜𝚞𝚌𝚌 in the final covering. Note that the co-ordinates are initially fixed. We use the arc generator πΆπΏπΌπ‘„π‘ˆπΈ(<) in order to avoid counting twice the same line-segment crossing.

PartsΒ (A) andΒ (B) of FigureΒ 5.145.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. Each arc of the final graph corresponds to a proper intersection between two line-segments.

Figure 5.145.2. Initial and final graph of the πšπš›πšŠπš™πš‘_πšŒπš›πš˜πšœπšœπš’πš—πš constraint
ctrs/graph_crossingA
(a)
ctrs/graph_crossingB
(b)