|
Prikladnaya Diskretnaya Matematika, 2013, Number 4(22), Pages 41–46
(Mi pdm438)
|
|
|
|
Applied Graph Theory
$V$-graphs and their relation to the problem of locating objects in a plane
I. G. Velichkoa, A. I. Zinchenkob a 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.
Citation:
I. G. Velichko, A. I. Zinchenko, “$V$-graphs and their relation to the problem of locating objects in a plane”, Prikl. Diskr. Mat., 2013, no. 4(22), 41–46
Linking options:
https://www.mathnet.ru/eng/pdm438 https://www.mathnet.ru/eng/pdm/y2013/i4/p41
|
|