Premium
The special routes in plane graphs
Author(s) -
Panyukova Tatiana
Publication year - 2007
Publication title -
pamm
Language(s) - English
Resource type - Journals
ISSN - 1617-7061
DOI - 10.1002/pamm.200701066
Subject(s) - eulerian path , vertex (graph theory) , plane (geometry) , edge cover , graph , combinatorics , enhanced data rates for gsm evolution , computer science , vertex cover , set (abstract data type) , mathematics , theoretical computer science , topology (electrical circuits) , geometry , artificial intelligence , lagrangian , pure mathematics , programming language
Let plane undirected graph G = ( V , E ) be set of items of all manipulator possible trajectories. The problem is constructing of routes satisfying different restrictions. The restrictions can be classified as local and global. For local restrictions the next edge in a route is defined by the conditions set for current vertex or edge. Otherwise restriction is called global. Examples of local restrictions are straightforward paths; a route in which the next edge is defined by the given cycle order on the set of edges incident the current vertex; a route where some edges should be passed in predefined order. The example of global restriction is problem of constructing the cover with ordered enclosing. The paper presents some ways to formalize restrictions and also information about algorithms for constructing of Eulerian covering for plane graph by the sequence of allowed trails. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)