# MPI-I-95-1-014

## A polyhedral approach to planar augmentation and related problems

### Mutzel, Petra

**MPI-I-95-1-014**. June** **1995, 14 pages. | Status:** **available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:

Given a planar graph $G$, the planar (biconnectivity)

augmentation problem is to add the minimum number of edges to $G$

such that the resulting graph is still planar and biconnected.

Given a nonplanar and biconnected graph, the maximum planar biconnected

subgraph problem consists of removing the minimum number of edges so

that planarity is achieved and biconnectivity is maintained.

Both problems are important in Automatic Graph Drawing.

In [JM95], the minimum planarizing

$k$-augmentation problem has been introduced, that links the planarization

step and the augmentation step together. Here, we are given a graph which is

not necessarily planar and not necessarily $k$-connected, and we want to delete

some set of edges $D$ and to add some set of edges $A$ such that $|D|+|A|$

is minimized and the resulting graph is planar, $k$-connected and spanning.

For all three problems, we have given a polyhedral formulation

by defining three different linear objective functions over the same polytope,

namely the $2$-node connected planar spanning subgraph polytope $\2NCPLS(K_n)$.

We investigate the facial structure of this polytope for $k=2$,

which we will make use of in a branch and cut algorithm.

Here, we give the dimension of the planar, biconnected, spanning subgraph

polytope for $G=K_n$ and we show that all facets of the planar subgraph

polytope $\PLS(K_n)$ are also facets of the new polytope $\2NCPLS(K_n)$.

Furthermore, we show that the node-cut constraints arising in the

biconnectivity spanning subgraph polytope, are facet-defining inequalities

for $\2NCPLS(K_n)$.

We give first computational results for all three problems, the planar

$2$-augmentation problem, the minimum planarizing $2$-augmentation problem

and the maximum planar biconnected (spanning) subgraph problem.

This is the first time that instances of any of these three problems can

be solved to optimality.

Acknowledgement:** **

References to related material:

To download this research report, please select the type of document that fits best your needs. | Attachement Size(s): |

MPI-I-95-1-014.pdf | 67 KBytes; 200 KBytes |

Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView |

**URL to this document: **http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1995-1-014

**BibTeX**
`@TECHREPORT{``Mutzel95b``,`

` AUTHOR = {Mutzel, Petra},`

` TITLE = {A polyhedral approach to planar augmentation and related problems},`

` TYPE = {Research Report},`

` INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},`

` ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},`

` NUMBER = {MPI-I-95-1-014},`

` MONTH = {June},`

` YEAR = {1995},`

` ISSN = {0946-011X},`

`}`