Download PlaNet Tutorial and Reference Manual

3.2 Net Graph Problem with a Bounded Number of Nets
(bounded_n_nets_graph)
The class Net Graph Problem with a Bounded Number of Nets is a direct descendant of the class
General Net Graph Problem with the specialization that graphs in this problem class have a bounded
number of nets. The number of terminals in a net remains arbitrary. The number of nets can be set in
the class and is initially bounded to 1.
3.3 Net Graph Problem with a Bounded Number of Terminals per Net
(bounded_netsize_graph)
The class Net Graph Problem with a Bounded Number of Terminals per Net is also a direct descendant
of the class General Net Graph Problem. The graphs in this problem class have a bounded number of
terminals per net; the number of nets remains arbitrary. Initially, the number of terminals per net is
bounded to 2, but can be set to an arbitrary value.
3.4 Menger Problem (menger)
ë
ì
í
ì
í ë
Let be an undirected planar graph with two specified terminals and . The Menger Problem is to
find a maximum number of internally vertex/edge–disjoint paths between and in . Without loss
of generality, here, the embedding of is enforced such that is situated on the outer face of .
ë
í
ë
The class Menger Problem is modeled as a direct descendant of the class Net Graph Problem with a
Bounded Number of Nets and of the class Net Graph Problem with a Bounded Number of Terminals
per Net. The graphs of the class Menger Problem have one net with two terminals and . The
–terminal has to be on the outer face.
ì
í
í
3.5 Okamura–Seymour Problem (okamura_seymour_graph)
ëînï°ð åPñLò
ì©ø íø ùûú1üGúJý
ó?îõô¦ô/ì¦Ù å íö٘÷ å˜æ˜æ˜æ©å ô/ì/ç å íçh÷¦÷
ë
ï°ð åPñJþ ô/ì“Ù å íyÙÏ÷ þÿæ˜æ˜æ“þ ô/ì/ç å íšçh÷ ò
ÙÏå˜æ˜æ˜æ©å bç
Let
be an undirected planar graph with a set of nets
. The
terminal nodes , ,
, are all on the outer face of . Additionally, the so called evenness
condition is fulfilled, that is the extended graph
is Eulerian. The
Okamura–Seymour Problem is to decide whether there are pairwise edge–disjoint paths
,
so that connects with for
, and if so, to determine such a set of paths.
ø
ì©ø
ílø ü:îsù å˜æ˜æ˜æ©å ý
The class Okamura–Seymour Problem is modeled as a descendant of the class Net Graph Problem
with a Bounded Number of Terminals per Net. The graphs of this problem class contain an arbitrary
number of nets with two terminals each. Both of the terminals of each net are on the outer face, each
terminal has degree 1 and all other nodes have even degree.
17