|
Navigation: Home:
Achievements:
Downloads:
Theorems:
Glossary:
References:
Contact:
|
|
| |
Algorithms
New Algorithms
Maximum Induced Outerplanar Subgraph Problem (MIOPS)
- A palm forest is a graph consisting of components that are trees, cycles or trees augmented with triangles. A palm forest is an outerplanar graph. An algorithm for finding an induced palm forest was designed. It was shown that for any graph of n vertices and maximum degree at most d, this algorithm finds an induced palm tree of at least 3n/(d+(5/3)) vertices.
- An algorithm was designed to find an large induced outerplanar graph. The subgraph produced by this algorithm is at least as large as that found by the algorithm for finding an induced palm forest.
Larger Induced Planar Subgraphs
Observing the behaviour of the algorithms on randomly generated graphs, it was noticed that the size of subgraph produced by the algorithms for MIOPS was comparable to the size of subgraph produced by the existing algorithms for MIPS. It seemed likely that an induced outerplanar subgraph would not usually be a maximal induced planar subgraph. An algorithm to increase the size of an existing subgraph by adding vertices was designed. This algorithm was combined with both algorithms for MIOPS and MIPS and results showed it successfully increased the size of subgraphs produced.
Existing Approximation Algorithms for MIPS
Algorithms for graphs of maximum degree at most d.
- Halldórsson and Lau [4] designed an algorithm that partitions a graph into a number of parts. Each part consists of disjoint paths and/or cycles and is thus planar. The largest part is chosen as the planar subgraph. The size of subgraph is at least 1/ceil(d+1)/3)).
- Edwards and Farr [1,2] provided an algorithm that finds an induced planar subgraph of at least 3n/(d+1) vertices. This algorithm divides the vertices of the graph into two sets, R and P. Initially P is empty. The algorithm creates a planar subgraph <P> by incrementally adding vertices from the original graph to P or interchanging a vertex in P with one in R whilst maintaining planarity of the graph <P>.
Algorithms for graphs of average degree d.
- Edwards and Farr [3] designed an algorithm that finds an induced planar subgraph for graphs of average degree d. They show that such a subgraph contains at least 3n/(d+1) vertices. In this algorithm P initially contains all vertices of the original graph. The algorithm iteratively removes vertices from the graph until a condition is met that guarantees the induced subgraph <P> is planar.
Modifications to Existing Algorithms
- A hybrid algorithm was designed which combined the two algorithms by Edwards and Farr [1,2,3]. The algorithm iteratively adds vertices whilst maintaining planarity. When no more vertices can be added, the graph is examined to ascertain if a vertex can be found that if removed from the subgraph enables additional vertices to be included.
Algorithms for Related Problems
There are many known algorithms for finding an independent set or an induced forest subgraph of a graph. Both an independent set and an induced forest are induced planar subgraphs. Although they are unlikely to be a maximal induced planar subgraph, they may in practice provide a "good" solution.
Algorithms for graphs of maximum degree at most d.
- A maximal independent set produces an induced planar subgraph of at least n/(d+1) vertices.
- A maximal induced forest produces an induced planar subgraph of at least 2n/(d+1) vertices.
|
|