Applied Graph Theory

$V$-graphs and their relation to the problem of locating objects in a plane

I. G. Velichko^a, A. I. Zinchenko<sup>b

a</sup> Zaporizhzhya National Technical University, Zaporizhzhya, Ukraine
^b Zaporizhzhya National University, Zaporizhzhya, Ukraine

Abstract: For two congruent figures with no common interior points, the locations in a plane are studied. A line being parallel to a shift vector intersects these pieces in two identical systems of intervals shifted by this vector. An oriented $V_n$-graph is constructed, its vertices correspond to the topologically different variants of relative position of two systems of $n$ intervals, and the edges correspond to the allowable transitions between vertices. The term of $W_n$-graph is introduced as a minimal transitive graph which contains $V_n$-graph augmented with an incident vertex. The properties of $V_n$-graphs and $W_n$-graphs are proved.

Keywords: placement of figures in a plane oriented graph, $W$-graph, the Catalan numbers, Dyck path, system slots, congruent figures.

UDC: 519.171.1+514.17